 | This articlemay contain improper references touser-generated content. Please helpimprove it by removing references tounreliable sources, where they areused inappropriately.(February 2023) (Learn how and when to remove this message) |
Incomputational complexity theory,exact quantum polynomial time (EQP or sometimesQP) is the class ofdecision problems that can be solved by aquantum computer with zero error probability and in guaranteed worst-case polynomial time. It is the quantum analogue of the complexity class P. This is in contrast tobounded-error quantum computing, where quantumalgorithms are expected to run in polynomial time, but may not always do so.
In the original definition of EQP, each language was computed by a single quantum Turing machine (QTM), using a finite gate set whose amplitudes could be computed in polynomial time. However, some results have required the use of an infinite gate set. The amplitudes in the gate set are typically algebraic numbers.
| P ≟ NP | Thistheoretical computer science–related article is astub. You can help Wikipedia byadding missing information. |
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems | |||||||||
| Quantum communication |
| ||||||||
| Quantum algorithms | |||||||||
| Quantum complexity theory | |||||||||
| Quantum processor benchmarks | |||||||||
| Quantum computing models | |||||||||
| Quantum error correction | |||||||||
| Physical implementations |
| ||||||||
| Quantum programming | |||||||||
