QAOA

QAOA is a family of parameterized quantum states built by alternating an objective-dependent phase separator with a mixer. This page uses one maximization convention throughout: larger eigenvalues of the diagonal cost operator $C$ are better, and the circuit applies $U_C(\gamma)=e^{-i\gamma C}$ before $U_B(\beta)=e^{-i\beta B}$ in each layer. The original construction is the quantum approximate optimization algorithm of Farhi, Goldstone, and Gutmann (2014); constrained and more general variants are often called the quantum alternating operator ansatz. The ansatz supports exact finite-depth analysis and useful family-specific results, but neither its form nor any result below establishes a generic end-to-end practical speedup over classical optimization.

Helpful background. Variational quantum algorithms explains how repeated measurements guide parameter optimization. Pauli matrices supplies the spin rotations used below.

QAOA as Alternating Cost-and-Mixer Dynamics

Let a classical score $C(z)$ be assigned to each $n$-bit string. Its diagonal operator and the standard transverse-field mixer are

$$C=\sum_z C(z)\lvert z\rangle\langle z\rvert, \qquad B=\sum_{j=1}^{n}X_j.$$

The corresponding unitaries are

$$U_C(\gamma)=e^{-i\gamma C}, \qquad U_B(\beta)=e^{-i\beta B}.$$

$U_C$ changes phases according to objective value but leaves computational-basis probabilities unchanged. $U_B$ then mixes amplitudes between strings that differ in one bit. Alternating the two can turn relative phases into a probability bias toward high-scoring strings. That interference mechanism is more precise than saying that the circuit “searches all answers at once”: useful bias depends on the encoded objective, initial state, mixer, angles, and depth.

“QAOA” is used for three related objects that should not be conflated. The original quantum approximate optimization algorithm uses a cost operator, the transverse-field mixer, the uniform initial state, and shared angles at a fixed level $p$. The broader quantum alternating operator ansatz replaces the initial state, phase separator, or mixer to encode constraints and problem structure, as formalized by Hadfield et al. (2019). A Hamiltonian variational ansatz alternates physically motivated noncommuting Hamiltonian terms and may target a quantum state rather than a classical bit string; early examples appear in Wecker, Hastings, and Troyer (2015). The last usage is QAOA-like, but a computational-basis measurement is not generally an energy sample for a non-diagonal target Hamiltonian.

To use this state family for optimization, choose the angles, measure bitstrings, score them and return a candidate. The choice of angles can use analytic formulas, classical simulation or a measurement-based optimizer. A low circuit depth alone does not specify how much work that search requires. The examples below first fix the angles analytically so that their quantum probabilities can be studied independently of optimization.

From a Classical Objective to a Cost Hamiltonian

Binary variables and diagonal operators

For $x_i\in\{0,1\}$, the computational-basis eigenvalue relation $Z_i\lvert x_i\rangle=(-1)^{x_i}\lvert x_i\rangle$ gives

$$x_i\mapsto\frac{I-Z_i}{2}, \qquad x_ix_j\mapsto \frac{I-Z_i-Z_j+Z_iZ_j}{4}.$$

Thus a quadratic unconstrained binary objective

$$f(x)=c+\sum_i h_i x_i+\sum_{i<j}Q_{ij}x_ix_j$$

becomes an Ising operator containing a constant, one-body $Z_i$ terms, and two-body $Z_iZ_j$ terms. The substitution is an equality on every basis state, not a continuous relaxation. Higher-degree monomials similarly become products of diagonal Pauli operators, although reducing their locality may require ancillas and penalties whose costs belong in the encoding.

Here the quadratic sum is over distinct variables. If a QUBO matrix notation includes diagonal terms, reduce them first with $x_i^2=x_i$ and absorb their coefficients into the linear terms before applying the two-variable substitution.

For weighted MaxCut, an edge $\{u,v\}$ is cut exactly when the endpoint bits differ. Its indicator is

$$x_u+x_v-2x_ux_v = \frac12(I-Z_uZ_v),$$

so, for weights $w_{uv}$,

$$C = \sum_{\{u,v\}\in E} \frac{w_{uv}}{2}(I-Z_uZ_v).$$

Every term is diagonal and all terms commute. Consequently,

$$U_C(\gamma) = \prod_{\{u,v\}\in E} \exp\!\left[-\frac{i\gamma w_{uv}}{2}(I-Z_uZ_v)\right]$$

is an exact factorization. Calling it a Trotter approximation would introduce an error that is absent. A compiler may discard the product of constant-term phases, but it must retain the coefficient scale that determines the useful angle and the physical rotation precision.

Penalties and objective scale

Constraints can be encoded by maximizing

$$C_\lambda=C-\lambda P,$$

where the feasible set is nonempty, $P=0$ on feasible strings and $P\ge1$ on infeasible strings. If the unpenalized objective is bounded by $C_{\min}\le C(z)\le C_{\max}$ on all strings, then the crude sufficient condition

$$\lambda>C_{\max}-C_{\min}$$

makes every infeasible penalized value at most $C_{\max}-\lambda<C_{\min}$, whereas every feasible value is at least $C_{\min}$. This condition is sufficient, not necessary. A tighter problem-specific gap can permit a much smaller penalty. Large coefficients expand the phase range, demand finer control, can worsen objective-estimation variance, and may require additional high-locality decomposition or ancillas. “Unconstrained” in QUBO therefore does not mean cost-free encoding.

Affine changes also require care. For

$$C'=\alpha C+\kappa I,$$

