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.

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

References in corpus (23)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A Quantum Approximate Optimization Algorithm
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• 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
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Graph neural network initialisation of quantum approximate optimisation
• 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
• 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
• 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