Quantum Complexity Classes

Introduction......Page 5
Hilbert space......Page 7
Tensor product......Page 8
Qubits and gates......Page 9
Classical deterministic Turing machine......Page 11
Deterministic Turing machines with oracles......Page 13
Probabilistic Turing machine......Page 14
Quantum Turing machine......Page 15
The quantumness of a quantum Turing machine......Page 17
Quantum circuits......Page 19
Universal sets of gates......Page 20
Some important gates......Page 21
Entanglement......Page 23
Quantum query model......Page 24
Relation between QTMs and Quantum circuits......Page 25
Classical classes......Page 26
BQP class......Page 28
The class BQP revisited......Page 29
The new families......Page 33
The classes MQt(n)......Page 34
Basic properties......Page 35
Building the hierarchy......Page 36
Putting some problems into the classes......Page 42
The class M2......Page 47
GapP functions......Page 52
Hierarchy with the new classes......Page 55
Conclusions and remarks......Page 57