EQP (complexity)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In computational complexity theory, EQP (sometimes called QP), which stands for exact quantum polynomial time, is the class of decision problems solvable by a quantum computer which outputs the correct answer with probability 1 and runs in polynomial time. It is the quantum analogue of the complexity class P.

In other words, there is an algorithm for a quantum computer (a quantum algorithm) that solves the decision problem exactly and is guaranteed to run in polynomial time.