Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation

Abstract

The Quantum Approximate Optimisation Algorithm (QAOA) is a widely studied quantum-classical iterative heuristic for combinatorial optimisation. While QAOA targets problems in complexity class NP, the classical optimisation procedure required in every iteration is itself known to be \NP-hard. Still, advantage over classical approaches is suspected for certain scenarios, but nature and origin of its computational power are not yet satisfactorily understood. By introducing means of efficiently and accurately approximating the QAOA optimisation landscape from solution space structures, we derive a new algorithmic variant of unit-depth QAOA for two-level Hamiltonians (including all problems in NP): Instead of performing an iterative quantum-classical computation for each input instance, our non-iterative method is based on a quantum circuit that is instance-independent, but problem-specific. It matches or outperforms unit-depth QAOA for key combinatorial problems, despite reduced computational effort. Our approach is based on proving a long-standing conjecture regarding instance-independent structures in QAOA. By ensuring generality, we link existing empirical observations on QAOA parameter clustering to established approaches in theoretical computer science, and provide a sound foundation for understanding the link between structural properties of solution spaces and quantum optimisation.

arXiv comment20 pages, 13 figures, to be submitted Replacement: added additional reference to "Related Work"

References in corpus (50)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Variational Quantum Algorithms
• Ising formulations of many NP problems
• A Quantum Approximate Optimization Algorithm
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum algorithms: an overview
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Training variational quantum algorithms is NP-hard
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• 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
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• $XY$-mixers: analytical and numerical results for QAOA
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Benchmarking the Quantum Approximate Optimization Algorithm
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Parameter Concentration in Quantum Approximate Optimization
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Training A Quantum Optimizer
• On the Universality of the Quantum Approximate Optimization Algorithm
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Graph neural network initialisation of quantum approximate optimisation
• Progress toward favorable landscapes in quantum combinatorial optimization
• 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
• Quantum-Informed Recursive Optimization Algorithms
• GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
• QAOA Performance in Noisy Devices: The Effect of Classical Optimizers and Ansatz Depth
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Comparison of QAOA with Quantum and Simulated Annealing
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Quantum Annealing-Based Software Components: An Experimental Case Study with SAT Solving
• Quantum Computing Techniques for Multi-Knapsack Problems
• Practical Verification of Quantum Properties in Quantum Approximate Optimization Runs
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Polynomial Reduction Methods and their Impact on QAOA Circuits
• Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations
• Approximating under the Influence of Quantum Noise and Compute Power
• Guided-SPSA: Simultaneous Perturbation Stochastic Approximation assisted by the Parameter Shift Rule
• Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
• Sampling binary sparse coding QUBO models using a spiking neuromorphic processor