🧠

Topic 12 of 12

Quantum Complexity Theory

Quantum complexity theory classifies computational problems by the resources (time, space, qubits) a quantum computer needs to solve them. The class BQP (Bounded-error Quantum Polynomial time) captures efficiently quantum-solvable problems. Understanding BQP's relationship to P, NP, and other classical classes determines what quantum computers actually buy us — and where their limits lie.

Key Concepts

BQP

Bounded-error Quantum Polynomial time: the class of problems solvable by a quantum computer in polynomial time with error probability at most 1/3. Factoring (Shor) and discrete logarithm are in BQP. We know P ⊆ BQP, but whether NP ⊆ BQP is open — most complexity theorists believe NP-complete problems are NOT efficiently quantum-solvable.

BQP vs NP

The relationship between BQP and NP is unknown and considered one of the most important open problems in computer science. Quantum computers likely cannot solve NP-complete problems (like 3-SAT or TSP) in polynomial time. Grover's O(√N) speedup is not sufficient to place NP in BQP — it still leaves exponential time for NP-hard problems.

QMA

Quantum Merlin-Arthur: the quantum analogue of NP. QMA contains problems where a quantum proof (witness) can be verified efficiently by a quantum computer. Local Hamiltonian problems (determining ground state energy) are QMA-complete. QMA is believed strictly harder than BQP, just as NP is believed harder than P.

Quantum Supremacy / Advantage

Quantum computational advantage occurs when a quantum computer outperforms all classical computers on a specific task. Google's 2019 Sycamore experiment demonstrated this for random circuit sampling — a task 53 qubits solved in 200 seconds that would take classical supercomputers ~10,000 years. However, the task was not practically useful.

Oracle Separations

Relative to a quantum oracle, BQP ≠ NP (Bernstein-Vazirani separation) and there exist problems in BQP not in the polynomial hierarchy (Raz-Tal, 2019). Oracle separations prove quantum speedups exist in query complexity but do not directly resolve circuit complexity questions like P vs NP.

Simulation of Quantum Systems

Feynman's original motivation (1982): simulating quantum systems classically requires exponential resources (storing

2^n

amplitudes for

n

qubits), but a quantum computer of

n

qubits can simulate them efficiently. Quantum chemistry and materials simulation are the most promising near-term quantum applications.

Key Equations

BQP Containment

\text{P} \subseteq \text{BQP} \subseteq \text{PSPACE},\quad \text{NP} \not\subseteq \text{BQP (?)}

Known containments; the BQP vs NP question is open.

Quantum Speedup Classes

\text{Grover: } O(\sqrt{N}), \quad \text{Shor: } O((\log N)^3), \quad \text{Classical GNFS: } e^{O((\log N)^{1/3})}

Comparing quantum and classical complexities for search and factoring.

Hilbert Space Scaling

\dim(\mathcal{H}_n) = 2^n \implies \text{classical simulation of } n \text{ qubits requires } O(2^n) \text{ memory}

The exponential growth of Hilbert space dimension makes classical quantum simulation infeasible for large n.

BQP Error Bound

P_{\text{BQP algorithm succeeds}} \geq \frac{2}{3}

BQP algorithms must succeed with probability at least 2/3; errors can be reduced by repetition.

Worked Example

Classifying Problems by Quantum Speedup

Problem

Classify the following problems: (a) Factoring, (b) Unstructured search, (c) 3-SAT, (d) Quantum chemistry simulation.

Solution

(a) Factoring: Shor's algorithm → In BQP. Exponential quantum speedup over classical.

(b) Unstructured search: Grover → In BQP. Quadratic speedup (O(√N) vs O(N)).

(d) Quantum chemistry: Local Hamiltonians → BQP or QMA depending on precision. Primary near-term application of quantum computers.

Answer Factoring and search are in BQP; NP-complete problems likely are not.

Practice

Exercises

5 problems

1 of 5

Grover searches $N$ items in $O(N^p)$ queries. What is $p$ ?

Your answer

2 of 5

$\log_2(1024) = ?$ (This is the number of qubits needed to represent 1024 states.)

Your answer

3 of 5

Simulating $n=50$ qubits classically requires $2^{50}$ complex amplitudes. $2^{50} \approx 10^p$ — what is $p$ (to 1 decimal)?

Unlock Exercise 3

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

4 of 5

A BQP algorithm must succeed with probability at least $2/3$ . Express $2/3$ as a decimal (to 3 places).

Unlock Exercise 4

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

5 of 5

Shor's algorithm runs in $O((\log N)^k)$ time. What is $k$ ?

Unlock Exercise 5

Subscribe to PhysWeb Pro to access all exercises and track your progress.

Upgrade to Pro →

Key Takeaways

BQP is the class of efficiently quantum-solvable problems; P ⊆ BQP ⊆ PSPACE, with NP relationship unknown.
Factoring and discrete log are in BQP; NP-complete problems like 3-SAT are not believed to be.
QMA is the quantum analogue of NP; Local Hamiltonian is QMA-complete.
Classical simulation of $n$ qubits requires $O(2^n)$ memory — the fundamental motivation for quantum computers.
Quantum advantage is proven in query complexity (oracles) but not yet for practically useful problems in circuit complexity.