Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits

Abstract

We embed 1-layer QAOA circuits into the larger class of parameterized Instantaneous Quantum Polynomial circuits to produce an improved variational quantum algorithm for solving combinatorial optimization problems. The use of analytic expressions to find optimal parameters classically makes our protocol robust against barren plateaus and hardware noise. The average overlap with the ground state scales as $\mathcal{O}(2^{-0.31N})$ with the number of qubits $N$ for random Sherrington-Kirkpatrick (SK) Hamiltonians of up to 29 qubits, a polynomial improvement over 1-layer QAOA. Additionally, we observe that performing variational imaginary time evolution on the manifold approximates low-temperature pseudo-Boltzmann states. Our protocol outperforms 1-layer QAOA on the recently released Quantinuum H2 trapped-ion quantum hardware and emulator, where we obtain an average approximation ratio of $0.985$ across 312 random SK instances of 7 to 32 qubits, from which almost $44\%$ are solved optimally using 4 to 1208 shots per instance.

arXiv commentreferences added, new experimental results, new appendix

References in corpus (32)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Variational ansatz-based quantum simulation of imaginary time evolution
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Theory of variational quantum simulation
• Training variational quantum algorithms is NP-hard
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Average-case complexity versus approximate simulation of commuting quantum computations
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Improving Variational Quantum Optimization using CVaR
• Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Instantaneous Quantum Computation
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Filtering variational quantum algorithms for combinatorial optimization
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• A case study of variational quantum algorithms for a job shop scheduling problem
• Ground state approximation for strongly interacting systems in arbitrary dimension
• Using models to improve optimizers for variational quantum algorithms
• The Sherrington-Kirkpatrick model: an overview
• Quantum variational optimization: The role of entanglement and problem hardness
• Progress toward favorable landscapes in quantum combinatorial optimization
• Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
• Renormalization algorithm with graph enhancement
• A variational method based on weighted graph states
• A Variational Ansatz for the Ground State of the Quantum Sherrington-Kirkpatrick Model
• Random circuits by measurements on weighted graph states
• Tensor network methods with graph enhancement

Cited by in corpus (5)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem