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:1706.02998 · Physical Review A

Quantum approximate optimization algorithm for MaxCut: A fermionic view

Zhihui Wang, Stuart Hadfield, Jiang Zhang, Eleanor Gilbert Rieffel

Published Feb 5, 2018• 351 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.97.022304

Related papers

Small graph perturbations, QAOA, and the MaxCut problem

Leonardo Lavagna, Simone Piperno, Andrea Ceschini +1 more

We investigate the Maximum Cut (MaxCut) problem on different graph classes with the quantum approximate optimization algorithm (QAOA) using symmetries. In particular, heuristics on the relationship between graph symmetries and the approximation ratio achieved by a QAOA simulation are considered. To do so, we first solve the MaxCut problem on well-known graphs, then we consider simple and controllable perturbations of the graph and find again the approximate MaxCut with the QAOA. Through an analysis of the spectrum of the graphs and their perturbations, as well as a careful study of the associated automorphism groups, we aim to extract valuable insight into how symmetry impacts the performance of QAOA. These insights can then be leveraged to heuristically reduce the quantum circuit complexity, the number of training steps, or the number of parameters involved, thus enhancing the efficiency and effectiveness of QAOA-based solutions.

arXiv:2408.15413•AVS Quantum Science•Oct 14, 2025•3 citations

Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit

Sami Boulebnane, Ashley Montanaro

Combinatorial optimization is regarded as a potentially promising application of near and long-term quantum computers. The best-known heuristic quantum algorithm for combinatorial optimization on gate-based devices, the Quantum Approximate Optimization Algorithm (QAOA), has been the subject of many theoretical and empirical studies. Unfortunately, its application to specific combinatorial optimization problems poses several difficulties: among these, few performance guarantees are known, and the variational nature of the algorithm makes it necessary to classically optimize a number of parameters. In this work, we partially address these issues for a specific combinatorial optimization problem: diluted spin models, with MAX-CUT as a notable special case. Specifically, generalizing the analysis of the Sherrington-Kirkpatrick model by Farhi et al., we establish an explicit algorithm to evaluate the performance of QAOA on MAX-CUT applied to random Erdos-Renyi graphs of expected degree $d$ for an arbitrary constant number of layers $p$ and as the problem size tends to infinity. This analysis yields an explicit mapping between QAOA parameters for MAX-CUT on Erdos-Renyi graphs of expected degree $d$, in the limit $d \to \infty$, and the Sherrington-Kirkpatrick model, and gives good QAOA variational parameters for MAX-CUT applied to Erdos-Renyi graphs. We then partially generalize the latter analysis to graphs with a degree distribution rather than a single degree $d$, and finally to diluted spin-models with $D$-body interactions ($D \geq 3$). We validate our results with numerical experiments suggesting they may have a larger reach than rigorously established; among other things, our algorithms provided good initial, if not nearly optimal, variational parameters for very small problem instances where the infinite-size limit assumption is clearly violated.

arXiv:2110.10685•Oct 20, 2021•9 citations

The Quantum Approximate Optimization Algorithm: Performance on Max-Cut using Heuristic Parameter determination

Jacques C. P. Bus

The Quantum Approximate Optimization Algorithm (QAOA) is one of the promising near-term algorithms designed to find approximate solutions for combinatorial optimization problems. The algorithm prepares a parametrized state that is aimed to maximize the expectation value of the objective function of the problem. The circuit for QAOA consists of p layers, and it depends on 2p parameters, the determination of which can be carried out using a variational quantum eigensolver (VQE) subroutine. This is a variational approach for finding optimal parameters, where the quantum state is prepared with a quantum computer, and a classical computer is used for calculating the corresponding objective function value and performing an outer loop optimization routine in order to find optimal parameters. Earlier work on the algorithm has shown that QAOA is closely related to the Quantum Adiabatic Algorithm, which results in noticeable patterns in the optimal parameters. To this purpose, two methods, INTERP and FOURIER, were proposed to exploit this structure by Zhou et al. (2018). In this thesis, I extend upon these results by examining the effectiveness of one of their methods, the INTERP method, on the Max-Cut problem from graph theory. The performance of QAOA using this method was studied on several classes of graphs and benchmarked against the currently best-known classical algorithm Goemans-Williamson, which achieves an approximation ratio of ρ ≈ 0.878 on arbitrary graphs. The classes of graphs examined include cyclic, weighted and unweighted 3-regular, and Erdős–Rényi graphs with edge probabilities of 0.5 and 0.75 and graph sizes ranging from 4 to 16. Moreover, it was investigated if the INTERP method offers an advantage compared to random initialization of parameters and whether or not the method is polynomial in p. It was found that different graph classes lead to similar but different parameter patterns. Furthermore, the performance of QAOA using the INTERP method was dependent on the graph class considered. For the small graphs investigated it was found that QAOA outperforms Goemans-Williamson on ER-0.50, ER-0.75 and weighted 3-regular graphs from p=7 and beyond with respect to how well the expectation of the objective function approximates the optimal value, while for unweighted 3-regular graphs p=6 suffices. However, the calculation of the parameters is costly and requires a number of function evaluations that is on the order of the number of possible bipartitions of small graph with sizes n ≤ 16. Moreover, the numerical results suggested that indeed the method is polynomial in p advocating that the algorithm might be a strong alternative to Goemans-Williamson for large graph sizes, once hardware allows it.

•Jan 1, 2020•0 citations

On the power of the Quantum Approximate Optimization Algorithm

Sami Boulebnane

The main object of study of this work is the Quantum Approximate Optimization Algorithm (QAOA) —the best-known heuristic quantum algorithm for addressing combinatorial optimization problems. Despite its popularity, QAOA poses major challenges. Namely, its performance remains poorly understood, especially in the low depth regime most relevant to near-term quantum computing. Besides, the algorithm is of variational nature, relying on several hyperparameters to be classically trained. In this work, we contribute to addressing these issues by developing techniques to understand the performance of QAOA at low depth, and deducing from these pretrained hyperparameters, thereby eliminating or considerably reducing the need for a classical optimization loop. We first consider applying QAOA to constraint satisfaction problems with the goal of maximizing the algorithm’s approximation ratio (fraction of satisfied constraints). As a particular example, we consider QAOA applied to MAXCUT on non-regular graphs, showing how analytic techniques provide good guess hyperparameters in this setting. Next, we analyze the performance of QAOA on a well-studied constraint satisfaction problem: random k-SAT. In this case, the performance is measured by the probability of finding an assignment satisfying all constraints (“success probability”). To estimate this quantity, we develop new techniques, mapping quantum expectation values of the QAOA circuits to classical spin models. We further show how these techniques can be generalized to a larger family of random constraint satisfaction problems. We conclude the work by two feasibility studies inspired by real-world use cases encountered in collaborations with industrial partners: peptide sampling, and solving flow problems. These problems are naturally phrased by encoding combinatorial variables in qudits, a relatively unexplored setting in the existing literature. We present partial analytic and numerical results for optimal QAOA hyperparameters and the scaling of its success probability in this framework, underlining potential specific difficulties when using QAOA with qudits.

•Nov 28, 2024•0 citations

Parameter Determination of Quantum Approximate Optimization Algorithm Using Layerwise Grid Search Method

Su‐Ling Lee, Chien‐Cheng Tseng

The quantum approximate optimization algorithm (QAOA) is an efficient method for solving combinatorial optimization problems in quantum computing. These problems involve finding the best solution from a finite set of possibilities. At its core, the QAOA uses an Ansatz circuit composed of alternating unitary operators, the mixing and problem Hamiltonians, that are controlled by a set of parameters. Its goal is to find the optimal parameters so that the final quantum state of the circuit encodes the problem’s solution. While this parameter optimization is often handled by classical optimizers, including constrained optimization by linear approximations (COBYLA) and Nelder–Mead, these methods frequently present local extrema. Therefore, we developed a layerwise grid search (LGS) method as an alternative. Since a full grid search is too time-consuming, the LGS method significantly reduces the search time while still finding a good solution. To demonstrate its effectiveness, we present experimental results for the max-cut problem, comparing the performance of our LGS method against conventional classical optimizers.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Apr 22, 2026•0 citations

Linearly simplified QAOA parameters and transferability

Ryo Sakai, Hiromichi Matsuyama, Wai-Hong Tam +2 more

Quantum Approximate Optimization Algorithm (QAOA) provides a way to solve combinatorial optimization problems using quantum computers. QAOA circuits consist of time evolution operators by the cost Hamiltonian and of state mixing operators, and embedded variational parameter for each operator is tuned so that the expectation value of the cost function is minimized. The optimization of the variational parameters is taken place on classical devices while the cost function is measured in the sense of quantum. To facilitate the classical optimization, there are several previous works on making decision strategies for optimal/initial parameters and on extracting similarities among instances. In our current work, we consider simplified QAOA parameters that take linear forms along with the depth in the circuit. Such a simplification, which would be suggested from an analogy to quantum annealing, leads to a drastic reduction of the parameter space from 2p to 4 dimensions with the any number of QAOA layers p. In addition, cost landscapes in the reduced parameter space have some stability on differing instances. This fact suggests that an optimal parameter set for a given instance can be transferred to other instances. In this paper we present some numerical results that are obtained for instances of the random Ising model and of the max-cut problem. The transferability of linearized parameters is demonstrated for randomly generated source and destination instances, and its dependence on features of the instances are investigated.