the identity contribution produces only the global phase $e^{-i\gamma\kappa}$, while $\alpha$ rescales the effective angle from $\gamma$ to $\alpha\gamma$. Positive $\alpha$ preserves the maximizing strings; negative $\alpha$ reverses their ranking, and $\alpha=0$ removes all objective dependence. It is safe to drop $\kappa I$ during state preparation if its value is restored when reporting the original objective. It is not safe to assume an approximation ratio is shift invariant: $F/C_{\max}$ and $(F+\kappa)/(C_{\max}+\kappa)$ are generally different. Keep the original objective and its offset when comparing a mean score with the optimum.

The Standard Depth-p Circuit

Shared angles and operator order

At level $p$, the declared state is

$$\lvert\boldsymbol\gamma,\boldsymbol\beta\rangle = U_B(\beta_p)U_C(\gamma_p)\cdots U_B(\beta_1)U_C(\gamma_1)\lvert s\rangle.$$

The rightmost operation acts first. The standard unconstrained construction uses

$$\lvert s\rangle=\lvert+\rangle^{\otimes n},$$

so the phase separator acts on a uniform superposition before the mixer in each layer. There are $2p$ shared real parameters: every cost term uses the same $\gamma_\ell$ and every mixer term uses the same $\beta_\ell$ within layer $\ell$. Parameter sharing is part of the ansatz and is distinct from a more general circuit that assigns an angle to each edge or vertex.

The maximization signs matter. Authors who minimize a problem Hamiltonian, define $e^{+i\gamma C}$, reverse the mixer sign, or write products in the opposite order obtain angle formulas related by sign changes or reordered coordinates. Transcribing a reported optimum without transcribing its generator and order conventions is therefore unsafe.

The ideal expectation and output distribution are

$$F_p(\boldsymbol\gamma,\boldsymbol\beta) = \langle C\rangle = \sum_z C(z)P_p(z),$$ $$P_p(z) = \left\lvert \langle z\vert\boldsymbol\gamma,\boldsymbol\beta\rangle \right\rvert^2.$$

$F_p$ is an average score. It is not the probability of sampling an optimum, nor does it determine the whole tail of $P_p$. Two angle sets can have the same expectation but very different probabilities of returning a usable candidate. If the aim is to obtain a good bitstring, examine the high-score part of the distribution as well as its mean.

MaxCut at p = 1

The general depth-one edge formula

Consider unweighted MaxCut on a simple graph under the exact convention above, with $\lvert s\rangle=\lvert+\rangle^{\otimes n}$ and $p=1$. For an edge $(u,v)$, let

$$a=\deg(u)-1, \qquad b=\deg(v)-1,$$

and let $\lambda$ be the number of triangles containing that edge. Then the ideal expected contribution of $C_{uv}=(I-Z_uZ_v)/2$ is

$$\langle C_{uv}\rangle ={}\frac12+ \frac14\sin(4\beta)\sin\gamma \left(\cos^a\gamma+\cos^b\gamma\right) -\frac14\sin^2(2\beta) \cos^{a+b-2\lambda}\gamma \left[1-\cos^\lambda(2\gamma)\right].$$

The result follows by evaluating the edge observable in the Heisenberg picture. Mixer conjugation sends each endpoint $Z$ into a linear combination of $Z$ and $Y$ with angle $2\beta$. Cost terms incident on one endpoint rotate the resulting $Y$ into $X$ components. Expectation in the plus state removes every Pauli string containing a remaining $Y$ or $Z$. Neighbors unique to one endpoint supply powers of $\cos\gamma$; common neighbors create paired paths whose interference produces the final triangle term. Terms outside the radius-one edge neighborhood cancel from this local expectation.

This is the corrected depth-one expression of Wang et al.. The last term vanishes only when $\lambda=0$ (or at special angles), so the triangle-free expression cannot be applied to a graph merely because it is regular. The hypotheses also exclude weighted edges unless the angle dependence is rederived with each incident weight.

For one isolated edge, $a=b=\lambda=0$, and the expression reduces to

$$\langle C_{uv}\rangle = \frac12+\frac12\sin(4\beta)\sin\gamma.$$

At $\beta=\pi/8$ and $\gamma=\pi/2$, the cut expectation is one. The complete distribution is derived in Exercise 2: each of the two cut bitstrings has probability one half.

Triangle-free regular graphs

For a simple triangle-free $d$-regular graph with $d\ge2$, every edge has $a=b=d-1$ and $\lambda=0$. Summing identical edge expectations gives

$$\frac{F_1}{\lvert E\rvert} = \frac12+ \frac12\sin(4\beta)\sin\gamma\cos^{d-1}\gamma.$$

Choose the positive branch. The factor $\sin(4\beta)$ is maximized by $\beta=\pi/8$. For $g(\gamma)=\sin\gamma\cos^{d-1}\gamma$,

$$g'(\gamma) = \cos^{d-2}\gamma \left(1-d\sin^2\gamma\right).$$

An interior maximum in $0<\gamma<\pi/2$ therefore satisfies

$$\tan\gamma=\frac1{\sqrt{d-1}}, \qquad \sin\gamma=\frac1{\sqrt d}, \qquad \cos\gamma=\sqrt{1-\frac1d}.$$

Substitution yields

$$\frac{F_1}{\lvert E\rvert} = \frac12+ \frac{1}{2\sqrt d} \left(1-\frac1d\right)^{(d-1)/2}.$$

This formula gives the ideal depth-one mean divided by the number of edges, not an optimum-hit probability. For a nonempty graph the maximum cut $C^*$ obeys $C^*\le m=\lvert E\rvert$, so

$$\frac{F_1}{C^*}\ge\frac{F_1}{m}.$$

Thus the displayed fraction is a lower bound on the expected approximation ratio, even when $C^*$ is unknown. It equals that ratio for a bipartite graph, whose entire edge set can be cut. It need not equal it for a nonbipartite triangle-free graph. Neither quantity guarantees the score of every individual measurement. The $d=1$ case is the isolated-edge value at $\gamma=\pi/2$.

