Improving the Quantum Approximate Optimization Algorithm with postselection

Abstract

Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. In this work, we consider a well-studied quantum algorithm for combinatorial optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We explore the idea of improving the solutions returned by the simplest version of the algorithm (depth-1 QAOA) using a form of postselection that can be efficiently simulated by state preparation. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable. Numerical experiments on large problem instances (beyond classical simulatability) complement and support our bounds. We also consider a distinct technique: local updates, which can be applied not only to QAOA but any optimization algorithm. In the case of QAOA, the resulting improvement can be sharply quantified theoretically for large problem instances and in absence of postselection. Combining postselection and local updates, the theory is no longer tractable but numerical evidence suggests that improvements from both methods can be combined.

arXiv comment51 pages, 26 figures

References in corpus (20)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Approximate Optimization Algorithm
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Extremal Cuts of Sparse Random Graphs
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Local algorithms for independent sets are half-optimal
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Suboptimality of local algorithms for a class of max-cut problems
• Classical and Quantum Bounded Depth Approximation Algorithms
• Low depth mechanisms for quantum optimization
• Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design
• Maximizing the number of independent sets of fixed size in $K_n$-covered graphs

Cited by in corpus (1)

• Graph neural network initialisation of quantum approximate optimisation