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
Previous Page Next Page