For $d=3$ and nine edges, the formula gives $F_1=9/2+\sqrt3$. At its representative optimum the ideal Hessian is diagonal:

$$\frac{\partial^2F_1}{\partial\beta^2}=-16\sqrt3, \qquad \frac{\partial^2F_1}{\partial\gamma^2}=-6\sqrt3, \qquad \frac{\partial^2F_1}{\partial\beta\,\partial\gamma}=0.$$

Those curvatures describe this two-parameter ideal landscape locally; they do not measure finite-shot optimizer difficulty or noise sensitivity by themselves.

Expectation, Sampling, and Approximation Quality

Expected score and threshold success

QAOA produces a distribution, so “performance” is incomplete without a functional of that distribution and an acceptance rule. For a score bounded by $C_{\min}$ and $C_{\max}$, the normalized expectation

$$\widetilde F_p = \frac{F_p-C_{\min}}{C_{\max}-C_{\min}}$$

lies in $[0,1]$ when $C_{\max}>C_{\min}$. If the true optimum $C^*>0$ is known and the nonnegative objective has not been shifted, $F_p/C^*$ is an expected approximation ratio. These normalizations answer different questions and can rank methods differently after offsets or penalties.

Quantity	Definition	Interpretation
Expected objective	$F_p=\sum_z C(z)P_p(z)$	Mean score of one draw.
Expected approximation ratio	$F_p/C^*$	Mean divided by the positive optimum of an unshifted nonnegative objective.
Threshold probability	$q_\tau=\Pr[C(z)\ge\tau]$	Chance that one draw meets the target score.
Best of $R$ samples	$C_{(R)}=\max_r C(z_r)$	Score of the candidate returned after $R$ independent draws.
Feasibility probability	$\Pr[z\in\mathcal F]$	Fraction of draws satisfying the constraint before any rejection.

An expectation does not fix a tail probability. A distribution concentrated just below $\tau$ can have a larger expectation but a smaller $q_\tau$ than a broader distribution. Conversely, a rare optimum can coexist with a modest mean. If the application consumes one best candidate, report the empirical or modeled distribution of $C_{(R)}$ and the total cost of all draws, not only the value of the selected string.

For one-shot threshold probability $q_\tau$, independent repetitions hit the threshold at least once with probability $1-(1-q_\tau)^R$. Requiring failure probability at most $\delta$ gives

$$R \ge \frac{\log\delta}{\log(1-q_\tau)}.$$

The expression is interpreted at its boundaries: if $q_\tau=0$, no finite number of repetitions can succeed; if $q_\tau=1$, one draw suffices and the logarithmic quotient is replaced by that direct conclusion. Independence is an assumption. Drift or adaptive changes between runs can invalidate the geometric model.

Shot uncertainty and independent validation

Suppose independent computational-basis shots produce scores $C_s$ in $[C_{\min},C_{\max}]$ and $\bar C=S^{-1}\sum_{s=1}^{S}C_s$. Hoeffding’s inequality gives

$$\Pr\!\left(\lvert\bar C-\mathbb EC\rvert\ge\epsilon\right) \le 2\exp\!\left[- \frac{2S\epsilon^2}{(C_{\max}-C_{\min})^2} \right].$$

For normalized cut fractions in $[0,1]$, demanding absolute error $\epsilon=0.025$ with failure probability $\delta=0.05$ is guaranteed by

$$S \ge \left\lceil \frac{\log(2/\delta)}{2\epsilon^2} \right\rceil =2952.$$

This distribution-free bound is conservative and addresses estimation of a fixed state’s mean. It does not say that 2952 shots find an optimum, estimate every bucket probability accurately, or suffice for an adaptive optimizer. Empirical Bernstein, likelihood, or exact binomial methods can be sharper when their assumptions and stopping rules are declared.

Choosing the best-looking angles from noisy estimates tends to select favorable measurement fluctuations. Fresh measurements at the selected angles estimate their performance without reusing the fluctuation that made those angles look favorable. Generalizing a fitted parameter rule to other graphs also requires testing on graphs that were not used to choose it. Count both the measurements used to choose the angles and those used to assess or sample the final state.

Parameter Domains, Optimization, and Transfer

Conditional periodicities

Period reductions depend on spectra and symmetries. Since $e^{-i\pi X_j}=-I$, the transverse mixer satisfies

$$U_B(\beta+\pi)=(-1)^nU_B(\beta),$$

so $\beta$ has period $\pi$ up to a global phase for the standard mixer. For an unweighted MaxCut objective, every eigenvalue $C(z)$ is an integer and

$$U_C(\gamma+2\pi)=U_C(\gamma).$$

Arbitrary real edge weights need not have a common nonzero $\gamma$ period. Commensurate rationally related weights can recover a rescaled period, but it must be derived from the actual spectrum rather than assumed from the unweighted case.

For the usual MaxCut initial state, a stronger symmetry holds. Let $Q=X^{\otimes n}$. Weighted or unweighted MaxCut satisfies $[Q,C]=0$, the standard mixer satisfies $[Q,B]=0$, and $Q\lvert+\rangle^{\otimes n}=\lvert+\rangle^{\otimes n}$. Since

$$U_B(\beta+\pi/2)=(-i)^n Q\,U_B(\beta),$$

a $\pi/2$ shift of any one mixer angle changes the complete standard QAOA state only by a global phase. Every bitstring probability is unchanged, and complementary bitstrings already have equal probabilities. A bitstring-dependent scoring rule cannot distinguish these two identical distributions.

For an asymmetric initial state, the same shift instead complements the output distribution; the cut mean remains invariant but individual bitstring probabilities need not. Local fields, pinned variables or different mixer generators require a fresh symmetry calculation. A smaller parameter domain should follow from the actual state and generators, not from the name QAOA.

