Quantum Algorithm Complexity
Quantum Algorithm Complexity
| Algorithm | Problem | Classical Best | Quantum | Speedup |
|---|---|---|---|---|
| Deutsch-Jozsa | Constant vs balanced function | O(2^(n-1)) | O(1) | Exponential |
| Bernstein-Vazirani | Hidden bit string (linear oracle) | O(n) | O(1) | Linear |
| Simon's | Hidden XOR period | O(2^(n/2)) | O(n) | Exponential |
| Shor's | Integer factoring | O(exp(n^1/3)) | O(n³) | Exponential |
| Grover's | Unstructured search (N items) | O(N) | O(√N) | Quadratic |
| HHL | Linear systems Ax=b | O(Ns·κ) | O(log(N)·κ²) | Exponential (sparse) |
| QFT | Discrete Fourier transform | O(N log N) | O(n²) for n=log N | Exponential |
| QAOA | Combinatorial optimization | Varies | Heuristic | Unknown |
| VQE | Ground state energy | O(exp(n)) | O(poly(n)) est. | Exponential (est.) |
| Quantum Walk | Element distinctness | O(N) | O(N^2/3) | Polynomial |
Qubit Requirements (Fault-Tolerant Estimates)
| Task | Logical Qubits | Physical Qubits (est.) | Status |
|---|---|---|---|
| Break RSA-2048 (Shor's) | ~4,000 | ~4 million | 10-20 years away |
| Grover's search (1M items) | ~20 | ~20,000 | 5-10 years away |
| FeMoco (nitrogen fixation, VQE) | ~111 | ~111,000 | 5-10 years away |
| Small molecule chemistry | ~50 | ~50,000 | 3-7 years away |
| Practical QML | TBD | TBD | Research stage |
BQP - Quantum Complexity
| Class | Problems |
|---|---|
| P | Classically easy: sorting, shortest path, linear programming |
| NP | Verifiable in poly time: SAT, TSP, graph coloring |
| BQP | Quantum poly-time: factoring, discrete log, simulation |
| BPP ⊆ BQP ⊆ PSPACE | Quantum is strictly more powerful than classical randomized |
| BQP vs NP | Unknown - quantum probably doesn't solve all NP problems |