Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era

Abstract

Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum heuristics for combinatorial optimization. While QAOA has been shown to perform well on small-scale instances and to provide an asymptotic speedup over state-of-the-art classical algorithms for some problems, fault-tolerance is understood to be required to realize this speedup in practice. The low resource requirements of QAOA make it particularly suitable to benchmark on early fault-tolerant quantum computing (EFTQC) hardware. However, the performance of QAOA depends crucially on the choice of the free parameters in the circuit. The task of setting these parameters is complicated in the EFTQC era by the large overheads, which preclude extensive classical optimization. In this paper, we summarize recent advances in parameter setting in QAOA and show that these advancements make EFTQC experiments with QAOA practically viable.

7 pages, an invited paper at ICCAD 2024 "Exploring Quantum Technologies in Practical Applications" special session

References in corpus (42)

• A variational eigenvalue solver on a quantum processor
• Barren plateaus in quantum neural network training landscapes
• Logical quantum processor based on reconfigurable atom arrays
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Training variational quantum algorithms is NP-hard
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• A Race Track Trapped-Ion Quantum Processor
• Geometry and non-adiabatic response in quantum and classical systems
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Quantum computing for finance
• Anderson localization casts clouds over adiabatic quantum optimization
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Counterdiabaticity and the quantum approximate optimization algorithm
• Performance comparison of optimization methods on variational quantum algorithms
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Early Fault-Tolerant Quantum Computing
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Multistart Methods for Quantum Approximate Optimization
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• Reinforcement Learning assisted Quantum Optimization
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Quantum approximate optimization via learning-based adaptive optimization
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• Policy Gradient based Quantum Approximate Optimization Algorithm
• Quantum Algorithms for Scientific Computing and Approximate Optimization
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• On quantum backpropagation, information reuse, and cheating measurement collapse
• QAOA with $N\cdot p\ge 200$
• Quantum Alternating Operator Ansatz (QAOA) beyond low depth with gradually changing unitaries
• Limitations of variational quantum algorithms: a quantum optimal transport approach

Cited by in corpus (3)

• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Performance of Quantum Approximate Optimization with Quantum Error Detection
• A Cyclic Layerwise QAOA Training