Table of Contents
- Introduction
- MIP* = RE and Its Impact
- Quantum PCP Progress and New Approaches
- QMA-Completeness Results for Hamiltonians
- Quantum Supremacy: Refinements and Limits
- Interactive Proofs with Quantum Verifiers
- Quantum Proof Compression and Verification
- Advances in Quantum Query Complexity
- Tight Bounds for Quantum Walk Algorithms
- Quantum Separations in Communication Complexity
- Lattice Problems and Quantum Lower Bounds
- Quantum Machine Learning Complexity
- Quantum State Certification Protocols
- BQP vs SZK and Oracle Constructions
- Reductions Between Quantum Learning Problems
- Randomness Expansion via Quantum Protocols
- Quantum Advice, Delegation, and Verification
- Circuit Lower Bounds in Restricted Quantum Models
- Quantum Nonlocal Games and Hardness Amplification
- Conclusion and Open Questions
1. Introduction
Quantum complexity theory (QCT) is evolving rapidly, with breakthroughs in interactive proofs, quantum learning, and cryptography. This review summarizes major recent results that define and refine the structure and power of quantum computations.
2. MIP* = RE and Its Impact
This landmark result shows that multiprover interactive proofs with entangled provers can decide all recursively enumerable languages. It implies:
- Undecidability of the quantum Tsirelson problem
- Collapse of classical vs quantum proof separation in this setting
- Deeper connections between entanglement and computation
3. Quantum PCP Progress and New Approaches
Recent work develops:
- Quantum low-degree testing for QPCP
- Quantum locally testable codes
- New encoding schemes for constant-soundness QMA
These approaches aim to resolve the QPCP conjecture or construct robust QMA-hard approximation problems.
4. QMA-Completeness Results for Hamiltonians
New complete problems have been proposed for:
- Translationally invariant Hamiltonians
- Fermionic systems and condensed matter models
- Low-energy quantum optimization with locality constraints
These results expand QMA’s expressiveness in modeling physics.
5. Quantum Supremacy: Refinements and Limits
Post-Google, refinements include:
- Classical simulators based on tensor contraction and hybrid Monte Carlo
- Better noise models for supremacy tasks
- Debate over robustness and reproducibility
Focus is shifting toward practical, certifiable advantage in useful domains.
6. Interactive Proofs with Quantum Verifiers
Quantum interactive proof classes (like QIP and QIP(2)) have new completeness/soundness tradeoff protocols and verifier restrictions. Applications include cryptographic delegation and trust verification.
7. Quantum Proof Compression and Verification
Recent protocols use:
- Quantum state tomography with fewer copies
- Compressed QMA protocols
- Self-verifying quantum proofs
These aim to reduce proof length and allow public verifiability.
8. Advances in Quantum Query Complexity
Key developments include:
- Tight adversary lower bounds for symmetric functions
- Improvements in triangle detection and collision problems
- Hybrid adversary techniques for bounded-error queries
9. Tight Bounds for Quantum Walk Algorithms
Quantum walks over Johnson graphs and product graphs now have nearly optimal query complexity bounds. Applications include hitting time, graph property testing, and element distinctness.
10. Quantum Separations in Communication Complexity
Quantum-classical separations have been shown for:
- Total functions under low-cost models
- One-way and simultaneous message protocols
- Distributed learning under bandwidth constraints
11. Lattice Problems and Quantum Lower Bounds
New insights into:
- Reductions from Ring-LWE and Module-LWE
- No-go results for certain quantum approximations of SVP
- Hybrid hardness assumptions for cryptographic analysis
12. Quantum Machine Learning Complexity
Ongoing results include:
- Lower bounds for learning with quantum statistical queries
- Limits of quantum neural nets under noise
- Quantum boosting and perceptron complexity
13. Quantum State Certification Protocols
Protocols allow:
- Self-testing of quantum devices
- Efficient certification of entanglement and mixed states
- Property testing with fewer measurements
14. BQP vs SZK and Oracle Constructions
Recent oracle results show:
- BQP ⊄ SZK (statistical zero knowledge) in relativized worlds
- New candidate problems for collapsing SZK under quantum adversaries
15. Reductions Between Quantum Learning Problems
New frameworks connect:
- Quantum agnostic learning and boosting
- Reductions from noisy label problems to LWE-style assumptions
- Complexity of learning stabilizer and Clifford circuits
16. Randomness Expansion via Quantum Protocols
Device-independent protocols expand random bits using:
- Bell inequality violations
- Nonlocal games
- Verified quantum sampling
These systems are now robust to noise and loss.
17. Quantum Advice, Delegation, and Verification
Recent work explores:
- Non-interactive quantum delegation
- Delegation with reusable quantum advice
- Verification protocols with one-time classical interactions
18. Circuit Lower Bounds in Restricted Quantum Models
New lower bounds for:
- QNC and QAC (quantum low-depth circuits)
- QAOA-style circuits under locality constraints
- Quantum read-once branching programs
19. Quantum Nonlocal Games and Hardness Amplification
Hardness amplification in quantum games is being refined via:
- Parallel repetition theorems for quantum settings
- Entanglement-preserving transformations
- Applications to cryptography and verification complexity
20. Conclusion and Open Questions
Recent results in QCT redefine classical boundaries and reveal the immense power of quantum models. Key future directions include:
- Proving unconditional lower bounds
- Resolving QMA vs QPCP
- Connecting quantum learning and verification
- Designing practically verifiable quantum advantage tasks
