BQP
Bounded-error quantum polynomial time: the class of problems solvable in polynomial time by a quantum computer with at least a fixed probability of success.
As defined in 99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
Where it comes up · 1
Most important claims · 5 of 5Search all claims for “BQP” →
- The biggest mistake popular writers have made about quantum computers for 25 years is conflating NP with BQP — writing as if a quantum computer is a magical machine for solving all NP problems by trying each answer in a parallel universe — when in fact NP and BQP are believed to be incomparable, factoring was a lucky special case, and typical exponentially hard problems remain exponentially hard on a quantum computer.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- Peter Shor's 1994 algorithm showed that factoring an n-digit number, the basis of most modern encryption, lies in BQP — solvable on a quantum computer in roughly N-squared operations — versus the best known classical algorithm (the number field sieve) which takes time growing exponentially in roughly the cube root of N; this exploits special structure from group theory, number theory and the Fourier transform, not mere parallel-universe trial of every divisor.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- Because P is contained in BQP which is contained in PSPACE, quantum computers can give at most an exponential running-time advantage over classical ones and cannot solve anything uncomputable like the halting problem; moreover, proving P is not equal to BQP would require proving P is not equal to PSPACE, explaining why a real-world quantum advantage cannot yet be proven.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- A quantum computer's power comes from the fact that to describe the state of just 1000 qubits requires a list of 2-to-the-1000 complex amplitudes — one for every possible configuration — making the underlying objects enormously larger than classical bit-strings and opening the potential to compute more in polynomial time, captured by the class BQP (bounded-error quantum polynomial time).99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity
- A quantum computer can always efficiently simulate a classical computer, so P is contained in BQP — like using a space shuttle to taxi around a parking lot, possible but not the point.99 | Scott Aaronson on Complexity, Computation, and Quantum Gravity