QuantumAtlas

Algorithms

BQP Complexity Class

The class of decision problems that a quantum computer can solve efficiently with a small chance of error.

Definition

BQP is the formal name for the problems that quantum computers can solve quickly. The letters stand for bounded-error quantum polynomial time: a quantum computer gets the right answer with high probability, in a number of steps that grows only polynomially with the size of the input. It is the quantum counterpart of the class P for classical computers, and the question of how BQP relates to other classes tells us what quantum computers can and cannot be expected to do.

In depth

Complexity classes let us ask precisely whether quantum computers are more powerful than classical ones. Factoring and discrete logarithms are in BQP because of Shor's algorithm, but they are not known to be in P, so if factoring is truly hard classically, BQP is larger than P. The classes BPP, probabilistic classical computation, and BQP are not known to differ, and no one has proven that quantum computers can solve any problem classically intractable, because that would also prove that P differs from PSPACE, a major open problem.

What is believed is that BQP does not contain NP-complete problems. Grover's algorithm gives only a quadratic speedup for search, and there is evidence in the oracle model that no quantum algorithm can solve NP-complete problems in polynomial time. Raz and Tal showed in 2018 that relative to an oracle, BQP is not contained in the polynomial hierarchy, which is evidence that quantum computers can do things beyond even large parts of classical complexity. Other classes matter too: QMA is the quantum analogue of NP, and the ground-state problem for local Hamiltonians is QMA-complete.

BQP is also the right frame for understanding quantum advantage experiments. Sampling tasks such as random circuit sampling and boson sampling are not decision problems, but hardness results show that efficient classical simulation would collapse the polynomial hierarchy, which gives the claims theoretical grounding. At the same time, practical advantage depends on constants, error correction overheads, and classical improvements, none of which the asymptotic class captures.

Technical Definition

BQP is the set of decision problems solvable by a uniform family of polynomial-size quantum circuits that output the correct answer with probability at least 2 over 3 on every input. The constant 2 over 3 can be amplified to any value below 1 by repetition. Known relationships are P is contained in BPP, which is contained in BQP, which is contained in PSPACE.

Visual Explanation: An Analogy

Think of a team of problem-solvers sorted by speed. P holds the problems an ordinary computer solves quickly. BQP is a larger group that includes everything in P and some extra problems, like factoring, that a quantum computer can crack quickly. Where the boundary of the group lies is the interesting question.

Key facts

ItemDetail
DefinitionDecision problems solvable by polynomial-size quantum circuits with error at most 1 over 3
Known relationsP in BPP in BQP in PSPACE
ContainsFactoring, discrete logarithm, and simulation of quantum systems
Believed not to containNP-complete problems
Defined byBernstein and Vazirani, 1993

Where the idea comes from

Bernstein and Vazirani defined BQP in their 1993 paper Quantum Complexity Theory, building on Deutsch's 1985 quantum Turing machine. Shor's 1994 algorithm gave the first major problem in BQP not known to be in BPP, and Raz and Tal's 2018 oracle separation was a milestone.

Real-World Use Cases

  • Classifying which problems a quantum computer can solve efficiently.
  • Giving theoretical backing for quantum advantage claims.
  • Setting expectations on what quantum computers cannot do, such as solving NP-complete problems.
  • Guiding the search for new quantum algorithms.

How it differs from related ideas

  • P is solvable by classical computers in polynomial time, BPP by randomized ones, and BQP by quantum ones.
  • NP is checkable in polynomial time, and BQP is solvable in polynomial time. They are not known to be related by inclusion.
  • QMA is to BQP as NP is to P.

Common Misconceptions

  • BQP does not mean quantum computers solve all hard problems. It is believed to exclude NP-complete ones.
  • It has not been proven that BQP is larger than P. That would be a breakthrough in complexity theory.
  • Being in BQP does not mean a problem is practical, since the polynomial may be large.

Frequently asked questions

What is BQP?

The class of decision problems that quantum computers can solve in polynomial time with high probability of being correct.

Can quantum computers solve NP-complete problems?

There is no evidence they can in polynomial time. The best known generic speedup is quadratic from Grover's algorithm.

Is factoring in BQP?

Yes, by Shor's algorithm, although it is not known whether factoring is in P.

Related Terms

Keep exploring

← Back to the dictionary