An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation

Abstract

The quantum approximate optimisation algorithm (QAOA) is a hybrid quantum-classical algorithm used to approximately solve combinatorial optimisation problems. It involves multiple iterations of a parameterised ansatz comprising a problem and mixer Hamiltonian, with the parameters being classically optimised. While QAOA can be implemented on NISQ devices, physical limitations can limit circuit depth and decrease performance. To address these limitations, this work introduces the eXpressive QAOA (XQAOA), an overparameterised variant of QAOA that assigns more classical parameters to the ansatz to improve its performance at low depths. XQAOA also introduces an additional Pauli-Y component in the mixer Hamiltonian, allowing the mixer to implement arbitrary unitary transformations on each qubit. To benchmark the performance of XQAOA at unit depth, we derive its closed-form expression for the MaxCut problem and compare it to QAOA, Multi-Angle QAOA (MA-QAOA), a classical-relaxed algorithm, and the state-of-the-art Goemans-Williamson algorithm on a set of unweighted regular graphs with 128 and 256 nodes for degrees ranging from 3 to 10. Our results indicate that at unit depth, XQAOA has benign loss landscapes, allowing it to consistently outperform QAOA, MA-QAOA, and the classical-relaxed algorithm on all graph instances and the Goemans-Williamson algorithm on graph instances with degrees greater than 4. Small-scale simulations also reveal that unit-depth XQAOA surpasses both QAOA and MA-QAOA on all tested depths up to five. Additionally, we find an infinite family of graphs for which XQAOA solves MaxCut exactly and analytically show that for some graphs in this family, XQAOA achieves a much larger approximation ratio than QAOA. Overall, XQAOA is a more viable choice for variational quantum optimisation on NISQ devices, offering competitive performance at low depths.

arXiv comment28 pages, 9 figures

References in corpus (65)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Barren plateaus in quantum neural network training landscapes
• A Quantum Approximate Optimization Algorithm
• Noisy intermediate-scale quantum (NISQ) algorithms
• The Variational Quantum Eigensolver: a review of methods and best practices
• Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• A Convergence Theory for Deep Learning via Over-Parameterization
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Training variational quantum algorithms is NP-hard
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Improving Variational Quantum Optimization using CVaR
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Gradient Descent Finds Global Minima of Deep Neural Networks
• $XY$-mixers: analytical and numerical results for QAOA
• Theory of overparametrization in quantum neural networks
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Reachability Deficits in Quantum Approximate Optimization
• Equivalence of quantum barren plateaus to cost concentration and narrow gorges
• Digitized-counterdiabatic quantum approximate optimization algorithm
• Parameter Concentration in Quantum Approximate Optimization
• Counterdiabaticity and the quantum approximate optimization algorithm
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• MAXCUT QAOA performance guarantees for p >1
• Benchmarking the performance of portfolio optimization with QAOA
• Hybrid quantum-classical algorithms for approximate graph coloring
• Quantum Algorithms for Fixed Qubit Architectures
• On the Universality of the Quantum Approximate Optimization Algorithm
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• Quantum approximate optimization is computationally universal
• How many qubits are needed for quantum computational supremacy?
• Assessing requirements to scale to practical quantum advantage
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Analytic theory for the dynamics of wide quantum neural networks
• Characterizing local noise in QAOA circuits
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Graph neural network initialisation of quantum approximate optimisation
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Evaluation of QAOA based on the approximation ratio of individual samples
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Learning Unitaries by Gradient Descent
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Analytical Framework for Quantum Alternating Operator Ansätze
• Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
• Effects of noise on the overparametrization of quantum neural networks
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• Optimizing Ansatz Design in QAOA for Max-cut
• A Convergence Theory for Over-parameterized Variational Quantum Eigensolvers
• The Quantum Alternating Operator Ansatz for Satisfiability Problems
• Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Connecting the Hamiltonian structure to the QAOA energy and Fourier landscape structure

Cited by in corpus (17)

• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• NISQ Computers: A Path to Quantum Supremacy
• Performance Analysis of Multi-Angle QAOA for p > 1
• Approximating under the Influence of Quantum Noise and Compute Power
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Quantum approximate optimization algorithm with random and subgraph phase operators
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Generalized Probabilistic Approximate Optimization Algorithm
• A Cyclic Layerwise QAOA Training
• Efficient Large-Scale Quantum Optimization via Counterdiabatic Ansatz
• Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
• Light Cone Cancellation for Variational Quantum Eigensolver in Solving Noisy Max-Cut
• Role of overparametrization in quantum approximate optimization
• Decoded Quantum Interferometry Under Noise