Layer growth and parameter transfer

Let $F_p^*$ be the globally optimized ideal expectation over all level-$p$ angles. Appending a layer with $\gamma_{p+1}=\beta_{p+1}=0$ applies the identity, so the level-$p$ family is embedded in level $p+1$ and

$$F_{p+1}^*\ge F_p^*.$$

This expressivity statement assumes exact gates and a global optimum. A finite optimizer can miss the embedded point; a noisy implementation can make an added identity only nominally identity; and increased compilation, estimation, or calibration cost can reduce achieved quality. Observed best-of-budget performance therefore need not be monotone in $p$.

Reachability can also fail at insufficient depth even before optimization and noise are considered, as emphasized by Akshay et al. (2020). Parameter interpolation from level $p$ to $p+1$, smooth Fourier parameterizations, and transfer across graph ensembles can reduce search cost on some structured families; Zhou et al. (2020) develops representative strategies and mechanisms. These are heuristics. Angles learned for one graph family or coefficient scale may perform poorly on another. Smooth-looking schedules do not by themselves prove convergence.

Hard Constraints and Alternating Operators

Feasibility preservation is not connectivity

For a feasible set $\mathcal F\subseteq\{0,1\}^n$, define

$$\Pi_{\mathcal F} = \sum_{z\in\mathcal F}\lvert z\rangle\langle z\rvert.$$

If the initial state lies in the feasible subspace and

$$[B_{\mathcal F},\Pi_{\mathcal F}]=0,$$

then $e^{-i\beta B_{\mathcal F}}$ preserves that subspace. A diagonal phase separator also preserves it. This removes infeasible measurement outcomes in the ideal circuit, but the commutator condition is not enough for a useful search. Construct a graph whose vertices are feasible strings and whose edges join pairs connected by a nonzero off-diagonal matrix element of $B_{\mathcal F}$. If that transition graph is disconnected, no choice of angles can move amplitude between its components. Any component absent from the initial support stays absent. If useful solutions lie only in such components, change the preparation or mixer. Initial support in several components is possible, but their total probabilities remain separately conserved.

The standard example for a fixed Hamming-weight constraint is

$$B_{XY} = \frac12\sum_{\{i,j\}\in E_M}(X_iX_j+Y_iY_j).$$

Writing $X_iX_j+Y_iY_j=2(\sigma_i^+\sigma_j^-+\sigma_i^-\sigma_j^+)$ shows that each term exchanges 10 and 01 while annihilating 00 and 11. It therefore commutes with the number operator

$$N_1=\sum_i\frac{I-Z_i}{2}, \qquad [B_{XY},N_1]=0.$$

If the mixer graph $(V,E_M)$ is connected, sequences of exchanges connect all bitstrings of a fixed nontrivial weight. If it is disconnected, the number of ones in each component is separately conserved, fragmenting the feasible space even though total Hamming weight is preserved.

Graph connectivity is not full quantum controllability. For example, in the one-excitation sector of three qubits, take the complete-graph XY mixer and assign scores $(1,1,0)$ to the three basis states. From their uniform superposition, both the cost and mixer preserve exchange of the first two states. Those amplitudes remain equal at every level, so neither optimal bitstring can acquire probability above $1/2$, although the transition graph is connected. The circuit can favor the pair without preparing either member alone.

There is also a compilation distinction from MaxCut. XY terms on overlapping edges generally do not commute. For $H_{ij}=(X_iX_j+Y_iY_j)/2$,

$$e^{-i\beta(H_{12}+H_{23})} \ne e^{-i\beta H_{12}}e^{-i\beta H_{23}}$$

at generic $\beta$. Disjoint-edge terms do commute. A specified sequence of edge-exchange gates is a valid alternating-operator mixer and preserves Hamming weight exactly, but it is a different unitary from the exponential of their sum unless an approximation with controlled error is intended.

This approach differs from the penalty $C_\lambda=C-\lambda P$. A penalty retains an easy transverse mixer but visits infeasible strings and introduces the coefficient-range and compilation costs discussed above. A constrained mixer can avoid penalties, but preparing a feasible superposition and compiling a connected mixer may be difficult. Neither approach dominates without an instance-specific resource and reachability analysis. The alternating-operator framework of Hadfield et al. (2019) makes these choices explicit.

Compiling cost and mixer layers

Logical layer costs

For unweighted MaxCut, one logical cost layer contains $m=\lvert E\rvert$ two-qubit $ZZ$ interactions, and one standard mixer layer contains $n$ single-qubit rotations because

$$e^{-i\beta B} = \prod_{j=1}^n e^{-i\beta X_j} = \prod_{j=1}^n R_x^{(j)}(2\beta).$$

Under all-to-all connectivity, disjoint edges can execute together. For a simple graph, an edge coloring partitions $E$ into $\chi'(G)$ matchings, and Vizing’s theorem gives

$$\chi'(G)\le\Delta+1.$$

With one native $ZZ$ interaction per edge, the two-qubit depth of a cost layer is $\chi'(G)$ and its mixer adds one single-qubit layer, giving logical alternating depth $p[\chi'(G)+1]$ under these assumptions. The native two-qubit interaction count is $pm$ and two-qubit depth is $p\chi'(G)$. Multigraphs require a different edge-coloring bound; restricted connectivity and crosstalk exclusions can require additional matchings or routing.

Compiled and experimental costs

Up to a global phase, an edge separator is a $ZZ$ rotation. With $R_z(\theta)=e^{-i\theta Z/2}$, one conventional implementation is a CNOT–$R_z(-\gamma w_{uv})$–CNOT sequence. It uses $2pm$ entangling gates, whereas a native $ZZ$ implementation uses $pm$. On a matching, the two CNOT rounds are sequential, so the ideal entangling depth becomes $2p\chi'(G)$ rather than the native-$ZZ$ depth $p\chi'(G)$; the intervening single-qubit rotations and mixer layers must also be scheduled. Gate orientation, echoed implementations, synthesis, and hardware topology can change both counts and depth.

