OP-3006OpenQuantum information

BPP versus BQP

Determine whether $\mathsf{BPP}=\mathsf{BQP}$ , or prove that efficient bounded-error quantum computation is strictly more powerful than efficient randomized classical computation.

Source-reported statusAs of 2026-09-04Source & evidence ↓

Read original source ↗ 0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Determine whether $\mathsf{BPP}=\mathsf{BQP}$ , or prove that efficient bounded-error quantum computation is strictly more powerful than efficient randomized classical computation.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

This is a sharp equality question, even though an unconditional separation is a long-horizon challenge. Since $\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}\subseteq\mathsf{PSPACE}$ , proving $\mathsf{BPP}\ne\mathsf{BQP}$ would also prove $\mathsf{P}\ne\mathsf{PSPACE}$ .

What is known: Bernstein–Vazirani's recursive Fourier sampling and Simon's problem give oracle/query-model evidence. Raz–Tal proved a classical-oracle separation of BQP from the entire polynomial hierarchy. These are relativized results, not unrelativized class separations. Shor's polynomial-time factoring algorithm is further evidence of quantum advantage, but an exponential advantage for factoring is not proved: no superpolynomial classical lower bound is known.

The question compares the same finite-input, bounded-error computation model; alternative data-access or output conventions belong in the methods discussion A16. Related: A2, A11.

Progress & source assessment

Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.

References

[1]Bernstein & Vazirani, 'Quantum complexity theory', SIAM J. Comput. 26 (1997) link
[2]Raz & Tal, 'Oracle separation of BQP and PH', STOC 2019 link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.