Structured variational quantum algorithms such as the Quantum Approximate Optimisation Algorithm (QAOA) have emerged as leading candidates for exploiting advantages of near-term quantum hardware. They interlace classical computation, in particular optimisation of variational parameters, with quantum-specific routines, and combine problem-specific advantages -- sometimes even provable -- with adaptability to the constraints of noisy, intermediate-scale quantum (NISQ) devices. While circuit depth can be parametrically increased and is known to improve performance in an ideal (noiseless) setting, on realistic hardware greater depth exacerbates noise: The overall quality of results depends critically on both, variational parameters and circuit depth. Although identifying optimal parameters is NP-hard, prior work has suggested that they may exhibit regular, predictable patterns for increasingly deep circuits and depending on the studied class of problems. In this work, we systematically investigate the role of classical parameters in QAOA performance through extensive numerical simulations and suggest a simple, yet effective heuristic scheme to find good parameters for low-depth circuits. Our results demonstrate that: (i) high-quality parameters often deviate substantially from expected patterns; (ii) QAOA performance becomes progressively less sensitive to specific parameter choices as depth increases; and (iii) iterative component-wise fixing performs on par with, and at shallow depth may even outperform, several established parameter-selection strategies. We identify conditions under which structured parameter patterns emerge, and when deviations from the patterns warrant further consideration. These insights for low-depth circuits may inform more robust pathways to harnessing QAOA in realistic quantum computing scenarios.
Structured variational quantum algorithms such as the Quantum Approximate Optimisation Algorithm (QAOA) have emerged as leading candidates for exploiting advantages of near-term quantum hardware. They interlace classical computation, in particular optimisation of variational parameters, with quantum-specific routines, and combine problem-specific advantages -- sometimes even provable -- with adaptability to the constraints of noisy, intermediate-scale quantum (NISQ) devices. While circuit depth can be parametrically increased and is known to improve performance in an ideal (noiseless) setting, on realistic hardware greater depth exacerbates noise: The overall quality of results depends critically on both, variational parameters and circuit depth. Although identifying optimal parameters is NP-hard, prior work has suggested that they may exhibit regular, predictable patterns for increasingly deep circuits and depending on the studied class of problems. In this work, we systematically investigate the role of classical parameters in QAOA performance through extensive numerical simulations and suggest a simple, yet effective heuristic scheme to find good parameters for low-depth circuits. Our results demonstrate that: (i) high-quality parameters often deviate substantially from expected patterns; (ii) QAOA performance becomes progressively less sensitive to specific parameter choices as depth increases; and (iii) iterative component-wise fixing performs on par with, and at shallow depth may even outperform, several established parameter-selection strategies. We identify conditions under which structured parameter patterns emerge, and when deviations from the patterns warrant further consideration. These insights for low-depth circuits may inform more robust pathways to harnessing QAOA in realistic quantum computing scenarios.
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.
The quantum approximate optimization algorithm (QAOA) is known for its capability and universality in solving combinatorial optimization problems on near-term quantum devices. The results yielded by QAOA depend strongly on its initial variational parameters. Hence, parameter selection for QAOA becomes an active area of research, as bad initialization might deteriorate the quality of the results, especially at great circuit depths. We first discuss the patterns of optimal parameters in QAOA in two directions: the angle index and the circuit depth. Then, we discuss the symmetries and periodicity of the expectation that is used to determine the bounds of the search space. Based on the patterns in optimal parameters and the bounds restriction, we propose a strategy that predicts the new initial parameters by taking the difference between the previous optimal parameters. Unlike most other strategies, the strategy we propose does not require multiple trials to ensure success. It only requires one prediction when progressing to the next depth. We compare this strategy with our previously proposed strategy and the layerwise strategy for solving the Max-cut problem in terms of the approximation ratio and the optimization cost. We also address the non-optimality in previous parameters, which is seldom discussed in other works despite its importance in explaining the behavior of variational quantum algorithms.
The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve combinatorial optimization problems in near-term gate-based noisy quantum devices. In QAOA, the objective is a function of the quantum state, which itself is a function of the gate parameters of a multi-level parameterized quantum circuit (PQC). A classical optimizer varies the continuous gate parameters to generate distributions (quantum state) with significant support to the optimal solution. Even at the lowest circuit depth, QAOA offers non-trivial provable performance guarantee which is expected to increase with the circuit depth. However, the existing analysis fails to consider non-idealities in the qubit quality i.e., short lifetime and imperfect gate operations in realistic quantum hardware. In this article, we investigate the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analyses indicate that the optimal number of stages (p-value) for any QAOA instance is limited by the noise characteristics (gate error, coherence time, etc.) of the target hardware as opposed to the current perception that higher-depth QAOA will provide monotonically better performance for a given problem compared to the low-depth implementations.
Abstract The quantum approximate optimisation algorithm (QAOA) is a hybrid quantum–classical algorithm used to approximately solve combinatorial optimisation problems. It involves multiple iterations of a parameterised ansatz that consists of a problem and mixer Hamiltonian, with the parameters being classically optimised. While QAOA can be implemented on near-term quantum hardware, physical limitations such as gate noise, restricted qubit connectivity, and state-preparation-and-measurement (SPAM) errors can limit circuit depth and decrease performance. To address these limitations, this work introduces the eXpressive QAOA (XQAOA), an overparameterised variant of QAOA that assigns more classical parameters to the ansatz to improve its performance at low depths. XQAOA also introduces an additional Pauli-Y component in the mixer Hamiltonian, allowing the mixer to implement arbitrary unitary transformations on each qubit. To benchmark the performance of XQAOA at unit depth, we derive its closed-form expression for the MaxCut problem and compare it to QAOA, Multi-Angle QAOA (MA-QAOA) (Herrman et al 2022 Sci. Rep. 12 6781), a classical-relaxed algorithm, and the state-of-the-art Goemans–Williamson algorithm on a set of unweighted regular graphs with 128 and 256 nodes for degrees ranging from 3 to 10. Our results indicate that at unit depth, XQAOA has benign loss landscapes with local minima concentrated near the global optimum, allowing it to consistently outperform QAOA, MA-QAOA, and the classical-relaxed algorithm on all graph instances and the Goemans–Williamson algorithm on graph instances with degrees greater than 4. Small-scale simulations also reveal that unit-depth XQAOA invariably surpasses both QAOA and MA-QAOA on all tested depths up to five. Additionally, we find an infinite family of graphs for which XQAOA solves MaxCut exactly and analytically show that for some graphs in this family, special cases of XQAOA are capable of achieving a much larger approximation ratio than QAOA. Overall, XQAOA is a more viable choice for variational quantum optimisation on near-term quantum devices, offering competitive performance at low depths.
The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm for Near-term Intermediate-Scale Quantum computers (NISQ) providing approximate solutions for combinatorial optimization problems. The QAOA utilizes a quantum-classical loop, consisting of a quantum ansatz and a classical optimizer, to minimize some cost function, computed on the quantum device. This paper presents an investigation into the impact of realistic noise on the classical optimizer and the determination of optimal circuit depth for the Quantum Approximate Optimization Algorithm (QAOA) in the presence of noise. We find that, while there is no significant difference in the performance of classical optimizers in a state vector simulation, the Adam and AMSGrad optimizers perform best in the presence of shot noise. Under the conditions of real noise, the SPSA optimizer, along with ADAM and AMSGrad, emerge as the top performers. The study also reveals that the quality of solutions to some 5 qubit minimum vertex cover problems increases for up to around six layers in the QAOA circuit, after which it begins to decline. This analysis shows that increasing the number of layers in the QAOA in an attempt to increase accuracy may not work well in a noisy device.
The quantum approximate optimization algorithm (QAOA) has numerous promising applications in solving the combinatorial optimization problems on near-term Noisy Intermediate Scalable Quantum (NISQ) devices. QAOA has a quantum-classical hybrid structure. Its quantum part consists of a parameterized alternating operator ansatz, and its classical part comprises an optimization algorithm, which optimizes the parameters to maximize the expectation value of the problem Hamiltonian. This expectation value depends highly on the parameters, this implies that a set of good parameters leads to an accurate solution. However, at large circuit depth of QAOA, it is difficult to achieve global optimization due to the multiple occurrences of local minima or maxima. In this paper, we propose a parameters fixing strategy which gives high approximation ratio on average, even at large circuit depths, by initializing QAOA with the optimal parameters obtained from the previous depths. We test our strategy on the Max-cut problem of certain classes of graphs such as the 3-regular graphs and the Erdös-Rényi graphs.