These counts describe one circuit execution. For example, $K$ evaluated angle sets with $S$ shots each already require $KS$ state preparations, before final sampling. Routing, state preparation, calibration, mitigation and discarded outcomes can add further work. Noise changes the implemented probability distribution: increasing the number of shots reduces sampling uncertainty but does not remove this systematic difference from the ideal model. See resource estimation for conversion to a physical implementation.

There is one important measurement simplification. A computational-basis shot supplies a complete bitstring, from which every diagonal MaxCut clause can be evaluated simultaneously. Thus $m$ clauses do not imply $m$ noncommuting measurement settings. That property is special to a diagonal classical objective. For a QAOA-like ansatz targeting a non-diagonal Hamiltonian, basis rotations, grouping, covariance, and termwise allocation return, as explained in VQE.

Guarantees, Locality, and Classical Competition

Fixed-depth locality

At level $p$, a local edge observable propagated backward through the circuit can only spread through $p$ rounds of incident cost interactions. On a graph of maximum degree $\Delta>2$, a cycle-free radius-$p$ neighborhood about the two endpoints contains at most

$$q_{\rm tree} = 2\frac{(\Delta-1)^{p+1}-1}{\Delta-2}$$

vertices. For $\Delta=2$, the corresponding bound is $2p+2$. Cycles and overlap can reduce the actual neighborhood. An exact local expectation can therefore be computed from a statevector on this light cone, with cost exponential in $q_{\rm tree}$ but independent of the total $n$ when $p$ and $\Delta$ are fixed.

This observation explains both analytic tractability at low depth and a limitation of local information. Farhi, Gamarnik, and Gutmann (2020) construct worst-case graph examples and depth regimes in which failure to see the whole graph limits what local QAOA can distinguish. The light-cone calculation does not by itself provide an efficient classical sampler for the complete correlated output distribution. Local expectation computation, marginal recovery, exact sampling, approximate sampling, and optimization are separate computational tasks.

For a sum of bounded local clauses on a bounded-degree graph at fixed $p$, only clauses with overlapping light cones can have nonzero covariance in the ideal plus-state calculation. Each clause overlaps only a bounded number of others, so $\operatorname{Var}(C)=O(m)$. This supports concentration of the extensive score under those hypotheses, but it still does not determine the rare optimum tail.

Comparing optimization guarantees

Several statements commonly grouped under “QAOA performance” are logically independent. Reachability asks whether the ansatz contains a useful state. Trainability asks whether an allowed procedure can find useful parameters. Symmetry protection can either exclude invalid states or trap the circuit in an unhelpful sector; Bravyi et al. (2020) prove such obstacles for specified symmetric shallow variational settings. Conditional output- sampling hardness, such as the complexity-theoretic route proposed by Farhi and Harrow (2016), does not imply that sampled strings have high objective value or that a complete optimization procedure beats classical solvers.

For nonnegative-weight MaxCut, a central classical reference point is the Goemans–Williamson semidefinite relaxation and randomized hyperplane rounding. Its worst-case guarantee is

$$\alpha_{\rm GW} = \min_{0<\theta\le\pi} \frac{2\theta}{\pi(1-\cos\theta)} \approx0.878567,$$

as proved by Goemans and Williamson (1995). The guarantee, an achieved instance score, and QAOA’s expected cut fraction are different quantities, but a comparison must nevertheless use the same graph, weights, output rule, and total-cost boundary. Exact branch-and-cut, semidefinite variants, local search, message passing, tensor methods, and modern heuristic portfolios may be more relevant than one universal baseline. Random assignment, with mean half the total weight, is a sanity check rather than a competitive comparator.

Classical local algorithms can also outperform the standard depth-one QAOA benchmark in stated triangle-free bounded-degree regimes; Hastings (2019) gives explicit bounded-depth comparisons. Such a result does not rule out deeper QAOA, different mixers, or other families. It does rule out presenting the depth-one analytic value as an uncontested classical separation. The durable conclusion is narrower: QAOA is a rich and analyzable ansatz framework with important family-dependent results, while shallow depth, a smooth landscape, sampling hardness, or beating random assignment alone establishes no generic end-to-end practical advantage.

Relations to Variational, Adiabatic, and Annealing Methods

QAOA is a VQA once its angles are chosen by an adaptive classical search. The general estimator, optimizer, barren-plateau, geometry, noise, and validation questions remain at Variational Quantum Algorithms; this page adds the alternating-operator structure, MaxCut formulas, output metrics, and constrained mixers. Hamiltonian variational ansatzes use the same alternating idea for quantum-state objectives, but non-diagonal energy measurement must not be replaced by scoring one computational-basis string.

There is also a controlled relation to adiabatic evolution. Under this page’s maximization convention, an adiabatic path can interpolate from a Hamiltonian whose ground state is $\lvert+\rangle^{\otimes n}$, such as $-B$, toward $-C$. A product-formula discretization produces alternating exponentials with angles fixed by time steps and schedule coefficients; because the Hamiltonians carry minus signs, those angles must be translated carefully into the $e^{-i\beta B}e^{-i\gamma C}$ convention. Such digitized schedules form a special subset of QAOA parameters. Arbitrarily optimized angles can be strongly nonadiabatic and need not approximate any monotone continuous path.

Conversely, a large-$p$ existence argument based on increasingly fine digitization supplies neither polynomially bounded $p$, a trainable schedule, a noise-tolerant implementation, nor a practical runtime. Adiabatic Quantum Computation explains the relevant spectral-gap and schedule assumptions. Quantum annealing also treats finite-time dynamics and environmental effects, which are absent from the ideal unitary circuit above.

