We study a variant of the quantum approximate optimization algorithm [E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028] with a slightly different parametrization and a different objective: rather than looking for a state which approximately solves an optimization problem, our goal is to find a quantum algorithm that, given an instance of the maximum 2-satisfiability problem (MAX-2-SAT), will produce a state with high overlap with the optimal state. Using a machine learning approach, we chose a ``training set'' of instances and optimized the parameters to produce a large overlap for the training set. We then tested these optimized parameters on a larger instance set. As a training set, we used a subset of the hard instances studied by Crosson, Farhi, C. Y.-Y. Lin, H.-H. Lin, and P. Shor (CFLLS) (arXiv:1401.7320). When tested, on the full set, the parameters that we find produce a significantly larger overlap than the optimized annealing times of CFLLS. Testing on other random instances from 20 to 28 bits continues to show improvement over annealing, with the improvement being most notable on the hardest instances. Further tests on instances of MAX-3-SAT also showed improvement on the hardest instances. This algorithm may be a possible application for near-term quantum computers with limited coherence times.
We study a variant of the quantum approximate optimization algorithm [E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028] with a slightly different parametrization and a different objective: rather than looking for a state which approximately solves an optimization problem, our goal is to find a quantum algorithm that, given an instance of the maximum 2-satisfiability problem (MAX-2-SAT), will produce a state with high overlap with the optimal state. Using a machine learning approach, we chose a ``training set'' of instances and optimized the parameters to produce a large overlap for the training set. We then tested these optimized parameters on a larger instance set. As a training set, we used a subset of the hard instances studied by Crosson, Farhi, C. Y.-Y. Lin, H.-H. Lin, and P. Shor (CFLLS) (arXiv:1401.7320). When tested, on the full set, the parameters that we find produce a significantly larger overlap than the optimized annealing times of CFLLS. Testing on other random instances from 20 to 28 bits continues to show improvement over annealing, with the improvement being most notable on the hardest instances. Further tests on instances of MAX-3-SAT also showed improvement on the hardest instances. This algorithm may be a possible application for near-term quantum computers with limited coherence times.
The convergence of machine learning (ML) and quantum computing is quickly becoming a game-changing new frontier in computational science. The most intriguing area of overlap may be quantum optimization, which seeks to reduce the exponentially increasing complexity and computational cost of ML algorithms. As they grow larger and more complicated, traditional optimization methods, particularly in high-dimensional and non-convex space, will inevitably hit performance limits. Quantum optimization is the whole new paradigm that leverages quantum mechanical effects like superposition, entanglement, and tunnelling to explore solution spaces more efficiently. The chapter outlines the theory, practice, and potential of hybrid quantum-classical optimization algorithms for machine learning. The most brilliant research direction in the current NISQ (noisy intermediate-scale quantum) era is mixed systems leveraging classical computing capability augmented by quantum capacity. In such designs, computationally intensive subroutines like optimization for global optima or escape from local minima are left to quantum processors and data preprocessing, iterative refinement, and model testing are performed by classical processors. We start by defining the fundamental principles of quantum computing and acquainting readers with the fundamentals like qubits, quantum gates, and quantum circuits. These are the building blocks for quantum algorithms, which hopefully can be utilized for optimization, for example, the QAOA (quantum approximate optimization algorithm), the VQE (variational quantum Eigensolver), and quantum annealing. They all build to optimize the problems in some way differently: QAOA through parameterized quantum circuits, VQE through approximations of ground states of the Hamiltonians, and quantum annealing through quantum evolution to low-energy solutions. We then form a loop between these quantum algorithms and regular machine learning tasks. Optimization impacts virtually all ML phases, from training neural networks, where one reduces loss functions; feature selection, where one aims to discover the most relevant subset of input variables; and hyperparameter optimization, which often involves expensive search procedures over extremely large combinatorial spaces. Quantum optimization techniques can therefore, in principle, accelerate such procedures through computational complexity reduction and enhancing solutions over challenging landscapes. Realistic simulations and case studies emphasize the degree to which hybrid quantum-classical algorithms have been employed in solving ML problems, that is, QSVMs, quantum-enhanced clustering, and quantum reinforcement learning. Despite their experimental nature, these applications already show encouraging results in terms of improved performance metrics as well as reduction in time-to-solution compared to classical-only solutions. Notwithstanding that, this new field is not bereft of real challenges. Quantum hardware suffers from hard limits on qubit fidelity, decoherence, and scalability in the current times. Furthermore, quantum circuit integration into broad ML pipelines requires novel architectures and software platforms. As a counter to those issues, this chapter surveys recent advances in quantum programming languages, simulators, and hybrid platforms like PennyLane, Qiskit, and TensorFlow Quantum. We conclude by looking to the future possibility that quantum optimization will revolutionize the machine learning landscape. As hardware improves and algorithmic complexity increases, the possibility of quantum-powered learning systems solving hard problems becomes increasingly accessible. From speeding up deep network training to enabling new types of unsupervised learning, quantum optimization holds the potential to recast computational tractability in machine learning. This chapter is an all-encompassing introduction and state-of-the-art work for students, researchers, and practitioners interested in using quantum optimization for practical ML applications. It sets the foundation for understanding how to pursue hybrid approaches (how they may be applied today in the real world and bracing oneself for disruption in the future).
One of the most prominent application areas for quantum computers is solving hard constraint satisfaction and optimization problems. However, detailed analyses of the complexity of standard quantum algorithms have suggested that outperforming classical methods for these problems would require extremely large and powerful quantum computers. The quantum approximate optimization algorithm (QAOA) is designed for near-term quantum computers, yet previous work has shown strong limitations on the ability of QAOA to outperform classical algorithms for optimization problems. Here we instead apply QAOA to hard constraint satisfaction problems, where both classical and quantum algorithms are expected to require exponential time. We analytically characterize the average success probability of QAOA on a constraint satisfaction problem commonly studied using statistical physics methods: random k -SAT at the threshold for satisfiability, as the number of variables n goes to infinity. We complement these theoretical results with numerical experiments on the performance of QAOA for small n , which match the limiting theoretical bounds closely. We then compare QAOA with leading classical solvers. For random 8-SAT, we find that for more than 14 quantum circuit layers, QAOA achieves more efficient scaling than the highest-performance classical solver we tested, WalkSATlm. Our results suggest that near-term quantum algorithms for solving constraint satisfaction problems may outperform their classical counterparts. Published by the American Physical Society 2024
We propose a machine learning based approach to accelerate quantum approximate optimization algorithm (QAOA) implementation which is a promising quantum-classical hybrid algorithm to prove the so-called quantum supremacy. In QAOA, a parametric quantum circuit and a classical optimizer iterates in a closed loop to solve hard combinatorial optimization problems. The performance of QAOA improves with increasing number of stages (depth) in the quantum circuit. However, two new parameters are introduced with each added stage for the classical optimizer increasing the number of optimization loop iterations. We note a correlation among parameters of the lower-depth and the higher-depth QAOA implementations and, exploit it by developing a machine learning model to predict the gate parameters close to the optimal values. As a result, the optimization loop converges in a fewer number of iterations. We choose graph MaxCut problem as a prototype to solve using QAOA. We perform a feature extraction routine using 100 different QAOA instances and develop a training data-set with 13, 860 optimal parameters. We present our analysis for 4 flavors of regression models and 4 flavors of classical optimizers. Finally, we show that the proposed approach can curtail the number of optimization iterations by on average 44.9% (up to 65.7%) from an analysis performed with 264 flavors of graphs.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading approach for solving combinatorial optimization problems on near-term quantum processors. However, finding good variational parameters remains a significant challenge due to the non-convex energy landscape, often resulting in slow convergence and poor solution quality. In this work, we propose a quantum meta-learning framework that trains advanced quantum sequence models to generate effective parameter initialization policies. We investigate four classical or quantum sequence models, including the Quantum Kernel-based Long Short-Term Memory (QK-LSTM), as learned optimizers in a "learning to learn" paradigm. Our numerical experiments on the Max-Cut problem demonstrate that the QK-LSTM optimizer achieves superior performance, obtaining the highest approximation ratios and exhibiting the fastest convergence rate across all tested problem sizes (n=10 to 13). Crucially, the QK-LSTM model achieves perfect parameter transferability by synthesizing a single, fixed set of near-optimal parameters, leading to a remarkable sustained acceleration of convergence even when generalizing to larger problems. This capability, enabled by the compact and expressive power of the quantum kernel architecture, underscores its effectiveness. The QK-LSTM, with only 43 trainable parameters, substantially outperforms the classical LSTM (56 parameters) and other quantum sequence models, establishing a robust pathway toward highly efficient parameter initialization for variational quantum algorithms in the NISQ era.
Abstract The performance of the quantum approximate optimization algorithm is evaluated by using three different measures: the probability of finding the ground state, the energy expectation value, and a ratio closely related to the approximation ratio. The set of problem instances studied consists of weighted MaxCut problems and 2-satisfiability problems. The Ising model representations of the latter possess unique ground states and highly degenerate first excited states. The quantum approximate optimization algorithm is executed on quantum computer simulators and on the IBM Q Experience. Additionally, data obtained from the D-Wave 2000Q quantum annealer are used for comparison, and it is found that the D-Wave machine outperforms the quantum approximate optimization algorithm executed on a simulator. The overall performance of the quantum approximate optimization algorithm is found to strongly depend on the problem instance.
Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.