Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2209.03824 · IEEE Transactions on Quantum Engineering

Bayesian Optimization for QAOA

Simone Tibaldi, Davide Vodola, Edoardo Tignone, Elisa Ercolessi

Published Jan 1, 2023• 18 citations
arXivHTMLPDF

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) adopts a hybrid quantum-classical approach to find approximate solutions to variational optimization problems. In fact, it relies on a classical subroutine to optimize the parameters of a quantum circuit. In this work we present a Bayesian optimization procedure to fulfil this optimization task, and we investigate its performance in comparison with other global optimizers. We show that our approach allows for a significant reduction in the number of calls to the quantum circuit, which is typically the most expensive part of the QAOA. We demonstrate that our method works well also in the regime of slow circuit repetition rates, and that few measurements of the quantum ansatz would already suffice to achieve a good estimate of the energy. In addition, we study the performance of our method in the presence of noise at gate level, and we find that for low circuit depths it is robust against noise. Our results suggest that the method proposed here is a promising framework to leverage the hybrid nature of QAOA on the noisy intermediate-scale quantum devices.

DOI
10.1109/tqe.2023.3325167

Related papers

Trainability Analysis of Quantum Optimization Algorithms from a Bayesian Lens

Yanqi Song, Yusen Wu, Su‐Juan Qin +3 more

The Quantum Approximate Optimization Algorithm (QAOA) is an extensively studied variational quantum algorithm utilized for solving optimization problems on near-term quantum devices. A significant focus is placed on determining the effectiveness of training the $n$-qubit QAOA circuit, i.e., whether the optimization error can converge to a constant level as the number of optimization iterations scales polynomially with the number of qubits. In realistic scenarios, the landscape of the corresponding QAOA objective function is generally non-convex and contains numerous local optima. In this work, motivated by the favorable performance of Bayesian optimization in handling non-convex functions, we theoretically investigate the trainability of the QAOA circuit through the lens of the Bayesian approach. This lens considers the corresponding QAOA objective function as a sample drawn from a specific Gaussian process. Specifically, we focus on two scenarios: the noiseless QAOA circuit and the noisy QAOA circuit subjected to local Pauli channels. Our first result demonstrates that the noiseless QAOA circuit with a depth of $\tilde{\mathcal{O}}\left(\sqrt{\log n}\right)$ can be trained efficiently, based on the widely accepted assumption that either the left or right slice of each block in the circuit forms a local 1-design. Furthermore, we show that if each quantum gate is affected by a $q$-strength local Pauli channel with the noise strength range of $1/{\rm poly} (n)$ to 0.1, the noisy QAOA circuit with a depth of $\mathcal{O}\left(\log n/\log(1/q)\right)$ can also be trained efficiently. Our results offer valuable insights into the theoretical performance of quantum optimization algorithms in the noisy intermediate-scale quantum era.

arXiv:2310.06270•Oct 10, 2023•1 citation

Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits

Mahabubul Alam, Abdullah Ash Saki, Swaroop Ghosh

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.

arXiv:1907.09631•Jul 13, 2019•33 citations

Design-Space Exploration of Quantum Approximate Optimization Algorithm under Noise

Mahabubul Alam, Abdullah Ash Saki, Swaroop Ghosh

Quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve NP-hard problems in near-term gate-based noisy quantum devices. In QAOA, the gate parameters of a parameterized quantum circuit (PQC) are varied by a classical optimizer to generate a quantum state with a significant support to the optimal solution. The existing analysis fails to consider nonidealities in the qubit quality i.e., short lifetime and imperfect gate operations in a realistic quantum hardware. In this article, we study the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analysis indicates that QAOA performance is noise-sensitive (especially higher-depth QAOA instances). Therefore, the optimal number of stages (p-value) for any QAOA instance is limited by the noise in the target hardware as opposed to the current perception that QAOA will provide monotonically better performance with higher-depth. We show that the two-qubit gate error has to be decreased by more than 75% of the current state-of-the-art levels to attain a performance within 10% of the maximum value for the lowest-depth QAOA.

Custom Integrated Circuits Conference•Mar 1, 2020•28 citations

The effect of classical optimizers and Ansatz depth on QAOA performance in noisy devices

Aidan Pellow-Jarman, Shane McFarthing, Ilya Sinayskiy +3 more

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.

arXiv:2307.10149•Scientific Reports•Jul 11, 2024•39 citations

Evaluating Quantum Approximate Optimization Algorithm: A Case Study

Ruslan Shaydulin, Yuri Alexeev

Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum algorithms for the Noisy Intermediate-Scale Quantum (NISQ) era. Quantifying the performance of QAOA in the near-term regime is of utmost importance. We perform a large-scale numerical study of the approximation ratios attainable by QAOA is the low-to medium-depth regime. To find good QAOA parameters we perform 990 million 10-qubit QAOA circuit evaluations. We find that the approximation ratio increases only marginally as the depth is increased, and the gains are offset by the increasing complexity of optimizing variational parameters. We observe a high variation in approximation ratios attained by QAOA, including high variations within the same class of problem instances. We observe that the difference in approximation ratios between problem instances increases as the similarity between instances decreases. We find that optimal QAOA parameters concentrate for instances in out benchmark, confirming the previous findings for a different class of problems.

arXiv:1910.04881•International Green and Sustainable Computing Conference•Oct 1, 2019•55 citations

Automatic depth optimization for a quantum approximate optimization algorithm

Yu Pan, Yifan Tong, Yi Yang