Device implementations, including the planar superconducting-processor study of Harrigan et al. (2021), are valuable finite experiments rather than timeless algorithmic guarantees. For experimental interpretation and comparisons, see optimization case studies.

Quantum algorithms for optimization compares this approach with search, quantum walks, adiabatic methods and other optimization procedures.

Small graphs: mean score and returned solutions

A two-vertex graph gives the simplest interference calculation: the angles $\gamma=\pi/2$, $\beta=\pi/8$ put equal probability on 01 and 10 and zero probability on 00 and 11. Exercise 2 derives this result. The next two examples show why triangles and probability distributions matter.

The triangle correction

For the three-cycle $C_3$, every edge has $a=b=\lambda=1$. At $(\gamma,\beta)=(\pi/3,\pi/8)$, the general formula gives, per edge,

$$\langle C_{uv}\rangle = \frac12+\frac{\sqrt3}{8}-\frac{3}{16},$$

and therefore

$$F_1 = \frac{15+6\sqrt3}{16} =1.587019052838328\ldots.$$

The only possible cut values of a triangle are zero and two. Hence the optimum-hit probability is not $F_1$ but

$$P(C=2)=\frac{F_1}{2} =0.793509526419164\ldots.$$

Dropping the triangle term would predict a different expectation. This small graph therefore gives a useful test of the common-neighbor term.

K₃,₃ expectation and sampling

Label the two parts of $K_{3,3}$ by $\{0,1,2\}$ and $\{3,4,5\}$, with all nine cross edges. This is a simple, triangle-free, $3$-regular graph. At

$$\beta=\frac\pi8, \qquad \gamma=\arctan\!\left(\frac1{\sqrt2}\right),$$

the regular-graph formula gives

$$F_1 = \frac92+\sqrt3 \approx6.232051,$$

and, because the optimum is $C_{\max}=9$,

$$\frac{F_1}{9} = \frac12+\frac1{3\sqrt3} \approx0.692450.$$

Complete enumeration gives the following distribution. The middle column is the number of the 64 bitstrings with that classical cut value; the last column sums their ideal probabilities, rounded to six decimal places.

Cut value	Bitstring count	Probability (rounded)
0	2	0.000867
3	12	0.070428
4	18	0.080112
5	18	0.393846
6	12	0.120545
9	2	0.334202

The same six possible cut scores have different probabilities before and after the cost–mixer layer. Dashed vertical lines mark the mean score, which rises from $4.5$ to about $6.23$. The probability of the optimum, score nine, rises from $2/64$ to about $0.334$. A higher mean and a larger optimum probability are distinct properties of this calculated distribution.

Thus $P(C=9)\approx0.334202$. Independent repetitions hit an optimum with probability $0.988604$ after eleven draws and $0.992412$ after twelve. The least $R$ reaching $0.99$ is therefore $R_{0.99}=12$. Complementary bitstrings have equal probability, as required by global bit-flip symmetry. This six-qubit bipartite instance is classically trivial—the bipartition itself is an optimum—so it validates only the ideal implementation and summary calculations.

The following NumPy calculation prepares this state and prints its mean and score probabilities. The score array is obtained directly from the edge list; no analytic expectation formula is inserted into the propagation.

import numpy as np
from functools import reduce

n = 6
edges = [(u, v) for u in range(3) for v in range(3, 6)]
cost = np.array([sum(((z >> u) ^ (z >> v)) & 1 for u, v in edges)
                 for z in range(2**n)])
gamma, beta = np.arctan(1 / np.sqrt(2)), np.pi / 8
psi = np.exp(-1j * gamma * cost) / np.sqrt(2**n)
x_rotation = np.array([[np.cos(beta), -1j*np.sin(beta)],
                       [-1j*np.sin(beta), np.cos(beta)]])
psi = reduce(np.kron, [x_rotation] * n) @ psi
probability = abs(psi)**2
print("Mean:", cost @ probability)
for score in np.unique(cost):
    print(score, probability[cost == score].sum())

The array index uses vertex $j$ as bit $j$, with $j=0$ the least significant bit. Every qubit has the same mixer, so the displayed tensor product is unaffected by the ordering of its identical factors. The full matrix is convenient for six qubits; its exponential memory cost makes it unsuitable for large graphs. The separate edge formula provides an analytic comparison for the calculated mean.

Common pitfalls

Cost first, then mixer. Acting first with the transverse mixer on $\lvert+\rangle^{\otimes n}$ changes only a global phase. A circuit-order mistake can therefore remove the desired interference rather than merely shift the best angles.

Regular does not mean triangle-free. The degrees alone do not determine the depth-one edge expectation. Common neighbors contribute the last term in the general formula.

A promising mean is not a success probability. The probability of obtaining a useful bitstring depends on the score distribution. Best-of-many sampling also consumes many executions; counting only the circuit that produced the best candidate omits that cost.

Exercises

1. Map a QUBO to Pauli operators

Let $f(x)=c+\sum_i h_i x_i+\sum_{i<j}Q_{ij}x_ix_j$ for $x_i\in\{0,1\}$. Derive its diagonal Pauli representation, including the constant. If the input instead contains diagonal $Q_{ii}x_i^2$ terms, state how they are reduced. Explain how omitting the constant affects state preparation and how it can affect a reported ratio.

Solution

Substituting $x_i=(I-Z_i)/2$ and $x_ix_j=(I-Z_i-Z_j+Z_iZ_j)/4$ gives

$$f\mapsto \alpha I+\sum_i a_iZ_i+\sum_{i<j}b_{ij}Z_iZ_j,$$

where

