computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

, exact quantum polynomial time (EQP or sometimes QP) is the class of

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

s that can be solved by a

quantum computer Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...

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 to bounded-error quantum computing, where quantum

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

s 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.

References

* {{ComplexityClasses Quantum complexity theory