Index 257
using ancillas, 60
unitary, 57
with quantum control, 65
Oracle, 26, 35, 83, 117
quantum, 118
randomized, 117
Partial trace, 96
Pauli matrices, 66
Phase estimation, 125, 128
Polynomial growth, 14
POVM, 107
Predicate, 12
decidable, 12
Problem
TQBF , 50
3-CNF, 33
3-SAT, 33
3-coloring, 34
clique, 35
determining the discrete logarithm, 136
Euler cycle, 35
factoring, 120
general search, 83
quantum formulation of, 84
hidden subgroup, 117, 135
ILP, 34
independent set, 198
local Hamiltonian, 142
matching
perfect, 35
period finding, 120
primality, 38
satisfiability, 31
TQBF, 64
with oracle, 83
Pseudo-random generator, 43
Purification, 97
unitary equivalence, 98
Quantum computer, 53
Quantum Fourier transform, 88, 135, 218
Quantum probability
for simple states, 93
general definition, 95
simplest definition, 55, 82
Quantum register, 58
Quantum teleportation, 108, 227–229
Resolution method, 195
Schmidt decomposition, 97
Set
enumerable, 16
Singular value, 57
decomposition, 57
State of a quantum system
basis, 53
entangled, 60
mixed, 95
product, 60
pure, 95
Superoperator, 100, 106
physically realizable, 100
characterization, 100, 101
Superposition of states, 54
Syndrome, 172
Tensor product, 55
of operators, 57
universality property, 55
Transformation, error-correcting, 158, 161
classical, 154
for symplectic codes, 172
Turing machine, 10
alphabet, 9, 10
blank symbol, 10
cell, 10
computational table, 20, 32
configuration, 11
control device, 10
external alphabet, 10
head, 10
initial configuration, 11
initial state, 10
input, 11
multitape, 16
nondeterministic, 28
computational path, 28
output, 11
probabilistic, 36
state, 10
step (or cycle) of work, 11
tape, 10
universal, 14
with oracle, 26, 50
Turing thesis, 12
Witness, 38
http://dx.doi.org/10.1090/gsm/047/31
Previous Page Next Page