$$\begin{aligned} \alpha &=c+\frac12\sum_i h_i+\frac14\sum_{i<j}Q_{ij},\\ a_i &=-\frac{h_i}{2} -\frac14\sum_{j<i}Q_{ji} -\frac14\sum_{j>i}Q_{ij},\\ b_{ij}&=\frac{Q_{ij}}4. \end{aligned}$$

Any diagonal $Q_{ii}x_i^2$ contribution is first replaced by $Q_{ii}x_i$ because $x_i\in\{0,1\}$, so it enters the corresponding linear coefficient $h_i$ rather than the two-variable substitution.

On a basis state, $Z_i$ has eigenvalue $1-2x_i$, so substitution back into the last expression recovers $f(x)$ exactly. The factor $e^{-i\gamma\alpha I}$ is a global phase and can be omitted from the circuit. The classical score must still restore $\alpha$. For example, dividing an expected value and optimum by their shifted values gives $(F+\alpha)/(f^*+\alpha)$, which is generally not $F/f^*$; a ratio is not invariant under an objective offset.

2. Solve one edge at depth one

For $C=(I-Z_1Z_2)/2$, start from $\lvert++\rangle$ and use $U_B(\beta)U_C(\gamma)$. Derive the expected cut and evaluate the complete output distribution at $(\gamma,\beta)=(\pi/2,\pi/8)$.

Solution

After the phase separator,

$$U_C(\gamma)\lvert++\rangle =\frac12\left( \lvert00\rangle+e^{-i\gamma}\lvert01\rangle +e^{-i\gamma}\lvert10\rangle+\lvert11\rangle \right).$$

Conjugating $Z_1Z_2$ by the two $X$ rotations, or multiplying the four amplitudes, gives

$$F_1(\gamma,\beta) =\frac12+\frac12\sin(4\beta)\sin\gamma.$$

At the stated angles both sine factors equal one, so $F_1=1$. Because the score is binary, expectation one already implies zero probability on the uncut strings. Direct amplitude evaluation gives

$$P(00)=P(11)=0, \qquad P(01)=P(10)=\frac12.$$

The result depends on applying $U_C$ first. If the rightmost order or a generator sign is changed, the same numerical angles cannot be assumed to remain optimal.

3. Optimize the regular-graph formula

Starting from the triangle-free $d$-regular depth-one expression, find a representative optimum for $d\ge2$ in the positive branch and derive the expected cut fraction. Explain its relation to the expected approximation ratio when the optimum is unknown.

Solution

For positive $\sin\gamma\cos^{d-1}\gamma$, maximize $\sin(4\beta)$ by choosing $\beta=\pi/8$. Differentiating the remaining factor gives

$$\frac{d}{d\gamma} \left(\sin\gamma\cos^{d-1}\gamma\right) = \cos^{d-2}\gamma(1-d\sin^2\gamma).$$

The interior maximum has $\sin\gamma=1/\sqrt d$ and $\tan\gamma=1/\sqrt{d-1}$. Hence

$$\frac{F_1}{\lvert E\rvert} =\frac12+ \frac{1}{2\sqrt d} \left(1-\frac1d\right)^{(d-1)/2}.$$

This is the expected fraction of all edges cut by the ideal depth-one distribution under the stated simple, unweighted, triangle-free, regular hypotheses. An approximation ratio instead divides by the instance optimum, which need not equal $\lvert E\rvert$. Since $0<C^*\le\lvert E\rvert$, the cut fraction is a lower bound on the ratio, and the two coincide for bipartite graphs. The $d=1$ case is obtained separately from the isolated-edge formula as $\gamma\to\pi/2$.

4. Reproduce the K₃,₃ distribution

Enumerate the 64 basis strings of $K_{3,3}$, propagate the declared depth-one state at $\beta=\pi/8$ and $\gamma=\arctan(1/\sqrt2)$, and recover the expectation, optimum probability, six probability buckets, and repetitions required for a $0.99$ optimum hit.

Solution

Apply $e^{-i\gamma C(z)}$ to each uniform initial amplitude and then apply $e^{-i\beta X}$ pairwise on each of the six bit axes. Summing $P(z)C(z)$ gives

$$\begin{aligned} F_1&=\frac92+\sqrt3\approx6.232051,\\ \frac{F_1}{9}&\approx0.692450. \end{aligned}$$

Grouping by cut value reproduces the six probability rows in the table above.

Their degeneracies are $(2,12,18,18,12,2)$ and the exact probabilities sum to one. Brute force finds $C^*=9$, so $q\approx0.334202$. Therefore

$$R=\left\lceil\frac{\log0.01}{\log(1-q)}\right\rceil=12.$$

Eleven and twelve draws give hit probabilities $0.988604$ and $0.992412$, respectively. The graph is an exactly soluble illustration: its bipartition already gives a classical optimum.

5. Prove that an XY mixer preserves Hamming weight

Prove $[B_{XY},N_1]=0$. Then explain why this conservation law does not by itself show that the mixer reaches every weight-$k$ bitstring.

Solution

For one mixer edge,

$$\frac12(X_iX_j+Y_iY_j) =\sigma_i^+\sigma_j^-+\sigma_i^-\sigma_j^+.$$

Each summand moves one excitation from one endpoint to the other, so it commutes with the pair number $n_i+n_j$, where $n_i=(I-Z_i)/2$. It also commutes with every $n_k$ off that edge. Summing over mixer edges gives

$$[B_{XY},N_1]=0.$$

Thus every $e^{-i\beta B_{XY}}$ preserves each fixed-weight subspace. But a conserved subspace can contain disconnected dynamical sectors. If the mixer graph has two components, the excitation count in each component is conserved separately, so strings with different component-wise counts cannot mix. If the mixer graph is connected, edge exchanges generate paths between any two weight-$k$ strings; this removes that particular disconnected-component obstruction. It does not imply arbitrary state preparation or efficient optimization. The exchange-symmetric three-state example in the text shows the additional restriction imposed by a common symmetry of the initial state and both generators.

