The prospect of using quantum computers to solve combinatorial optimization problems via the quantum approximate optimization algorithm (QAOA) has attracted considerable interest in recent years. However, a key limitation associated with QAOA is the need to classically optimize over a set of quantum circuit parameters. This classical optimization can have significant associated costs and challenges. Here we provide an expanded description of Lyapunov control-inspired strategies for quantum optimization, as presented in [Magann et al., Phys. Rev. Lett. 129, 250502 (2022)], that do not require any classical optimization effort. Instead, these strategies utilize feedback from qubit measurements to assign values to the quantum circuit parameters in a deterministic manner, such that the combinatorial optimization problem solution improves monotonically with the quantum circuit depth. Numerical analyses are presented that investigate the utility of these strategies towards MaxCut on weighted and unweighted 3-regular graphs, both in ideal implementations and in the presence of measurement noise. We also discuss how how these strategies compare with QAOA and how they may be used to seed QAOA optimizations in order to improve performance for near-term applications, and we explore connections to quantum annealing.
It is hoped that quantum computers will offer advantages over classical computers for combinatorial optimization. Here, we introduce a feedback-based strategy for quantum optimization, where the results of qubit measurements are used to constructively assign values to quantum circuit parameters. We show that this procedure results in an estimate of the combinatorial optimization problem solution that improves monotonically with the depth of the quantum circuit. Importantly, the measurement-based feedback enables approximate solutions to the combinatorial optimization problem without the need for any classical optimization effort, as would be required for the quantum approximate optimization algorithm. We demonstrate this feedback-based protocol on a superconducting quantum processor for the graph-partitioning problem MaxCut, and present a series of numerical analyses that further investigate the protocol's performance.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm used to study NP-hard combinatorial optimization problems. In this work, we focused on optimization strategies for QAOA including circuit depth reduction, parameter parallelization, and hybrid classical feedback mechanisms. We will consider the application of QAOA to different types of NP-hard problems such as Max-Cut and Vehicle Routing Problem (VRP) and discuss the advantages and disadvantages of each in terms of approximation quality and cost of computation. The comparative simulation on the various qubit counts and depth layers points out the limits of scalability and the constraints of hardware on the current Noisy Intermediate-Scale Quantum (NISQ) devices. And also an improved divide-and-conquer strategy is presented in which parameter reusability and gradient-informed initialization are combined to boost convergence rates. The results of the experiment show that it is more efficient and scalable while maintaining the competitive approximation performance compared to the baseline QAOA. The experimental validation focuses on representative small-size instances, while the proposed framework provides extensions for scalable implementations. Ultimately, this work is a step towards the realization of efficient, hardware-aware, and scalable optimization strategies, thus opening up the practical deployment of QAOA on the quantum systems of the next few years.
The transition from theoretical quantum computing to practical real-world applications heavily relies onhybrid quantum-classical architectures designed for NoisyIntermediate-Scale Quantum (NISQ) devices. Among these approaches, the Quantum Approximate Optimization Algorithm(QAOA) is a prominent strategy for addressing complex combinatorial optimization challenges, such as the NP-hard MaxCut problem. Instead of performing the entire computationon a quantum processor, QAOA utilizes a quantum circuit toevaluate a parameterized cost function, whereas a classical optimizer refines the parameters iteratively. This study presentsa rigorous empirical evaluation comparing the performanceof QAOA against established classical solvers on small-scaleMax-Cut instances. All experiments were implemented andexecuted using Python (Qiskit Aer) on a state-vector simulator.Using Erdős–Rényi random graphs and regular graphs with4 to 20 nodes, we benchmark QAOA at depths p = 2 andp = 3 against simulated annealing, the Goemans–WilliamsonSDP-based algorithm, and a linear-time greedy heuristic. Ourexperimental results demonstrate that low-depth QAOA implementations exhibit severe performance degradation, prohibitive computational overhead (O(2^n) scaling), and low convergencerates compared to mature classical algorithms. At 20 nodes,QAOA (p = 2) achieves only a 0.467 approximation ratio versus0.856 for Goemans–Williamson, with a 210× runtime slowdownover greedy heuristics
Combinatorial optimization problems are one of the areas where near-term noisy quantum computers may have practical advantage against classical computers. Recently, a feedback-based quantum optimization algorithm has been proposed by Magann , . The method explicitly determines quantum circuit parameters by feeding back measurement results thus avoids classical parameter optimization that is known to cause significant trouble in quantum approximate optimization algorithm, the well-studied near-term algorithm. Meanwhile, a significant drawback of the feedback-based quantum optimization is that it requires deep circuits, rendering the method unsuitable to noisy quantum devices. In this study we propose a feedback law for parameter determination by introducing the second-order approximation with respect to time interval, a hyperparameter in the feedback-based quantum optimization. This allows one to take larger time interval, leading to acceleration of convergence to solutions. In numerical simulations on the maximum cut problem we demonstrate that our proposal significantly reduces circuit depth, with its linear scaling with the problem size smaller by more than an order of magnitude. We expect that the feedback law proposed in this work may pave the way for feedback-based quantum optimization with near-term noisy quantum computers.
Farhi et al. recently proposed a class of quantum algorithms, the quantum approximate optimization algorithm (QAOA), for approximately solving combinatorial optimization problems (E. Farhi et al., arXiv:1411.4028; arXiv:1412.6062; arXiv:1602.07674). A level-
p QAOA circuit consists of
p steps; in each step a classical Hamiltonian, derived from the cost function, is applied followed by a mixing Hamiltonian. The
2p times for which these two Hamiltonians are applied are the parameters of the algorithm, which are to be optimized classically for the best performance. As
p increases, parameter optimization becomes inefficient due to the curse of dimensionality. The success of the QAOA approach will depend, in part, on finding effective parameter-setting strategies. Here we analytically and numerically study parameter setting for the QAOA applied to MaxCut. For the level-1 QAOA, we derive an analytical expression for a general graph. In principle, expressions for higher
p could be derived, but the number of terms quickly becomes prohibitive. For a special case of MaxCut, the ``ring of disagrees,'' or the one-dimensional antiferromagnetic ring, we provide an analysis for an arbitrarily high level. Using a fermionic representation, the evolution of the system under the QAOA translates into quantum control of an ensemble of independent spins. This treatment enables us to obtain analytical expressions for the performance of the QAOA for any
p. It also greatly simplifies the numerical search for the optimal values of the parameters. By exploring symmetries, we identify a lower-dimensional submanifold of interest; the search effort can be accordingly reduced. This analysis also explains an observed symmetry in the optimal parameter values. Further, we numerically investigate the parameter landscape and show that it is a simple one in the sense of having no local optima.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.