Index

Algorithm, 9

for finding the hidden subgroup

in Zk, 136

for period finding, 122, 128

Grover’s, 83

Grover’s (for the solution of the general

search problem), 87

nondeterministic, 28

primality testing, 40

probabilistic, 36

quantum, 90, 91

Simon’s (for finding the hidden subgroup

in Z2

k),

118

Amplification of probability, 37, 83, 139, 141

Amplitudes, 55, 92

Ancilla, 60

Angle between subspaces, 147

Anyons, 173

Automaton

finite-state, 24

Basis

classical, 55

Bit, 1

quantum (qubit), 53

Bra-vector, 56

Carmichael numbers, 39

Check matrix

for a linear classical code, 155

Check operator, 167

Chernoff’s bound, 127, 231

Church thesis, 12

Circuit

Boolean, 17

depth, 23

fan-in, 23

fan-out, 23

formula, 18

graph, 17

size, 19

width, 27

quantum, 60

complete basis, 73

standard basis, 73

universal, 89

reversible, 61

complete basis, 61

uniform sequence of, 22, 23, 90

Circuit complexity, 20

Clause, 33

CNF, 19, 33

Code

Hamming, 155

repetition, 154

Shor, 161

Code distance

classical, 154

Codes, error-correcting, 151

classical, 152

linear, 155

quantum, 152

congruent symplectic, 168

symplectic, 167, 168

toric, 170

Codevector, 152

Codeword, 152

Complexity classes, 14

BQNP, 138

Πk, 46

Σk, 45, 46

255