6. Compare estimation shots with hit-probability repetitions

For normalized scores, compute the Hoeffding allocation for $\epsilon=0.025$ and $\delta=0.05$. Contrast it with the repetitions needed to sample a $K_{3,3}$ optimum with probability at least $0.99$.

Solution

Hoeffding’s bound requires

$$S\ge \left\lceil \frac{\log(2/0.05)}{2(0.025)^2} \right\rceil =2952$$

shots to guarantee the fixed-state normalized mean is within $0.025$ with failure probability at most $0.05$. For the calculated optimum probability $q\approx0.334202$, independent best-of-$R$ solution sampling needs

$$R\ge \frac{\log0.01}{\log(1-q)},$$

so $R=12$. The smaller number does not estimate the mean accurately; it only controls whether at least one threshold event occurs when $q$ is already known. In an optimization run, estimating $q$, selecting angles and assessing the selected state consume additional fresh samples. If $q=0$, retries cannot help; if $q=1$, one draw suffices.

7. Count logical and compiled MaxCut resources

Count interactions, rotations, and ideal all-to-all depths for level-$p$ QAOA on $K_{3,3}$. Compare native $ZZ$ gates with a CNOT–$R_z$–CNOT decomposition, and identify the hypothesis behind the general $\chi'(G)\le\Delta+1$ bound.

Solution

$K_{3,3}$ has $n=6$, $m=9$, maximum degree three, and an edge coloring with three matchings. Per level it therefore uses nine logical edge interactions and six mixer rotations. With native $ZZ$ gates, the cost has two-qubit depth three; adding the parallel mixer gives logical alternating depth four, hence counts $9p$, $6p$, and depth $4p$ over $p$ levels.

The CNOT–$R_z$–CNOT form uses $18p$ CNOTs. The two CNOT rounds for each matching are sequential, giving ideal entangling depth $6p$, plus the single-qubit $R_z$ and mixer scheduling. A native implementation instead uses $9p$ two-qubit gates at two-qubit depth $3p$.

For a general simple graph, Vizing’s theorem supplies $\chi'(G)\le\Delta+1$. $K_{3,3}$ attains the sharper bipartite value $\chi'=\Delta=3$. Neither statement includes routing, crosstalk restrictions, orientation, calibration, shots, or optimizer evaluations.

8. Bound success from a mean score

Suppose an integer score satisfies $0\le C\le m$, and success means $C\ge\tau$, where $1\le\tau\le m$. Derive upper and lower bounds on $q=\Pr(C\ge\tau)$ from its mean $F$. Then construct two distributions with mean five and maximum possible score nine but different optimum probabilities.

Solution

Successful scores are at least $\tau$, while unsuccessful scores are at most $\tau-1$. Therefore

$$\tau q\le F\le mq+(\tau-1)(1-q).$$

Rearrangement gives

$$\max\!\left(0,\frac{F-\tau+1}{m-\tau+1}\right) \le q\le \min\!\left(1,\frac F\tau\right).$$

The integer-score assumption is essential to the $\tau-1$ bound. For a real-valued score, use the appropriate upper bound on scores that fail the threshold.

One distribution assigns probability one to score five. Another assigns probability $5/9$ to score nine and $4/9$ to score zero. Both have mean five, but their optimum probabilities are zero and $5/9$. These are probability examples rather than an assertion that both are attainable in a particular QAOA family. They show why a mean alone cannot determine the number of retries needed to obtain an optimum.

References

• V. Akshay, H. Philathong, M. E. S. Morales, and J. D. Biamonte, “Reachability Deficits in Quantum Approximate Optimization,” Physical Review Letters 124, 090504 (2020), doi:10.1103/PhysRevLett.124.090504.
• S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, “Obstacles to Variational Quantum Optimization from Symmetry Protection,” Physical Review Letters 125, 260505 (2020), doi:10.1103/PhysRevLett.125.260505.
• E. Farhi, D. Gamarnik, and S. Gutmann, “The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples,” arXiv:2005.08747 [quant-ph] (2020), doi:10.48550/arXiv.2005.08747.
• E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm,” arXiv:1411.4028 [quant-ph] (2014), doi:10.48550/arXiv.1411.4028.
• E. Farhi and A. W. Harrow, “Quantum Supremacy through the Quantum Approximate Optimization Algorithm,” arXiv:1602.07674 [quant-ph] (2016), doi:10.48550/arXiv.1602.07674.
• M. X. Goemans and D. P. Williamson, “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming,” Journal of the ACM 42, 1115–1145 (1995), doi:10.1145/227683.227684.
• S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, “From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz,” Algorithms 12, 34 (2019), doi:10.3390/a12020034.
• M. P. Harrigan et al., “Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor,” Nature Physics 17, 332–336 (2021), doi:10.1038/s41567-020-01105-y.
• M. B. Hastings, “Classical and Quantum Bounded Depth Approximation Algorithms,” Quantum Information & Computation 19, 1116–1140 (2019), doi:10.26421/QIC19.13-14-3.
• Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, “Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View,” Physical Review A 97, 022304 (2018), doi:10.1103/PhysRevA.97.022304; corrected expression in arXiv:1706.02998v2.
• D. Wecker, M. B. Hastings, and M. Troyer, “Progress towards Practical Quantum Variational Algorithms,” Physical Review A 92, 042303 (2015), doi:10.1103/PhysRevA.92.042303.
• L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, “Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices,” Physical Review X 10, 021067 (2020), doi:10.1103/PhysRevX.10.021067.