256 Index
P/poly, 20
BPP, 36, 37
MA, 138
Arthur and Merlin, 30, 139
BPP, 150
BQNP, 150, 151
BQP, 91
definition using games, 44, 139, 151
dual class (co-A), 44
EXPTIME, 22
MA, 150
NC, 23
NP, 28, 150
Karp reducibility, 30
NP-complete, 31
P, 14
PP, 91
PSPACE, 15, 150
Computation
nondeterministic, 27
probabilistic, 36
quantum, 83
reversible, 63
Copying
of a quantum state, 103
Decoherence, 102
Density matrix, 95
Diagonalization, 179
distance function, 77
DNF, 19
Element cf. Operator
Elementary transformation, 58
Encoding
for a quantum code, 153
one-to-many, 153
Error
classical, 161
phase, 161
Fidelity, 99
distance, 99
Function
Boolean, 17
basis, 17
complete basis, 18
conjunction, 19
disjunction, 19
negation, 19
standard complete basis, 18, 19
computable, 11, 12
majority, 26, 83
partial, 10, 138
total, 10
Garbage, 62
removal, 63
Gate
controlled NOT, 62
Deutsch, 75
Fredkin, 206
quantum, 60
Toffoli, 61
Group
(Z/qZ)∗, 120, 121
ESp2(n), 164, 166
SO(3), 66, 75
Sp2(n), 165
U(1), 66
U(2), 66
character, 118
Hamiltonian, 156, 173
k-local, 142
cycle, 28
graph, 28
Inner product, 56
Ket-vector, 56
Language, 12
Literal, 19
Measurement, 92, 105
conditional probabilities, 114
destructive, 107
POVM, 107
projective, 107
Measuring operator, 112, 113
conditional probabilities, 112
eigenvalues, 113
Miller–Rabin test, 38
Net, 77
α-sparse, 77
in SU(M), 77
quality, 77
Norm
of a superoperator
stable, 110
unstable, 108
operator, 71
trace, 98
Operator
applied to a register, 58
approximate representation, 72
using ancillas, 73
Hermitian adjoint, 56
permutation, 61
projection, 93
realized by a quantum circuit, 60
http://dx.doi.org/10.1090/gsm/047/30
Previous Page Next Page