Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems

Abstract

We report on the energy-expectation-value landscapes produced by the single-layer ($p=1$) Quantum Approximate Optimization Algorithm (QAOA) when being used to solve Ising problems. The landscapes are obtained using an analytical formula that we derive. The formula allows us to predict the landscape for any given Ising problem instance and consequently predict the optimal QAOA parameters for heuristically solving that instance using the single-layer QAOA. We have validated our analytical formula by showing that it accurately reproduces the landscapes published in recent experimental reports. We then applied our methods to address the question: how well is the single-layer QAOA able to solve large benchmark problem instances? We used our analytical formula to calculate the optimal energy-expectation values for benchmark MAX-CUT problems containing up to $7000$ vertices and $41459$ edges. We also calculated the optimal energy expectations for general Ising problems with up to $100000$ vertices and $150000$ edges. Our results provide an estimate for how well the single-layer QAOA may work when run on a quantum computer with thousands of qubits. In addition to providing performance estimates when optimal angles are used, we are able to use our analytical results to investigate the difficulties one may encounter when running the QAOA in practice for different classes of Ising instances. We find that depending on the parameters of the Ising Hamiltonian, the expectation-value landscapes can be rather complex, with sharp features that necessitate highly accurate rotation gates in order for the QAOA to be run optimally on quantum hardware. We also present analytical results that explain some of the qualitative landscape features that are observed numerically.

24 pages, 11 figures

References in corpus (3)

• A Quantum Approximate Optimization Algorithm
• Hybrid quantum-classical algorithms for approximate graph coloring
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances

Cited by in corpus (22)

• Challenges and Opportunities in Quantum Optimization
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Quantum-Informed Recursive Optimization Algorithms
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
• Analytical Framework for Quantum Alternating Operator Ansätze
• Reinforcement Learning Assisted Recursive QAOA
• Provable bounds for noise-free expectation values computed from noisy samples
• Lie-algebraic classical simulations for quantum computing
• ON-OFF Neuromorphic ISING Machines using Fowler-Nordheim Annealers
• Performance Analysis of Multi-Angle QAOA for p > 1
• Deep recurrent networks predicting the gap evolution in adiabatic quantum computing
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• Quantum approximate optimization algorithm with random and subgraph phase operators
• Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
• Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Interference and Measurement: Changing amplitude phase information to amplitude magnitude information