arXiv:2405.00655•May 1, 2024•0 citations
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-ppp QAOA circuit consists of ppp steps; in each step a classical Hamiltonian, derived from the cost function, is applied followed by a mixing Hamiltonian. The 2p2p2p 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 ppp 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 ppp 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 ppp. 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.
We investigate the Maximum Cut (MaxCut) problem on different graph classes with the quantum approximate optimization algorithm (QAOA) using symmetries. In particular, heuristics on the relationship between graph symmetries and the approximation ratio achieved by a QAOA simulation are considered. To do so, we first solve the MaxCut problem on well-known graphs, then we consider simple and controllable perturbations of the graph and find again the approximate MaxCut with the QAOA. Through an analysis of the spectrum of the graphs and their perturbations, as well as a careful study of the associated automorphism groups, we aim to extract valuable insight into how symmetry impacts the performance of QAOA. These insights can then be leveraged to heuristically reduce the quantum circuit complexity, the number of training steps, or the number of parameters involved, thus enhancing the efficiency and effectiveness of QAOA-based solutions.
Combinatorial optimization is regarded as a potentially promising application of near and long-term quantum computers. The best-known heuristic quantum algorithm for combinatorial optimization on gate-based devices, the Quantum Approximate Optimization Algorithm (QAOA), has been the subject of many theoretical and empirical studies. Unfortunately, its application to specific combinatorial optimization problems poses several difficulties: among these, few performance guarantees are known, and the variational nature of the algorithm makes it necessary to classically optimize a number of parameters. In this work, we partially address these issues for a specific combinatorial optimization problem: diluted spin models, with MAX-CUT as a notable special case. Specifically, generalizing the analysis of the Sherrington-Kirkpatrick model by Farhi et al., we establish an explicit algorithm to evaluate the performance of QAOA on MAX-CUT applied to random Erdos-Renyi graphs of expected degree ddd for an arbitrary constant number of layers ppp and as the problem size tends to infinity. This analysis yields an explicit mapping between QAOA parameters for MAX-CUT on Erdos-Renyi graphs of expected degree ddd, in the limit d→∞d \to \inftyd→∞, and the Sherrington-Kirkpatrick model, and gives good QAOA variational parameters for MAX-CUT applied to Erdos-Renyi graphs. We then partially generalize the latter analysis to graphs with a degree distribution rather than a single degree ddd, and finally to diluted spin-models with DDD-body interactions (D≥3D \geq 3D≥3). We validate our results with numerical experiments suggesting they may have a larger reach than rigorously established; among other things, our algorithms provided good initial, if not nearly optimal, variational parameters for very small problem instances where the infinite-size limit assumption is clearly violated.
The Quantum Approximate Optimization Algorithm (QAOA) is one of the promising near-term algorithms designed to find approximate solutions for combinatorial optimization problems. The algorithm prepares a parametrized state that is aimed to maximize the expectation value of the objective function of the problem. The circuit for QAOA consists of p layers, and it depends on 2p parameters, the determination of which can be carried out using a variational quantum eigensolver (VQE) subroutine. This is a variational approach for finding optimal parameters, where the quantum state is prepared with a quantum computer, and a classical computer is used for calculating the corresponding objective function value and performing an outer loop optimization routine in order to find optimal parameters. Earlier work on the algorithm has shown that QAOA is closely related to the Quantum Adiabatic Algorithm, which results in noticeable patterns in the optimal parameters. To this purpose, two methods, INTERP and FOURIER, were proposed to exploit this structure by Zhou et al. (2018). In this thesis, I extend upon these results by examining the effectiveness of one of their methods, the INTERP method, on the Max-Cut problem from graph theory. The performance of QAOA using this method was studied on several classes of graphs and benchmarked against the currently best-known classical algorithm Goemans-Williamson, which achieves an approximation ratio of ρ ≈ 0.878 on arbitrary graphs. The classes of graphs examined include cyclic, weighted and unweighted 3-regular, and Erdős–Rényi graphs with edge probabilities of 0.5 and 0.75 and graph sizes ranging from 4 to 16. Moreover, it was investigated if the INTERP method offers an advantage compared to random initialization of parameters and whether or not the method is polynomial in p. It was found that different graph classes lead to similar but different parameter patterns. Furthermore, the performance of QAOA using the INTERP method was dependent on the graph class considered. For the small graphs investigated it was found that QAOA outperforms Goemans-Williamson on ER-0.50, ER-0.75 and weighted 3-regular graphs from p=7 and beyond with respect to how well the expectation of the objective function approximates the optimal value, while for unweighted 3-regular graphs p=6 suffices. However, the calculation of the parameters is costly and requires a number of function evaluations that is on the order of the number of possible bipartitions of small graph with sizes n ≤ 16. Moreover, the numerical results suggested that indeed the method is polynomial in p advocating that the algorithm might be a strong alternative to Goemans-Williamson for large graph sizes, once hardware allows it.
The main object of study of this work is the Quantum Approximate Optimization Algorithm (QAOA) —the best-known heuristic quantum algorithm for addressing combinatorial optimization problems. Despite its popularity, QAOA poses major challenges. Namely, its performance remains poorly understood, especially in the low depth regime most relevant to near-term quantum computing. Besides, the algorithm is of variational nature, relying on several hyperparameters to be classically trained. In this work, we contribute to addressing these issues by developing techniques to understand the performance of QAOA at low depth, and deducing from these pretrained hyperparameters, thereby eliminating or considerably reducing the need for a classical optimization loop. We first consider applying QAOA to constraint satisfaction problems with the goal of maximizing the algorithm’s approximation ratio (fraction of satisfied constraints). As a particular example, we consider QAOA applied to MAXCUT on non-regular graphs, showing how analytic techniques provide good guess hyperparameters in this setting. Next, we analyze the performance of QAOA on a well-studied constraint satisfaction problem: random k-SAT. In this case, the performance is measured by the probability of finding an assignment satisfying all constraints (“success probability”). To estimate this quantity, we develop new techniques, mapping quantum expectation values of the QAOA circuits to classical spin models. We further show how these techniques can be generalized to a larger family of random constraint satisfaction problems. We conclude the work by two feasibility studies inspired by real-world use cases encountered in collaborations with industrial partners: peptide sampling, and solving flow problems. These problems are naturally phrased by encoding combinatorial variables in qudits, a relatively unexplored setting in the existing literature. We present partial analytic and numerical results for optimal QAOA hyperparameters and the scaling of its success probability in this framework, underlining potential specific difficulties when using QAOA with qudits.
The quantum approximate optimization algorithm (QAOA) is an efficient method for solving combinatorial optimization problems in quantum computing. These problems involve finding the best solution from a finite set of possibilities. At its core, the QAOA uses an Ansatz circuit composed of alternating unitary operators, the mixing and problem Hamiltonians, that are controlled by a set of parameters. Its goal is to find the optimal parameters so that the final quantum state of the circuit encodes the problem’s solution. While this parameter optimization is often handled by classical optimizers, including constrained optimization by linear approximations (COBYLA) and Nelder–Mead, these methods frequently present local extrema. Therefore, we developed a layerwise grid search (LGS) method as an alternative. Since a full grid search is too time-consuming, the LGS method significantly reduces the search time while still finding a good solution. To demonstrate its effectiveness, we present experimental results for the max-cut problem, comparing the performance of our LGS method against conventional classical optimizers.
Quantum Approximate Optimization Algorithm (QAOA) provides a way to solve combinatorial optimization problems using quantum computers. QAOA circuits consist of time evolution operators by the cost Hamiltonian and of state mixing operators, and embedded variational parameter for each operator is tuned so that the expectation value of the cost function is minimized. The optimization of the variational parameters is taken place on classical devices while the cost function is measured in the sense of quantum. To facilitate the classical optimization, there are several previous works on making decision strategies for optimal/initial parameters and on extracting similarities among instances. In our current work, we consider simplified QAOA parameters that take linear forms along with the depth in the circuit. Such a simplification, which would be suggested from an analogy to quantum annealing, leads to a drastic reduction of the parameter space from 2p to 4 dimensions with the any number of QAOA layers p. In addition, cost landscapes in the reduced parameter space have some stability on differing instances. This fact suggests that an optimal parameter set for a given instance can be transferred to other instances. In this paper we present some numerical results that are obtained for instances of the random Ising model and of the max-cut problem. The transferability of linearized parameters is demonstrated for randomly generated source and destination instances, and its dependence on features of the instances are investigated.