BQP

Unsolved problem in computer science: What is the relationship between BQP and NP? (more unsolved problems in computer science)

The suspected relationship of BQP to other problem spaces^[1]

In computational complexity theory, BQP (bounded error quantum polynomial time) 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 of the complexity class BPP.

In other words, there is an algorithm for a quantum computer (a quantum algorithm) that solves the decision problem with high probability and is guaranteed to run in polynomial time. On any given run of the algorithm, it has a probability of at most 1/3 that it will give the wrong answer.

Similarly to other "bounded error" probabilistic classes the choice of 1/3 in the definition is arbitrary. We can run the algorithm a constant number of times and take a majority vote to achieve any desired probability of correctness less than 1, using the Chernoff bound. Detailed analysis shows that the complexity class is unchanged by allowing error as high as 1/2 − n^−c on the one hand, or requiring error as small as 2^−nc on the other hand, where c is any positive constant, and n is the length of input.

Definition

BQP can also be viewed as a bounded-error uniform family of quantum circuits. A language L is in BQP if and only if there exists a polynomial-time uniform family of quantum circuits , such that

• For all , Q_n takes n qubits as input and outputs 1 bit
• For all x in L,
• For all x not in L,

Quantum computation

The number of qubits in the computer is allowed to be a polynomial function of the instance size. For example, algorithms are known for factoring an n-bit integer using just over 2n qubits (Shor's algorithm).

Usually, computation on a quantum computer ends with a measurement. This leads to a collapse of quantum state to one of the basis states. It can be said that the quantum state is measured to be in the correct state with high probability.

Quantum computers have gained widespread interest because some problems of practical interest are known to be in BQP, but suspected to be outside P. Some prominent examples are:

• Integer factorization (see Shor's algorithm)^[2]
• Discrete logarithm^[2]
• Simulation of quantum systems (see universal quantum simulator)
• Approximating the Jones polynomial at certain roots of unity

Relationship to other complexity classes

This class is defined for a quantum computer and its natural corresponding class for an ordinary computer (or a Turing machine plus a source of randomness) is BPP. Just like P and BPP, BQP is low for itself, which means BQP^BQP = BQP. Informally, this is true because polynomial time algorithms are closed under composition. If a polynomial time algorithm calls as a subroutine polynomially many polynomial time algorithms, the resulting algorithm is still polynomial time.

BQP contains P and BPP and is contained in AWPP,^[3] PP^[4] and PSPACE.^[5] In fact, BQP is low for PP, meaning that a PP machine achieves no benefit from being able to solve BQP problems instantly, an indication of the possible difference in power between these similar classes.

As the problem of P ≟ PSPACE has not yet been solved, the proof of inequality between BQP and classes mentioned above is supposed to be difficult.^[5] The relation between BQP and NP is not known.

Adding postselection to BQP results in the complexity class PostBQP which is equal to PP.^[6][7]

External links

• Complexity Zoo link to BQP

References

1. ↑ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.
2. 1 2 arXiv:quant-ph/9508027v2 Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor
3. ↑ Fortnow, Lance; Rogers, John (1999). "Complexity limitations on Quantum computation" (PDF). J. Comput. Syst. Sci. Boston, MA: Academic Press. 59 (2): 240–252. doi:10.1006/jcss.1999.1651. ISSN 0022-0000. 
4. ↑ L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997.
5. 1 2 Bernstein and Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997.
6. ↑ Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A. 461 (2063): 3473–3482. doi:10.1098/rspa.2005.1546. . Preprint available at
7. ↑ Aaronson, Scott (2004-01-11). "Complexity Class of the Week: PP". Computational Complexity Weblog. Retrieved 2008-05-02. 

Quantum information science
General	Quantum computer Qubit Quantum information Quantum machine Quantum programming Timeline of quantum computing
Quantum communication	Quantum capacity Classical capacity Entanglement-assisted classical capacity Quantum channel Quantum network Quantum cryptography Quantum key distribution Quantum energy teleportation Quantum teleportation Superdense coding LOCC Entanglement distillation
Quantum algorithms	Universal quantum simulator Deutsch–Jozsa algorithm Grover's algorithm Quantum Fourier transform Shor's algorithm Simon's problem Quantum phase estimation algorithm Quantum annealing Algorithmic cooling
Quantum complexity theory	Quantum Turing machine EQP BQP QMA PostBQP
Quantum computing models	Quantum circuit Quantum gate One-way quantum computer cluster state Adiabatic quantum computation Topological quantum computer
Decoherence prevention	Quantum error correction Stabilizer codes Entanglement-Assisted Quantum Error Correction Quantum convolutional codes
Physical implementations	Quantum optics Cavity QED Circuit QED Linear optical quantum computing Ultracold atoms Trapped ion quantum computer Optical lattice Spin-based Nuclear magnetic resonance QC Kane QC Loss–DiVincenzo QC Nitrogen-vacancy center Superconducting quantum computing Charge qubit Flux qubit Phase qubit