Quantum approximate optimization algorithm (QAOA) is a hybrid algorithm whose control parameters are classically optimized. In addition to the variational parameters, the right choice of hyperparameter is crucial for improving the performance of any optimization model. Control depth, or the number of variational parameters, is considered as the most important hyperparameter for QAOA. In this paper we investigate the control depth selection with an automatic algorithm based on proximal gradient descent. The performances of the automatic algorithm are demonstrated on seven-node and ten-node max-cut problems, which show that the control depth can be significantly reduced during the iteration whereas achieving an sufficient level of optimization accuracy. With theoretical convergence guarantee, the proposed algorithm can be used as an efficient tool for choosing the appropriate control depth as a replacement of random search or empirical rules. Moreover, the reduction of control depth will induce a significant reduction in the number of quantum gates in circuit, which improves the applicability of QAOA on noisy intermediate-scale quantum devices.

arXiv:2206.14412•Physical Review A•Mar 21, 2022•11 citations
The Quantum Approximate Optimization Algorithm (QAOA) adopts a hybrid quantum-classical approach to find approximate solutions to variational optimization problems. In fact, it relies on a classical subroutine to optimize the parameters of a quantum circuit. In this work we present a Bayesian optimization procedure to fulfil this optimization task, and we investigate its performance in comparison with other global optimizers. We show that our approach allows for a significant reduction in the number of calls to the quantum circuit, which is typically the most expensive part of the QAOA. We demonstrate that our method works well also in the regime of slow circuit repetition rates, and that few measurements of the quantum ansatz would already suffice to achieve a good estimate of the energy. In addition, we study the performance of our method in the presence of noise at gate level, and we find that for low circuit depths it is robust against noise. Our results suggest that the method proposed here is a promising framework to leverage the hybrid nature of QAOA on the noisy intermediate-scale quantum devices.
The Quantum Approximate Optimization Algorithm (QAOA) is an extensively studied variational quantum algorithm utilized for solving optimization problems on near-term quantum devices. A significant focus is placed on determining the effectiveness of training the nnn-qubit QAOA circuit, i.e., whether the optimization error can converge to a constant level as the number of optimization iterations scales polynomially with the number of qubits. In realistic scenarios, the landscape of the corresponding QAOA objective function is generally non-convex and contains numerous local optima. In this work, motivated by the favorable performance of Bayesian optimization in handling non-convex functions, we theoretically investigate the trainability of the QAOA circuit through the lens of the Bayesian approach. This lens considers the corresponding QAOA objective function as a sample drawn from a specific Gaussian process. Specifically, we focus on two scenarios: the noiseless QAOA circuit and the noisy QAOA circuit subjected to local Pauli channels. Our first result demonstrates that the noiseless QAOA circuit with a depth of O~(log⁡n)\tilde{\mathcal{O}}\left(\sqrt{\log n}\right)O~(logn​) can be trained efficiently, based on the widely accepted assumption that either the left or right slice of each block in the circuit forms a local 1-design. Furthermore, we show that if each quantum gate is affected by a qqq-strength local Pauli channel with the noise strength range of 1/poly(n)1/{\rm poly} (n)1/poly(n) to 0.1, the noisy QAOA circuit with a depth of O(log⁡n/log⁡(1/q))\mathcal{O}\left(\log n/\log(1/q)\right)O(logn/log(1/q)) can also be trained efficiently. Our results offer valuable insights into the theoretical performance of quantum optimization algorithms in the noisy intermediate-scale quantum era.
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.
Quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve NP-hard problems in near-term gate-based noisy quantum devices. In QAOA, the gate parameters of a parameterized quantum circuit (PQC) are varied by a classical optimizer to generate a quantum state with a significant support to the optimal solution. The existing analysis fails to consider nonidealities in the qubit quality i.e., short lifetime and imperfect gate operations in a realistic quantum hardware. In this article, we study the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analysis indicates that QAOA performance is noise-sensitive (especially higher-depth QAOA instances). Therefore, the optimal number of stages (p-value) for any QAOA instance is limited by the noise in the target hardware as opposed to the current perception that QAOA will provide monotonically better performance with higher-depth. We show that the two-qubit gate error has to be decreased by more than 75% of the current state-of-the-art levels to attain a performance within 10% of the maximum value for the lowest-depth QAOA.
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.
Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum algorithms for the Noisy Intermediate-Scale Quantum (NISQ) era. Quantifying the performance of QAOA in the near-term regime is of utmost importance. We perform a large-scale numerical study of the approximation ratios attainable by QAOA is the low-to medium-depth regime. To find good QAOA parameters we perform 990 million 10-qubit QAOA circuit evaluations. We find that the approximation ratio increases only marginally as the depth is increased, and the gains are offset by the increasing complexity of optimizing variational parameters. We observe a high variation in approximation ratios attained by QAOA, including high variations within the same class of problem instances. We observe that the difference in approximation ratios between problem instances increases as the similarity between instances decreases. We find that optimal QAOA parameters concentrate for instances in out benchmark, confirming the previous findings for a different class of problems.
Quantum approximate optimization algorithm (QAOA) is a hybrid algorithm whose control parameters are classically optimized. In addition to the variational parameters, the right choice of hyperparameter is crucial for improving the performance of any optimization model. Control depth, or the number of variational parameters, is considered as the most important hyperparameter for QAOA. In this paper we investigate the control depth selection with an automatic algorithm based on proximal gradient descent. The performances of the automatic algorithm are demonstrated on seven-node and ten-node max-cut problems, which show that the control depth can be significantly reduced during the iteration whereas achieving an sufficient level of optimization accuracy. With theoretical convergence guarantee, the proposed algorithm can be used as an efficient tool for choosing the appropriate control depth as a replacement of random search or empirical rules. Moreover, the reduction of control depth will induce a significant reduction in the number of quantum gates in circuit, which improves the applicability of QAOA on noisy intermediate-scale quantum devices.