Open problems

The exact relationship between what quantum computers can do efficiently (BQP) and the NP / polynomial-hierarchy landscape is unproven in either direction. Aaronson's 2009 work gave evidence — a relativized world where BQP is not in the polynomial hierarchy — but no unconditional separation exists. The working conjecture in the field is that NP-complete problems stay hard for quantum computers; the applications map on this site is written under that assumption.

Classically, the PCP theorem says certain approximation problems are as hard as exact ones. The quantum version asks whether estimating the ground energy of a local Hamiltonian to constant precision is QMA-hard. Aharonov, Arad and Vidick's 2013 survey framed the question and its consequences for physics (robust entanglement at constant temperature); it remains unresolved.

In 2018 Ewin Tang gave a classical algorithm for recommendation systems that, assuming sample-and-query access to the data, matches the earlier quantum algorithm up to polynomial factors — erasing a claimed exponential speedup. The pattern has since been applied to other quantum-machine-learning algorithms; which remaining speedups are genuine versus artifacts of a data-access assumption is an active question, and the reason the applications map labels quantum machine learning 'promising, unproven'.

Aharonov and Ben-Or proved that quantum computation can be made robust against errors when the error rate is below a constant threshold — for a noise model the abstract describes as general and not necessarily probabilistic, and even for one-dimensional devices with nearest-neighbor interactions. The guarantee is relative to that model: whether a real device's correlated, drifting or leakage errors fit it well enough is exactly what the below-threshold experiments on the scoreboard test.

Preskill's 2018 'NISQ' paper named the era of noisy intermediate-scale devices (50–100 qubits, in his framing) and argued they may surpass classical computers on some tasks while noting that gate noise limits the circuit sizes that run reliably. Eight years on, the strongest advantage claims (see the hardware scoreboard and applications map) still come with caveats, and whether NISQ-era devices deliver useful advantage before fault tolerance remains an open empirical question — one DARPA's benchmarking initiative exists to adjudicate.