Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
arXiv:2504.08577 · doi:10.1103/l5r4-zcqv
Abstract
The Quantum Approximate Optimization Algorithm (QAOA) has been suggested as a promising candidate for the solution of combinatorial optimization problems. Yet, whether - or under what conditions - it may offer an advantage compared to classical algorithms remains to be proven. Using the standard variational form of QAOA requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which constitutes a bottleneck for achieving a potential scaling advantage. The linear-ramp QAOA (LR-QAOA) has been proposed to address this issue, as it relies on only two parameters which have to be optimized. Based on this, we develop a method to estimate suitable values for those parameters through extrapolation, starting from smaller problem sizes (number of qubits) towards larger problem sizes. We apply this method to several use cases such as portfolio optimization, feature selection, clustering and weighted maxcut. From results obtained on a noiseless quantum emulator, we evaluate the quantum runtime scaling for finding the optimal solution and compare it with that of classical methods. In the case of portfolio optimization, we demonstrate superior scaling compared to the classical runtime for the problem sizes of up to qubits that we consider in this work.
14 pages, 15 figures
References in corpus (13)
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Defining and detecting quantum speedup
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
- Quantum annealing initialization of the quantum approximate optimization algorithm
- Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- Benchmarking the performance of portfolio optimization with QAOA
- Classical symmetries and the Quantum Approximate Optimization Algorithm
- Parameter Setting in Quantum Approximate Optimization of Weighted Problems
- Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
- An introduction to variational quantum algorithms for combinatorial optimization problems
- Fair sampling of ground-state configurations of binary optimization problems
- A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz