Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem
Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew P. DeCross, Dylan Herman, Niraj Kumar, Jeffrey M. Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan Dreiling, John Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, Marco Pistoia
The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tackle classically intractable problems remains unclear. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem, which is classically intractable even for moderately sized instances. We perform noiseless simulations with up to 40 qubits and observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which are the state-of-the-art exact solvers for LABS. The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem. We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors. Our results provide evidence for the utility of QAOA as an algorithmic component that enables quantum speedups.
The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tackle classically intractable problems remains unclear. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem, which is classically intractable even for moderately sized instances. We perform noiseless simulations with up to 40 qubits and observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which are the state-of-the-art exact solvers for LABS. The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem. We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors. Our results provide evidence for the utility of QAOA as an algorithmic component that enables quantum speedups.
The quantum approximate optimization algorithm (QAOA) is a quantum heuristic for combinatorial optimization that has been demonstrated to scale better than state-of-the-art classical solvers for some problems. For a given problem instance, QAOA performance depends crucially on the choice of the parameters. While average-case optimal parameters are available in many cases, meaningful performance gains can be obtained by fine-tuning these parameters for a given instance. This task is especially challenging, however, when the number of circuit executions (shots) is limited. In this work, we develop an end-to-end protocol that combines multiple parameter settings and fine-tuning techniques. We use large-scale numerical experiments to optimize the protocol for the shot-limited setting and observe that optimizers with the simplest internal model (linear) perform best. We implement the optimized pipeline on a trapped-ion processor using up to 32 qubits and 5 QAOA layers, and we demonstrate that the pipeline is robust to small amounts of hardware noise. To the best of our knowledge, these are the largest demonstrations of QAOA parameter fine-tuning on a trapped-ion processor in terms of two-qubit gate count.
Abstract The quantum approximate optimization algorithm (QAOA) is a hybrid quantum–classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors it is a promising candidate likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. In particular for three-regular random graphs, QAOA performance shows improvement by up to two orders of magnitude compared to previous estimates, strongly reducing the performance gap with classical alternatives. This was possible by reducing the number of function evaluations per iteration and optimizing the variational parameters on small graph instances and transferring to large via training. Because QAOA’s performance guarantees are only known for limited applications and contexts, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.
Solving optimization problems is critical across many research domains, but the high dimensionality of parameter spaces often poses significant challenges. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for accelerating optimization in the Noisy Intermediate-Scale Quantum (NISQ) era by leveraging both classical and quantum computational resources. However, its performance can vary depending on the underlying quantum hardware architecture. In this work, we evaluate the performance of QAOA on different quantum hardware platforms, specifically, superconducting transmon qubits and trapped-ion qubits, targetting real-world optimization problems formulated as fully connected Quadratic Unconstrained Binary Optimization (QUBO) instances. We evaluate both the solution quality and time-to-solution using dense QUBO matrices. Furthermore, we show that large-scale problems, such as a 100-bit QUBO instance, can be effectively tackled by integrating quantum computing with high-performance computing (HPC) resources. This study provides practical insights into the strengths and limitations of different qubit technologies and advances the application of quantum computing in solving real-world optimization problems.
Abstract The Quantum approximate optimization algorithm (QAOA) constitutes one of the often mentioned candidates expected to yield a quantum boost in the era of near-term quantum computing. In practice, quantum optimization will have to compete with cheaper classical heuristic methods, which have the advantage of decades of empirical domain-specific enhancements. Consequently, to achieve optimal performance we will face the issue of algorithm selection, well-studied in practical computing. Here we introduce this problem to the quantum optimization domain. Specifically, we study the problem of detecting those problem instances of where QAOA is most likely to yield an advantage over a conventional algorithm. As our case study, we compare QAOA against the well-understood approximation algorithm of Goemans and Williamson on the Max-Cut problem. As exactly predicting the performance of algorithms can be intractable, we utilize machine learning (ML) to identify when to resort to the quantum algorithm. We achieve cross-validated accuracy well over 96%, which would yield a substantial practical advantage. In the process, we highlight a number of features of instances rendering them better suited for QAOA. While we work with simulated idealised algorithms, the flexibility of ML methods we employed provides confidence that our methods will be equally applicable to broader classes of classical heuristics, and to QAOA running on real-world noisy devices.
Quantum computers are expected to offer advantages in solving optimization problems challenging for classical computers. Quadratic Unconstrained Binary Optimization (QUBO) problems represent an important class of problems with relevance in finance and logistics. The Quantum Approximate Optimization Algorithm (QAOA) is a prominent candidate for solving QUBO problems on near-term quantum devices. In this paper, we evaluate the performance of both the standard QAOA and the adaptive derivative assembled problem tailored QAOA (ADAPT-QAOA) to solve QUBO problems of varying sizes and hardnesses for financial feature selection problems. Our main observation is that ADAPT-QAOA achieves substantially higher approximation ratios than standard QAOA for harder feature-selection problems (α = 0.6) with statistically significant improvements observed for problem sizes n = 6 and 14. However, the standard QAOA remains competitive for simpler problems. Additionally, we evaluate the practical feasibility and limitations of QAOA through a hardware-aware scaling analysis based on the real-device calibration data for various hardware platforms. We estimate that standard QAOA implementation on superconducting quantum computers provides a shorter time-to-solution compared to trapped-ion devices, while trapped-ion devices yield more favorable error rates. Our findings provide a comprehensive overview of the challenges, trade-offs, and strategies for deploying QAOA-based methods on near-term quantum hardware.
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 with 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 has been proposed to address this issue, as it relies on only two parameters that 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) toward 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 with the classical runtime for the problem sizes of up to 28 qubits that we consider in this work.