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.

51 pages, 26 figures

References in corpus (5)

• A Quantum Approximate Optimization Algorithm
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Maximizing the number of independent sets of fixed size in $K_n$-covered graphs