alt=Diagram of randomised complexity classes|thumb|upright=1.25|BQP in relation to other probabilistic complexity classes (ZPP (complexity)|ZPP, RP, co-RP, BPP, PP), which generalise P within [[PSPACE. It is unknown if any of these containments are strict.]] In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.
Article
11 sectionsContents
- Definition
- Relationship to other complexity classes
- A complete problem for Promise-BQP
- APPROX-QCIRCUIT-PROB
- BQP and EXP
- BQP and PSPACE
- BQP and PP
- P and BQP {{anchor|BQP, P, and NP}}
- See also
- References
- External links
alt=Diagram of randomised complexity classes|thumb|upright=1.25|BQP in relation to other probabilistic complexity classes (ZPP (complexity)|ZPP, RP, co-RP, BPP, PP), which generalise P within [[PSPACE. It is unknown if any of these containments are strict.]] In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.
A decision problem is a member of BQP if there exists a quantum algorithm (an algorithm that runs on a quantum computer) that solves the decision problem with high probability and is guaranteed to run in polynomial time. A run of the algorithm will correctly solve the decision problem with a probability of at least 2/3.