Complexity Barriers to State Preparation in Quantum Approximate Optimization

arXiv:2609.31520 · quant-ph, cs.CC · Submitted 2026-09-25 · Read on arXiv

quant-ph, cs.CC

Submitted: 2026-09-25

Updated: 2026-09-25

Terminology

• BQP — 24× in this paper · explained in 2 episodes
• Combinatorial Optimization — 7× in this paper · explained in 2 episodes
• Benchmarking — 5× in this paper · explained in 3 episodes
• Accuracy — 3× in this paper · explained in 1 episode
• Benchmark — 3× in this paper · explained in 2 episodes
• Entanglement — 3× in this paper · explained in 3 episodes
• Trace — 3× in this paper · explained in 2 episodes
• Adiabatic Evolution — 2× in this paper · explained in 2 episodes
• Loss Function — 2× in this paper · explained in 2 episodes
• Objective Function — 2× in this paper · explained in 2 episodes
• Calibration — 1× in this paper · explained in 7 episodes
• Consistency — 1× in this paper · explained in 3 episodes
• Decode — 1× in this paper · explained in 2 episodes
• Decoded Quantum Interferometry (DQI) — 1× in this paper · explained in 2 episodes
• Generalization — 1× in this paper · explained in 13 episodes

Sources

• Challenges and Opportunities in Quantum Optimization
• A Quantum Approximate Optimization Algorithm
• Quantum Computation by Adiabatic Evolution
• Approximate Solutions of Combinatorial Problems via Quantum Relaxations
• Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions
• Complexity Amplification from Compression in Quantum Random Access Optimization
• No Free Compression in Quantum Relaxations for Optimization
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Quantum Max-Cut is NP hard to approximate
• Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT
• Evaluating QAOA expectation values can be as hard as counting optimal solutions
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms
• Quantum-Informed Recursive Optimization Algorithms
• Quantum DPLL and Generalized Constraints in Iterative Quantum Algorithms
• A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization
• Warm-starting quantum optimization
• Iterative warm-start optimization with quantum imaginary time evolution

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity