betaFeedback

WorksPhysics and Astronomy

QAOA Inside ADMM: Subproblem Wins Do Not Become Decomposition Wins at Matched Budgets

Abstract

We benchmark the quantum approximate optimization algorithm (QAOA) as the binary subproblem solver in a two-block alternating direction method of multipliers (ADMM) for mixed-binary problems against classical solvers under matched budgets. With 23 optimizer evaluations per subproblem, scoring determines the comparison: on its final readout, the optimized QAOA loses to random search at n=12n=12 and 16 binary variables (inconclusive at 20; exploratory and post hoc tests). When credited with its best sample, it wins. In a noiseless 12-qubit simulation, transferred-angle depth-2 QAOA finds the exact optimum of 97.3% of planted-family subproblems, against 50.6%–67.4% for the four strongest local heuristics (100% against 90.4%–94.4% crediting the four best bitstrings) and a not significantly different 96.5% for semidefinite rounding with local search (SDP+LS). Under our evaluation-counting convention, its time to solution there is a factor of three to five below the local heuristics' but grows with a larger exponent; it is ten times that of SDP+LS and, in seconds, 54 times that of tabu search with restarts. For the benchmark class, an unconstrained binary quadratic problem in disguise, ADMM's binary step is a proximal step on the reduced problem: at unit penalty ADMM re-solves it, and for larger penalties exact solutions increasingly stall. On two families that do not reduce to one, less accurate solvers found the problem optimum more often at unit and larger penalties. No family gave QAOA a better ADMM outcome than the best classical solver and penalty. The benchmark includes a correctness gate and a log of its hypothesis tests.

Introduction

Decomposition methods are a standard route to large mixed-binary problems, such as unit commitment in power systems [1], because they split a problem into continuous and combinatorial parts that can be solved separately. The alternating direction method of multipliers (ADMM) [2] is among the most widely used, also as a heuristic for mixed-integer programs [3]. Gambella and Simonetto [4] showed that its binary update, a quadratic unconstrained binary optimization (QUBO) subproblem, can be delegated to a quantum heuristic once per outer iteration, a role for which the quantum approximate optimization algorithm (QAOA) [5] is a leading near-term candidate [6]–[9].

Whether the quantum subroutine is worth its cost is an open question. Benchmarks consistently show that the answer depends on how cost and quality are accounted for [10]–[14], and we find one accounting choice to be decisive. A QAOA run draws hundreds of bitstrings while optimizing its angles, yet its output can be the best bitstring of a short final read-out. The Qiskit Optimization tutorial (version 0.7.0) for the ADMM heuristic of [4] does this: it builds the QUBO solution from the final sampled state (eigenstate), not from the best bitstring measured during optimization (best_measurement) [15], [16]; with the tutorial’s sampler (1,024 shots per circuit call by default), this read-out is a single call’s shots. Simulated annealing (SA) and random search, in contrast, are credited with their best evaluation. Under a matched budget, this asymmetry reverses the comparison, as we show.

Without the asymmetry, the question is which QAOA protocol best uses a fixed budget. Per-instance angle optimization spends most of its evaluations searching a noisy parameter landscape, whereas angles trained once on small instances and reused [17], [18] make every evaluation a candidate solution; ADMM, whose subproblems change at every outer iteration, is a demanding test of such transferability. Solvers are judged at two levels, kept separate throughout: by the QUBO solutions they return within their budget (subproblem level) and by the best feasible solution of the original problem that ADMM finds with them (ADMM level). We study the fixed-penalty two-block scheme (Algorithm 1) on problem (1), an instance of the quadratic-plus-convex class of [4] whose continuous variables can be eliminated so that every ADMM run can be checked against the exact optimum.

In every family tested, some classical configuration of solver and penalty found the optimum of the original problem at least as often as the best QAOA configuration. The paper makes four contributions.

  1. The scoring rule decides the comparison. With a small training budget of 23 optimizer evaluations per subproblem, optimized QAOA loses to random search under final-read-out scoring and wins under best-sample scoring of the same logged runs, at n=12n = 12 for every tested ADMM penalty ρ\rho from 0.5 to 4 and at n=16n = 16 and 20 for ρ=2\rho= 2 (inconclusively at n=20n = 20, uncorrected P=0.041P = 0.041; the read-out tests are exploratory and, except at n=12n = 12 and ρ=2\rho= 2, post hoc). By Proposition 1, read-out scoring requires the final state to amplify every small good set roughly B/R\mathcal{B}/R-fold over uniform sampling (budget B\mathcal{B}, read-out size RR). This is an accounting caution for this regime, not a QAOA property.

  1. Transferred angles against tuned classical solvers. Depth-2 transferred-angle QAOA matches seven classical solvers, three of them tuned, on the benign main family. On a Wishart planted family [19], it finds the exact optimum more often than tuned tabu search with restarts, tuned parallel tempering (PT), tuned SA, and local search, also when near-degenerate competitors are credited. Its time-to-solution is shorter than theirs by a prefactor in evaluations (charging tabu search and local search nn evaluations per neighborhood scan), but it grows with a larger exponent, has no advantage over semidefinite-programming (SDP) rounding with local search (SDP+LS), and is much larger in seconds.

  1. What ADMM’s binary step solves. Theorem 1 shows that after the first iteration, the binary subproblem is a proximal step on the reduced problem and characterizes the bitstrings at which exact subproblem solutions stall. A penalty sweep is consistent with every prediction that a finite run can test. In two mixed-binary families outside the theorem, on one of which QAOA was among the most accurate subproblem solvers, less accurate solvers found the problem optimum more often for ρ≥1\rho\ge1.

  1. A benchmark protocol with a correctness gate. The benchmark includes a gate at the matrix, circuit, and sampling levels and a log of its hypothesis tests with cluster-adjusted inference, and we report a circuit-sampler limitation that the gate did not test (§ 5-C).

Fig. 1 summarizes the method. Section II reviews related work, Sections III and IV give the problem and analytical results, § 5 and § 6 the benchmark, § 7 the results, and Sections VIII to § 10 the discussion, limitations, and conclusions. The Appendix gives the proofs.

QAOA and ADMM for Mixed-Binary Problems

Gambella and Simonetto [4] introduced multiblock ADMM heuristics that delegate the binary block of quadratic-plus-convex mixed-binary problems to a variational quantum eigensolver [20] or to QAOA. Such hybrids have been applied to transaction settlement [21] and unit commitment [1], but to our knowledge, none compares the quantum subroutine with classical solvers at a matched budget. Over a nonconvex set such as {0,1}n\{0,1\}^{n}, ADMM is a heuristic, used with restarts because it may converge to suboptimal points [3]. Convergence analyses of nonconvex ADMM require a penalty large relative to the smoothness modulus of the continuous block [22, 23]; Theorem 1 uses the same first-order identity to show that, for the binary block, a large penalty enlarges the set of suboptimal stalling points.

Benchmarking QAOA Against Classical Solvers

QAOA has been compared with quantum and simulated annealing [12], unstructured search [24], and classical MaxCut heuristics by the samples needed to reach a given quality, a measure that credits QAOA with its best sample [14]; it has also been calibrated against the classical effort matching its quality [25]. Hybrid variational heuristics were far less efficient than classical solvers on small instances [26], quantum annealing outperformed short-depth QAOA on 127-qubit higher-order Ising models [13], and QAOA with amplitude amplification showed a scaling advantage over exact solvers on low-autocorrelation binary sequences [27]. Application-oriented suites weigh solution quality against execution cost [10] and provide hard instances [11]. Meaningful scaling exponents require each solver’s run length to be optimized at every size [28, 29], and stochastic algorithms need explicit budgets and replication [30]. To our knowledge, no prior work shows that the choice between read-out and best-sample scoring reverses a matched comparison.

Fixed, Concentrated, and Transferred Angles

At fixed angles, the QAOA objective concentrates over typical instances [17], optimal angles concentrate as size grows [18], and fixed angles are near optimal for MaxCut on regular graphs [31]. Angles transfer between weighted MaxCut instances [32], aided by weight rescaling [33], which motivates our normalization; structured initializations exploit the same regularities [34]. The success-probability decay of fixed-angle QAOA has been compared with classical solvers on random kk-SAT [35] and for linear-ramp schedules [36]. On MaxCut, local classical algorithms match or exceed the performance of bounded-depth QAOA, which sees only a neighborhood of each variable [37, 38, 39]; we therefore compare the scaling of QAOA with that of local heuristics.

Angle Optimization and Classical Baselines

The classical optimizer strongly affects QAOA [40]: conditional value-at-risk (CVaR) aggregation [41] and warm starts [42] are common remedies, whereas shot noise [43] and barren plateaus [44] limit any optimizer. Among classical baselines, the Goemans–Williamson (GW) relaxation [45] guarantees an expected ratio of 0.878 for MaxCut with nonnegative weights. Relaxation-based and local-search heuristics, including tabu search, are among the strongest for MaxCut and QUBO [46, 47], and parallel tempering [48, 49] is the standard spin-glass sampler. QAOA has also been run on superconducting processors [50]. We compare solvers in noiseless simulation, with a check under depolarizing noise, and use a quantum processor only to measure the device time per shot.

Problem Formulation

ADMM for Mixed-Binary Optimization

We consider an instance of the quadratic-plus-convex mixed-binary class studied in [4],

min⁡x∈Rn, z∈{0,1}n12∥x∥22−cTx+zTQzs.t.x+Bz=b,(1)\min_{x\in\mathbb{R}^{n},\,z\in\{0,1\}^{n}} \frac{1}{2}\lVert x\rVert_{2}^{2}-c^{\mathsf{T}}x+z^{\mathsf{T}}Qz \quad\mathrm{s.t.}\quad x+Bz=b, \tag*{(1)}

with Q,B∈Rn×nQ,B\in\mathbb{R}^{n\times n}, QQ symmetric, and c,b∈Rnc,b\in\mathbb{R}^{n}. With penalty ρ>0\rho>0 and dual variable λ\lambda, the augmented Lagrangian is Lρ(x,z,λ)=12∥x∥22−cTx+zTQz+λT(x+Bz−b)+ρ2∥x+Bz−b∥22L_{\rho}(x,z,\lambda)=\frac{1}{2}\lVert x\rVert_{2}^{2}-c^{\mathsf{T}}x+z^{\mathsf{T}}Qz+\lambda^{\mathsf{T}}(x+Bz-b)+\frac{\rho}{2}\lVert x+Bz-b\rVert_{2}^{2}. Each iteration updates zz, then xx, then λ\lambda (Algorithm 1). For fixed (xk,λk)(x^{k},\lambda^{k}) the zz-update is the QUBO

zk+1∈arg⁡min⁡z∈{0,1}nzTQρz+(hk)Tz,(2)z^{k+1}\in\arg\min_{z\in\{0,1\}^{n}} z^{\mathsf{T}}Q_{\rho}z+(h^{k})^{\mathsf{T}}z, \tag*{(2)}
Qp=Q+ρ2BTB,hk=BTλk+ρBT(xk−b),(3)Q_p = Q + \frac{\rho}{2}B^{\mathsf{T}}B,\qquad h^k = B^{\mathsf{T}}\lambda^k + \rho B^{\mathsf{T}}(x^k-b), \tag*{(3)}

followed by xk+1=(c−λk−ρ(Bzk+1−b))/(1+ρ)x^{k+1} = (c-\lambda^k-\rho(Bz^{k+1}-b))/(1+\rho) and λk+1=λk+ρ(xk+1+Bzk+1−b)\lambda^{k+1}=\lambda^k+\rho(x^{k+1}+Bz^{k+1}-b), starting from x0=λ0=0x^0=\lambda^0=0. Because hkh^k changes at every iteration, the solver faces a new QUBO each time. For any zz, the point x=b−Bzx=b-Bz is feasible, so every iterate zkz^k defines a feasible solution of (1). Eliminating xx gives the reduced objective

F(z)=12∥b−Bz∥2−cT(b−Bz)+zTQz,(4)F(z)=\frac{1}{2}\lVert b-Bz\rVert^2-c^{\mathsf{T}}(b-Bz)+z^{\mathsf{T}}Qz, \tag*{(4)}

itself a QUBO. Problem (1) is therefore a QUBO in disguise: an exact or heuristic QUBO solver applied to FF solves it directly. We study it because it is the class of [4] and because enumeration yields its global optimum for the sizes studied, thereby enabling the ADMM-level verification of Section VII-G. Theorem 1 relates (2) to (4). Algorithm 1 returns the best feasible iterate, z†=arg⁡min⁡1≤k≤KF(zk)z^\dagger=\arg\min_{1\leq k\leq K}F(z^k) with x†=b−Bz†x^\dagger=b-Bz^\dagger. Section VIII-H also studies two families that do not reduce to a QUBO.

Algorithm 1 ADMM with a QUBO subproblem solver

Require: Q,B,c,bQ,B,c,b; penalty ρ\rho; iterations KK; subproblem solver SS with budget B\mathcal{B}

  1. x0←0,λ0←0x^0\leftarrow0,\lambda^0\leftarrow0

  2. for k=0,1,…,K−1k=0,1,\ldots,K-1 do

  3. Qp←Q+ρ2BTB, hk←BTλk+ρBT(xk−b)Q_p\leftarrow Q+\frac{\rho}{2}B^{\mathsf{T}}B,\ h^k\leftarrow B^{\mathsf{T}}\lambda^k+\rho B^{\mathsf{T}}(x^k-b)

  4. zk+1←S(Qp,hk;B)z^{k+1}\leftarrow S(Q_p,h^k;\mathcal{B}) ▹\triangleright QUBO (2)

  5. xk+1←(c−λk−ρ(Bzk+1−b))/(1+ρ)x^{k+1}\leftarrow(c-\lambda^k-\rho(Bz^{k+1}-b))/(1+\rho)

  6. λk+1←λk+ρ(xk+1+Bzk+1−b)\lambda^{k+1}\leftarrow\lambda^k+\rho(x^{k+1}+Bz^{k+1}-b)

  7. δk+1←∥xk+1+Bzk+1−b∥2\delta^{k+1}\leftarrow\lVert x^{k+1}+Bz^{k+1}-b\rVert_2 ▹\triangleright primal residual

  8. end for

  9. return best feasible iterate (b−Bz†,z†)(b-Bz^\dagger,z^\dagger), z†=arg⁡min⁡1≤k≤KF(zk)z^\dagger=\arg\min_{1\leq k\leq K}F(z^k)

QAOA and the Cost Hamiltonian

Writing zi=(1−si)/2z_i=(1-s_i)/2 with si∈{±1}s_i\in\{\pm1\} gives the cost C(z)=zTQpz+hTzC(z)=z^{\mathsf{T}}Q_pz+h^{\mathsf{T}}z as

C(s)=const+∑i(−hi2−Qp,ii2)si−∑i<jQp,ij+Qp,ji4(si+sj)+∑i<jQp,ij+Qp,ji4sisj,(5)C(s)=\mathrm{const}+\sum_i\left(-\frac{h_i}{2}-\frac{Q_{p,ii}}{2}\right)s_i-\sum_{i<j}\frac{Q_{p,ij}+Q_{p,ji}}{4}(s_i+s_j)+\sum_{i<j}\frac{Q_{p,ij}+Q_{p,ji}}{4}s_is_j, \tag*{(5)}

whose operator form, with si↦Zis_i\mapsto Z_i, defines the cost Hamiltonian HCH_C. Every off-diagonal coupling contributes a linear term to both of its spins. An implementation that updates only one accumulator per ordered pair halves these terms; we found this defect in our initial implementation, where the ground state of the defective Hamiltonian differed from the true optimum of the first subproblem on 66 of 80 test instances. QAOA of depth pp prepares

∣γ,β⟩=UM(βp)UC(γp)⋯UM(β1)UC(γ1)∣+⟩⊗n,(6)\lvert\gamma,\beta\rangle=U_M(\beta_p)U_C(\gamma_p)\cdots U_M(\beta_1)U_C(\gamma_1)\lvert+\rangle^{\otimes n}, \tag*{(6)}

with UC(γ)=e−iγH~CU_C(\gamma)=e^{-i\gamma\widetilde{H}_C}, UM(β)=e−iβHMU_M(\beta)=e^{-i\beta H_M}, and HM=∑iXiH_M=\sum_iX_i, where H~C=HC/σ\widetilde{H}_C=H_C/\sigma and σ\sigma is the root-mean-square of the non-identity Pauli coefficients of HCH_C (σ=1\sigma=1 in the unnormalized variant). The normalization makes angle scales comparable across subproblems with different energy scales [33].

Normalized Gap

For a subproblem with optimum C∗C^*, mean cost Cˉ\bar{C} over all 2n2^n bitstrings, and maximum Cmax⁡C_{\max}, the normalized gap of a bitstring zz is

gunif(z)=C(z)−C∗Cˉ−C∗,(7)g_{\mathrm{unif}}(z) = \frac{C(z)-C^*}{\bar{C}-C^*}, \tag*{(7)}

which is 0 at the optimum, 1 for the expected result of a single uniform guess, and at most G=(Cmax⁡−C∗)/(Cˉ−C∗)G=(C_{\max}-C^*)/(\bar{C}-C^*). For a distribution over bitstrings, gˉ\bar{g} denotes its mean normalized gap, so that gˉ=1\bar{g}=1 for the uniform distribution.

Analytical Results

This section states three results in terms of Algorithms 1 and 2; Section VII tests each, and the Appendix gives the proofs. Propositions 1 and 2 are elementary consequences of independent sampling; we state them because they set the quantitative bars that the experiments test.

Scoring Rules and Sampling Budgets

Call a set Ω\Omega of bitstrings good (for example, all bitstrings whose normalized gap is at most some threshold), and let uu be the fraction of all 2n2^n bitstrings that lie in Ω\Omega. Random search with budget B\mathcal{B} finds Ω\Omega with probability 1−(1−u)B1-(1-u)^{\mathcal{B}}. We ask what the final QAOA state must achieve to do as well when only its read-out is scored.

Proposition 1 (Read-out scoring raises the bar): Let the QAOA solver of Algorithm 2 use budget B\mathcal{B} with a read-out of RR shots drawn independently from its final state, and let that state place probability π\pi on a good set Ω\Omega. Then:

(a) the best-sample output is never worse than the read-out output;

(b) the read-out finds Ω\Omega at least as often as random search if and only if

π≥1−(1−u)B/R≈BRu,(8)\pi\ge1-(1-u)^{\mathcal{B}/R} \approx\frac{\mathcal{B}}{R}u, \tag*{(8)}

where the approximation holds when (B/R)u(\mathcal{B}/R)u is small, and the exact threshold always lies between 0.63(B/R)u0.63(\mathcal{B}/R)u and (B/R)u(\mathcal{B}/R)u once (B/R)u≤1(\mathcal{B}/R)u\le1;

(c) if all B\mathcal{B} shots are drawn from one state and the best sample is scored, as with transferred angles, the condition is only π≥u\pi\ge u.

In words, read-out scoring requires the final state to amplify every small good set by roughly B/R\mathcal{B}/R over uniform sampling (larger sets by the smaller factor of the exact threshold), whereas best-sample scoring with fixed angles requires no amplification to match random search. In the main protocol, B/R=768/32=24\mathcal{B}/R=768/32=24. Because the expected gap equals ∫0GPr⁡[miss Ωt] dt\int_0^G \Pr[\mathrm{miss}\ \Omega_t]\,\mathrm{d}t with Ωt={z:gunif(z)≤t}\Omega_t=\{z:g_{\mathrm{unif}}(z)\le t\}, the mean-gap comparison integrates (8) over all thresholds. The per-set condition is therefore sufficient but not necessary for matching random search in the mean gap, and a state can pass it for the optimum yet lose on the mean gap.

Proposition 2 (Success of fixed-angle sampling): If a fixed state places probability qq on the optimal bitstrings and is sampled B\mathcal{B} times independently, the optimum is missed with probability

(1−q)B≤e−qB,(9)(1-q)^{\mathcal{B}}\le e^{-q\mathcal{B}}, \tag*{(9)}

and the expected normalized gap of the best sample is at most G(1−q)BG(1-q)^{\mathcal{B}}. Hence q≥ln⁡(1/ϵ)/Bq\ge\ln(1/\epsilon)/\mathcal{B} guarantees that the optimum is found with probability at least 1−ϵ1-\epsilon.

For uniform sampling at n=12n=12 with a unique optimum, q=2−12q=2^{-12} and B=768\mathcal{B}=768 give a success probability of 1−(1−2−12)768=0.1711-(1-2^{-12})^{768}=0.171. Success with probability 0.99 requires q≥6.0×10−3q\ge6.0\times10^{-3}, an amplification of the optimum by a factor of about 25 over uniform sampling. At a fixed budget the required amplification doubles with every added variable, so Proposition 2 turns the scaling question into how fast qq decays with nn (Section VII-D).

What the Binary Step of ADMM Solves

Theorem 1 concerns problem (1) as stated: a continuous part 12∥x∥2−CTx\frac{1}{2}\lVert x\rVert^2-C^{\mathsf{T}}x and the coupling x+Bz=bx+Bz=b, with no further constraints on xx.

Theorem 1 (The binary step is a proximal step): Run Algorithm 1 on problem (1) with any subproblem solver and penalty ρ\rho. For every iteration k≥1k\ge1, the QUBO passed to the solver in line 4 is, up to an additive constant,

min⁡z∈{0,1}nF(z)+ρ−12∥Bz−ak∥22,ak=b−xk,(10)\min_{z\in\{0,1\}^n} F(z)+\frac{\rho-1}{2}\lVert Bz-a^k\rVert_2^2,\qquad a^k=b-x^k, \tag*{(10)}

that is, the reduced problem (4) plus a proximal term that pulls BzBz toward the anchor aka^k set by the current iterate. Consequently:

(a) Penalty one. If ρ=1\rho=1, line 4 solves the reduced problem itself at every iteration after the first, so an exact solver finds a global optimum of (1) at the second iteration.

(b) Residual. If line 4 returns the same bitstring zˉ\bar{z} from some iteration on, the residual of line 7 is divided by exactly 1+ρ1+\rho at every subsequent iteration, whether or not zˉ\bar{z} is optimal.

(c) Stalling points. Suppose line 4 is solved exactly, with ties broken in favor of the previous bitstring, and returns zk+1=zˉz^{k+1}=\bar{z}, computed with the anchor aka^k, at some iteration k≥1k\ge1. Then line 4 returns zˉ\bar{z} at every later iteration if and only if

F(zˉ)≤F(z)+ρ−12∥B(z−zˉ)∥22∀z∈{0,1}n.(11)F(\bar{z})\le F(z)+\frac{\rho-1}{2}\lVert B(z-\bar{z})\rVert_2^2\quad\forall z\in\{0,1\}^n. \tag*{(11)}

We call such a zˉ\bar{z} a stalling point; the characterization holds for every ρ>0\rho>0. At ρ=1\rho=1, the stalling points are exactly the global minimizers of FF. For ρ>1\rho>1, every global minimizer is a stalling point, but suboptimal bitstrings can be as well; their excess cost is at most ρ−12∥B(z∗−zˉ)∥22\frac{\rho-1}{2}\lVert B(z^*-\bar{z})\rVert_2^2 for a global minimizer z∗z^*, and the set of stalling points can only grow as ρ\rho increases. For ρ<1\rho<1 a stalling point must be a global minimizer that is sharp, F(z)−F(zˉ)≥1−ρ2∥B(z−zˉ)∥22F(z)-F(\bar{z})\ge\frac{1-\rho}{2}\lVert B(z-\bar{z})\rVert_2^2 for all zz, and there may be none.

For ρ<1\rho<1, the weight in (10) is negative; we keep the name proximal for brevity. An experiment with KK iterations can only observe a bitstring held for its last few iterations, so

Section VII-G checks (11) directly. Our exact solver breaks exact ties by enumeration order, an event of probability zero for the instance distributions used here.

Theorem 1 has three consequences for QAOA-in-ADMM benchmarks. The binary subproblem is a proximally regularized version of the full reduced QUBO, not a smaller problem. A converged residual certifies only that the binary iterate has stopped changing, not that it is good. For ρ>1\rho> 1, an exact subproblem solver never leaves a stalling point once it returns one, whereas a stochastic solver keeps changing zz and may escape. The first step of the proof is the standard first-order identity of nonconvex ADMM analyses [23]; the contribution lies in the characterization of stalling points in part (c) and its dependence on ρ\rho.

Remark 1 (A general quadratic): The proximal form extends to a strongly convex quadratic 12xTHx−cTx\frac{1}{2}x^{\mathsf T}Hx-c^{\mathsf T}x: for k≥1k \ge1 the QUBO of line 4 equals F(z)+12∥Bz−ak∥ρI−H2F(z)+\frac{1}{2}\lVert Bz-a^{k}\rVert_{\rho I-H}^{2} up to a constant, where FF is the corresponding reduced objective and ∥v∥W2=vTWv\lVert v\rVert_{W}^{2}=v^{\mathsf T}Wv is a quadratic form, not a norm when WW is indefinite. The anchor now contracts toward BzˉB\bar{z} by the matrix (H+ρI)−1H(H+\rho I)^{-1}H rather than by the scalar 1/(1+ρ)1/(1+\rho). The residual ratio of part (b) therefore needs not be 1+ρ1+\rho, and of part (c) only the “only if” direction is proved to carry over, with the weight ρI−H\rho I-H in place of (ρ−1)I(\rho-1)I. Part (a) carries over when H=ηIH=\eta I, at ρ=η\rho=\eta (Appendix).

Section VII-H tests two families outside both results.

Benchmark Design

Matched Objective-Evaluation Budget and Scoring

One evaluation is one candidate bitstring whose cost the solver obtains: a measurement shot for QAOA, a proposal for SA, a draw for random search, and a hyperplane rounding for the SDP. Tabu search and local search are charged nn evaluations per scan of the nn one-flip neighbors, although an incremental implementation computes the nn flip differences in O(n)O(n) time. Every solver receives the same budget B\mathcal{B} per subproblem. Because ratios of evaluation counts depend on this convention, we also report wall-clock time (§ 7-F); hardware execution time, compilation, and classical optimizer overhead are not equalized.

We log every shot that QAOA draws, in both angle optimization and readout. Best-sample scoring credits QAOA with the best bitstring sampled anywhere within its budget, exactly as SA and random search are credited with the best of their evaluations; read-out scoring credits QAOA only with the best bitstring of its final read-out, the rule of the Qiskit Optimization path (Section I). Best-sample scoring is the primary choice because it defines every solver’s output consistently. Inside ADMM, the best-sample output updates the iterates, and the read-out is scored on the same trajectory, so the two rules are compared at the subproblem level; the ADMM-level effect of read-out scoring was not measured. If the angle optimizer terminates early, the remainder is spent sampling at the final angles (line 11 of Algorithm 2), so every solver uses exactly B\mathcal{B} evaluations.

Algorithm 2 QAOA subproblem solver with shot logging

Require: QUBO (Qp,h)(Q_p,h); budget B\mathcal{B}; depth pp; mode; read-out size RR; shots per evaluation mm; fixed angles θ⋆\theta^\star

  1. build HˉC=HC/σ\bar{H}_C=H_C/\sigma from (5); L←∅\mathcal{L}\gets\varnothing ▹\triangleright log of all shots

  2. if mode is transferred then

  3. &nbsp;&nbsp;&nbsp;&nbsp;draw B\mathcal{B} shots at θ⋆\theta^\star into L\mathcal{L}; R←L\mathcal{R}\gets\mathcal{L}

  4. else ▹\triangleright mode is optimized

  5. &nbsp;&nbsp;&nbsp;&nbsp;θ←\theta\gets uniform sample from [−π/4,π/4]2p[-\pi/4,\pi/4]^{2p}

  6. &nbsp;&nbsp;&nbsp;&nbsp;while optimizer runs and ∣L∣+m≤B−R|\mathcal{L}|+m\le\mathcal{B}-R do

  7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;draw mm shots at θ\theta into L\mathcal{L}

  8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return their mean cost to the optimizer; update θ\theta

  9. &nbsp;&nbsp;&nbsp;&nbsp;end while

  10. &nbsp;&nbsp;&nbsp;&nbsp;draw RR read-out shots R\mathcal{R} at θ\theta into L\mathcal{L}

  11. &nbsp;&nbsp;&nbsp;&nbsp;draw B−∣L∣\mathcal{B}-|\mathcal{L}| shots at θ\theta into L\mathcal{L} ▹\triangleright top-up

  12. end if

  13. return best-sample output arg⁡min⁡z∈LC(z)\arg\min_{z\in\mathcal{L}}\mathcal{C}(z) and read-out output arg⁡min⁡z∈RC(z)\arg\min_{z\in\mathcal{R}}\mathcal{C}(z)

Solvers

Optimized QAOA runs constrained optimization by linear approximation (COBYLA) [51] (SciPy; initial step 1.0, tolerance 10−410^{-4}) from initial angles uniform on [−π/4,π/4][-\pi/4,\pi/4]: 23 optimizer evaluations of 32 shots, each returning the mean sampled cost, then a 32-shot read-out at the returned angles (B=768\mathcal{B}=768, R=32R=32). The main comparison (Figure 2) adds depths p=1p=1 and 3, the unnormalized Hamiltonian, warm starts from the angles optimized at the previous ADMM iteration, a multi-start variant that splits the budget over four restarts (each 11 evaluations of 16 shots and a 16-shot read-out) and pools their read-outs, and a budget control that uses a quarter of the budget (11 evaluations of 16 shots and a 16-shot read-out).

Figure 2. ADMM-embedded comparison (n=12n = 12, 80 instances, ρ=2\rho= 2, circuit sampler). (a) Normalized gap gunifg_{\mathrm{unif}} under best-sample scoring, mean, and 95% bootstrap interval. (b) Each QAOA protocol under best-sample (filled) and final-read-out scoring (open); dotted lines: SA and random search. “Optimized QAOA” without a depth label is p=2p = 2. Under read-out scoring, most optimized protocols fall to or behind random search; Table II gives independent-draw values for optimized QAOA with p=2p = 2.

Transferred-angle QAOA fixes (γ,β)(\gamma,\beta) in advance and spends the entire budget across one circuit, so its read-out and best-sample scores coincide. Angles are trained on held-out instances of size n∈{6,8,12}n\in\{6,8,12\} at ρ=2\rho=2 by minimizing the mean exact expected normalized gap gg over 36 subproblems (the first, third, and fifth of the exact ADMM trajectories of 12 instances), with Nelder–Mead [52] from one linear-ramp and five random starting points. Planted-family angles are trained likewise on held-out planted instances at n=12n=12, and the time-to-solution study also uses angles retrained at n=16n=16 on 18 subproblems of six held-out instances, starting from the n=12n=12 angles and two random points. Training, a one-time classical cost, is excluded from the matched budget, as is the tuning of the classical solvers.

Classical baselines. SA [53] performs B\mathcal{B} single-bit-flip Metropolis proposals with geometric cooling from T0=2T_0=2 to 0.010.01; SA with restarts splits the budget over four runs, and tuned SA and SA, tuned (ext.) use the configurations with the lowest held-out mean gap on grids of 36 and 125 configurations; on the planted family, tuned SA denotes the extended-grid configuration, which is also selected on a wider grid of 100 configurations also selected. Tabu search flips the best non-tabu bit along a single trajectory, local search runs steepest descent with random restarts, and random search draws B\mathcal{B} uniform bitstrings. The three stronger heuristics, charged by the same convention, are tabu search with restarts [47, 54], which restarts from a random bitstring when its best value stops improving; parallel tempering (PT) [48, 49] with MM replicas, neighbor exchanges after every sweep, and one evaluation per proposal; and SDP+LS, which follows each hyperplane rounding of the relaxation below by steepest descent. Tuned solvers were tuned per family on that family’s held-out subproblems; on the main family, many configurations tie at a held-out mean gap of zero. Ties went to the first configuration in grid order. For the main and planted families, the selected SA has initial temperature, final temperature, and restarts (0.25, 0.005, 16) and (0.5, 0.005, 16) (small grid: (1, 0.1, 4)); tabu search has tenure 3 and 9 and restarts after 6 and 12 non-improving steps; and PT has 8 and 16 replicas on temperature ranges [0.005, 3] and [0.02, 0.3].

For the ADMM subproblems, a general-QUBO SDP relaxation (linear terms absorbed into couplings to an auxiliary spin) is solved anew for every subproblem with CVXPY [55] and the splitting conic solver (SCS) and followed by B\mathcal{B} randomized hyperplane roundings; for couplings of mixed sign, it carries no approximation guarantee. Its solve time is reported, but, like other classical overhead, it is not counted against the evaluation budget.

Sampling of QAOA Shots

QAOA shots are drawn by one of two samplers. The exact-distribution sampler computes the output distribution by statevector simulation and draws from it with a generator that persists across calls, so every call returns fresh, independent shots. The circuit sampler runs the circuit on the Qiskit Aer sampler, which our code created once per subproblem with a fixed seed and which restarted its seeded stream at every call, so every optimizer evaluation and the read-out of a run reused the same uniform random numbers. Shots at nearby angles are therefore correlated, and the 32-shot read-out at the returned angles, which COBYLA selects for their low sampled mean, repeats exactly the shots of the optimizer evaluation there, as a rerun of the first subproblem of five test instances confirmed. Both effects favor read-out over best-sample scoring and thus work against the reversal of § 7-A. The circuit sampler drew the optimized-QAOA arms of the main comparison at ρ=2\rho= 2 (Figure 2), the 40-instance shared-trajectory comparison, and the budget sweep of § 7-A. It also drew studies of optimized QAOA with other optimizers (Nelder–Mead and simultaneous perturbation stochastic approximation [56], CVaR aggregation [41], and linear-ramp initialization [34]), at other sizes, coupling densities, and noise levels, and on MaxCut instances; because common random numbers across calls change the noise that each optimizer sees, we draw no conclusions from these and do not report them. Transferred-angle QAOA, which draws its budget in one call, and every other experiment is unaffected. The penalty sweep repeats the main optimized-QAOA arm on the same instances and seeds with the exact-distribution sampler, with identical classical arms, so at ρ=2\rho= 2 it is an independent-draw replicate. Every solver applied to a subproblem receives the same integer seed, which ensures that the arms’ pseudorandom draws are correlated without evident bias.

Performance Measures

The primary subproblem-level measure is the normalized gap (7) of the solver’s output; we also report the fraction of subproblems solved exactly, Pr⁡[opt]\Pr[\mathrm{opt}]. Exhaustive enumeration provides C∗C^* and C~\widetilde{C} for every subproblem up to n=24n = 24. At the ADMM level, we report the final primal residual, whether the best feasible iterate is a global optimum of (1) (problem optimum found), and the gap between the best feasible objective and that optimum, found by enumerating zz in (4) and normalized as in (7) with FF in place of CC.

Scaling is measured by the time to solution TTS99\mathrm{TTS}_{99}, the number of evaluations needed to find the optimum with probability 0.99, with every solver’s run length optimized at every size [28, 29]. For a sampler placing probability qq on the optimum (transferred QAOA with exact qq, uniform sampling, and SDP rounding with qq estimated from 4,096 roundings), TTS99=ln⁡0.01/ln⁡(1−q)\mathrm{TTS}_{99} = \ln0.01/\ln(1-q). For solvers with a run length, the run budget b∗b^* is chosen per solver, size, and family from 25 values between 8 and 32,768 as the one minimizing the median TTS99\mathrm{TTS}_{99} over 20 held-out instances (256 runs per budget). Each test instance is then scored from 1,024 runs at b∗b^* as b∗ln⁡0.01/ln⁡(1−p^)b^* \ln0.01/\ln(1-\widehat{p}), with p^\widehat{p} the fraction of runs that found the optimum, or as b∗b^*, an upper bound, when every run succeeds; an instance with no successful run is censored. The exponent κ\kappa is the least-squares slope of log⁡2\log_2 of the median against nn, with a bootstrap interval over instances; exponents are compared by a paired bootstrap of the slope difference (4,000 resamples of the test instances). Conversion to seconds uses the measured serial time per evaluation of our Python implementations, with the SDP relaxation charged once per subproblem, and the device time per shot reported by the runtime service at n=12n = 12, which is a lower bound for larger nn.

Experimental Designs and Statistics

ADMM-embedded runs execute K=12K = 12 outer iterations unless stated otherwise, with each solver driving its own trajectory; a seed’s score is the mean over iterations, and comparisons are paired by instance. Shared-trajectory runs score every solver on the identical subproblems of the exact-solver trajectory. Standalone runs score the first subproblem of each instance. Fixed-budget runs score the second subproblem, the first to take the proximal form of Theorem 1, at β=768\beta= 768 for nn from 12 to 24. Direct runs apply a solver once to FF with the total budget KBKB of an ADMM run.

The unit of analysis is the instance. We write PP for PP-values, rr for the matched-pairs rank-biserial effect size of the exact two-sided Wilcoxon signed-rank test [57], with r<0r < 0 meaning the first-named method is better; because accurate solvers produce many ties, we report the number of non-tied pairs, which bounds the smallest attainable PP. Intervals are percentile bootstrap 95% intervals [58]. Because consecutive subproblems on an instance are dependent, the fraction solved exactly is compared at the instance level by the cluster-adjusted McNemar statistic of Obuchowski [59] (P≥5×10−6P \geq5 \times10^{-6} from 2×1052 \times10^5 sign flips beyond 20 discordant instances) and, for equivalence, by two one-sided tests with a margin of 2 percentage points. A lenient secondary criterion, a margin of 0.01 in mean gunifg_{\mathrm{unif}}, places a method among the strong solvers without ranking it. Holm correction [60] is applied within families of comparisons.

The planned comparisons are recorded in a log of 392 tests, with a global Bonferroni threshold computed across all tests; equivalence tests, descriptive McNemar counts, and post hoc comparisons are outside the log. A test is labeled confirmatory when its hypothesis was specified before its experiment was run; only the main-family hypotheses preceded all results, and every time-to-solution test is exploratory. The main comparison was extended from 40 to 80 seeds before its results were analyzed, and no experiment was extended in response to the results. Comparisons outside the log, including the post hoc analyses, are identified as such.

Correctness Verification

Before any experiment, a gate checks the cost Hamiltonian at three levels and halts on failure. At the matrix level, the diagonal of HCH_C plus its offset must equal the exact QUBO cost of every bitstring (n∈{4,6,8,12,16}n \in\{4,6,8,12,16\}). At the circuit level (n∈{4,8,12}n \in\{4,8,12\}), the cost layer with zero mixer angle must prepare e−iγH~C∣+⟩⊗ne^{-i\gamma\tilde{H}_C}|+\rangle^{\otimes n}, and the full p=2p=2 ansatz must reproduce the output probabilities of the independent NumPy simulator used for angle training. At the sampling level (n=8n=8, 40,000 shots), the mean sampled cost must agree with the exact expectation within five standard errors, for both samplers. This check examines a single call and does not test independence across calls, which is why the shared random stream of § 5-C went undetected.

Experimental Setup

ADMM instances draw all entries of QQ uniformly from [−1,1][-1,1] (symmetrized), BB from [−0.7,0.7][-0.7,0.7], and c,bc,b from [−1,1][-1,1], and use ρ=2\rho=2 unless stated otherwise. The planted family takes QQ from the Wishart planted ensemble [19]: Ising couplings J=−WWT/nJ=-WW^{\mathsf{T}}/n with zero diagonal, where the αn\alpha n Gaussian columns of WW (α=0.5\alpha=0.5) are orthogonal to a planted configuration hidden by a random gauge, mapped to a QUBO scaled to unit maximum magnitude and weakly coupled to the continuous block (BB from [−0.05,0.05][-0.05,0.05], c,bc,b from [−0.1,0.1][-0.1,0.1]) so that the subproblems inherit the ensemble’s landscape. Because the Wishart Ising model has no field, only these weak linear terms break its symmetry under complementing every bit, and the complement of each optimum is close to it in cost. The main setting is n=12n=12 with B=768B=768, 18.75% of the search space, which keeps exhaustive verification feasible. Test instances use seeds 0 to 79 (planted: 30000 to 30079); angle training and solver tuning use held-out seeds 5000 to 5011, and the selection of run budgets uses 6000 to 6019 (planted: offset by 30000 in both cases). Simulations use Qiskit 2.5.2 [61], Qiskit Aer 0.17.2, NumPy [62], and SciPy [63]. To convert evaluations to seconds, we executed p=2p=2 circuits of this benchmark at n=12n=12 (4,096 shots each) on the IBM Quantum processor ibm_marrakesh, for which Qiskit Runtime reported 54 s of quantum processing time for the 163,840 shots of a first submission and 73 s for the 204,800 shots of the five jobs of a second submission that reported usage (its sixth job reported none), both including runs with and without dynamical decoupling and twirling, that is, 3.30×10−43.30 \times10^{-4} and 3.56×10−43.56 \times10^{-4} s per shot. We use these executions only for this timing and do not analyze their outputs here (the transpiled circuits contain 526 two-qubit gates, compared with 264 in the logical circuit).

All random number generators are seeded. Our code caches every per-instance result, and each execution after the one that computed it reloads it unchanged, using the same pinned Qiskit versions; all reported results come from executions on Kaggle. Classical timings were obtained in Kaggle’s CPU environment using serial Python implementations; the processor model was not recorded. Post hoc analyses, identified as such, were computed from the cached results without new experiments, except for a rerun of five subproblems that checked the circuit sampler (§ 5-C).

Results

Table 1 summarizes the findings.

QuestionFinding
Does the scoring rule matter?Yes: with 23 optimizer evaluations, optimized QAOA loses to random search under read-out scoring and wins under best-sample scoring of the same runs at n=12n = 12 and 1616 (inconclusive at n=20n = 20; exploratory or post hoc) (Section VII-A).
Do transferred angles solve the subproblems of the main family?Yes: 99.8% to 100% solved exactly with angles trained at n=6n = 6 to 12, equivalent within 2 percentage points to seven classical solvers; at a fixed budget, qq decays as 2−0.33n2^{-0.33n} up to n=24n = 24 at p=2p = 2 (Sections VII-B to VII-D).
Is there an advantage on a rugged planted family?Over local heuristics only (noiseless, p=2p = 2): 97.3% against at most 67.4% solved exactly; fewer evaluations to solution at n=12n = 12 under our convention, but a larger exponent; none over SDP+LS or in seconds (Sections VII-E and VII-F).
Does subproblem accuracy improve the ADMM outcome?No: at ρ=1\rho= 1 ADMM re-solves FF; for ρ>1\rho> 1, exact solutions stall more often; in two non-QUBO families, less accurate solvers found the problem optimum more often for ρ≥1\rho\ge1 (Sections VII-G and VII-H).

Table 1. Findings at a glance.

The Scoring Rule Decides the Comparison

Figure 2 reports the ADMM-embedded comparison on 80 instances at p=2p=2, with QAOA drawn by the circuit sampler. Scored on its final read-out, optimized QAOA (p=2p=2) is significantly worse than random search (r=+0.859r=+0.859 [0.72, 0.96], P<10−10P<10^{-10}); scored on the best bitstring sampled within the same budget, on the same runs, it is significantly better (r=−0.833r=-0.833 [−0.96, −0.68], P<10−10P<10^{-10}, all 80 pairs non-tied) and solves 37.5 percentage points more subproblems exactly (95% CI 32.7 to 42.1). The independent-draw replicate (§ 5-C) shows this more clearly: the read-out loses (r=+0.985r=+0.985, P<10−10P<10^{-10}) and the best sample wins (r=−0.972r=-0.972, P<10−10P<10^{-10}); 46.4 percentage points more subproblems solved exactly, 95% CI 42.0 to 50.6, and the same holds at every penalty from 0.5 to 4 (P<10−10P<10^{-10} for each; Table II; post hoc and outside the test log). The unnormalized protocol reverses in the same way but more weakly (r=+0.42r=+0.42, P=9.5×10−4P=9.5\times10^{-4}), whereas multi-start, whose four pooled 16-shot read-outs halve B/RB/R to 12, beats random search even under read-out scoring (r=−0.50r=-0.50, P=6.4×10−5P=6.4\times10^{-5}), as Proposition 1 allows, although the circuit sampler’s bias toward the read-out (§ 5-C) may inflate this result. Depth (p=1,2,3p=1,2,3) had no detectable effect (Friedman test [64], P=0.99P=0.99), a null result that the circuit sampler makes inconclusive. Under best-sample scoring every QAOA variant except the budget control, which uses a quarter of the budget, beats random search, despite the circuit sampler’s bias against that rule. Only 32 of the 768 evaluations per subproblem enter the read-out, so read-out scoring discards 96% of the samples that the budget pays for.

Proposition 1 explains how read-out scoring can lose on the gap while the final state is far from uniform. With independent draws, as the proposition assumes, the read-out of optimized QAOA contained the optimum more often (21.4% of subproblems) than random search finds it (0.171 in theory, 17.7% observed), so for the optimal set it met, on average over subproblems, the bar that condition (8) sets for each final state. Yet its read-out gap was larger than random search’s (Table II), so for good sets defined by larger gap thresholds, the final states fell short of that bar.

Differing ADMM trajectories do not produce the reversal: on identical subproblems from the exact-solver trajectory (40 instances), optimized QAOA beats random search under best-sample scoring (r=−0.898r = -0.898, P=2.1×10−8P = 2.1 \times10^{-8}) and loses under read-out scoring (mean gunifg_{\mathrm{unif}} 0.127 against 0.093, r=+0.72r = +0.72, P=2.6×10−5P = 2.6 \times10^{-5}, post hoc). Embedded in ADMM at n=16n = 16 and 20 with a fixed budget of 768 evaluations (15 instances, eight ADMM iterations, independent draws, 1.2% and 0.07% of the search space), the read-out had a larger gap than random search at n=16n = 16 (r=+0.917r = +0.917, P=6.1×10−4P = 6.1 \times10^{-4}) and, inconclusively, at n=20n = 20 (r=+0.600r = +0.600, P=0.041P = 0.041; both solved 0.8% of subproblems exactly), and the best sample a smaller gap on all 15 instances at both sizes (P=6.1×10−5P = 6.1 \times10^{-5}; all uncorrected, post hoc, and outside the test log). A circuit-sampled budget sweep at n=12n = 12 from 5% to 45% of the space (30 instances, eight ADMM iterations) shows the reversal at 10% (read-out loss uncorrected, P=0.033P = 0.033), 18.75%, and 45%, with inconclusive nulls for the read-out at 5% (P=0.40P = 0.40) and the best sample at 30% (P=0.21P = 0.21); without the top-up, early termination of COBYLA left up to 29% of the budget unspent.

These results concern the training budget we gave to the optimized QAOA: 23 optimizer evaluations per subproblem in the main comparison and 5–56 in the sweep. A longer optimization could concentrate the final state enough to pass (8); we do not claim that read-out scoring always reverses a comparison. Per-instance optimization is in any case the weak link: every protocol that optimizes the angles from random or warm-started initial values is significantly worse than SA (r≥+0.918r \ge+0.918, P<10−10P < 10^{-10}), and with independent draws optimized QAOA (p=2p = 2) remains far behind SA in mean gap (103gunif10^3 g_{\mathrm{unif}} of 36.8 against 1.96; Table III).

Transferred Angles Solve the ADMM Subproblems

Transferred-angle QAOA (p=2p = 2 and p=3p = 3 alike) found the exact optimum of every subproblem on all 80 instances, 3.4 percentage points more than SA (95% CI 1.8 to 5.3; P=1.5×10−5P = 1.5 \times10^{-5}, 17 non-tied pairs), and is equivalent to the SDP within the lenient margin. Because it solves every subproblem exactly, its ADMM trajectory coincides with that of the exact solver. Training need not use the target size: angles trained at n=6n = 6 and n=8n = 8 solve 99.8% and 99.9% of the n=12n = 12 subproblems exactly, and the three angle sets differ by at most 0.07 rad in any component, consistent with parameter concentration. Angles trained at n=12n = 12 gave a mean gunifg_{\mathrm{unif}} of at most 0.0015 at every size from 6 to 16 (15 instances per size, eight ADMM iterations, budget 18.75% of the search space, 25% at n=8n = 8 and the whole space at n=6n = 6) and solved 99.5% to 100% of the subproblems over every penalty from 0.5 to 4. They also solved every recorded subproblem of the general family exactly.

Stronger Classical Baselines and Cost

Table III adds classical competitors stronger than default SA, including the three stronger heuristics. On the 960 subproblems of the exact-solver trajectory, transferred QAOA is equivalent at the instance level within 2 percentage points (outside the log) to each of seven classical solvers (tabu search with and without restarts, SDP+LS, the SDP, local search, PT, and SA tuned on the extended grid; Figure 3(a)), and no difference in fraction solved exactly survives Holm correction.

Figure 3. Subproblem accuracy on the identical subproblems of the exact-solver ADMM trajectory (n=12n = 12, 80 instances, 960 subproblems per solver, B=768B = 768). (a) Main family: number of the 960 subproblems that each solver did not solve exactly (the axis is cut for optimized QAOA, 354, and random search, 811). (b) Planted (Wishart) family: fraction of subproblems solved exactly, instance-level mean, and 95% bootstrap interval. Optimized QAOA is drawn by the exact-distribution sampler in both panels.

Evaluations are not equally expensive: the classical solvers other than random search took 1.16 to 16.4 ms per subproblem (including the relaxation for the SDP-based ones), whereas 768 shots took 0.253 to 0.274 s at the device’s 3.30×10−43.30 \times10^{-4} to 3.56×10−43.56 \times10^{-4} s per shot (Section VI), so a 768-shot subproblem takes 15 to 237 times longer (Table III, note a), before compilation and job latency.

Scaling at a Fixed Budget

With the budget held at 768 evaluations as nn grows from 12 to 24, where it covers 4.6×10−54.6 \times10^{-5} of the space (Figure 4; second ADMM subproblem; 20 instances per size, 10 at n=22n = 22 and 24), the probability qq of the optimum under the transferred state falls as 2−0.33n2^{-0.33n} for p=2p = 2 and 2−0.27n2^{-0.27n} for p=3p = 3 (least-squares fits over instances), while 2−n2^{-n} falls by a factor of 4,096; the exact success probability at 768 samples stays, in the mean over instances, at or above 0.816 (p=2p = 2) and 0.966 (p=3p = 3). Growing amplification over uniform sampling [24] is nevertheless a low bar on this family: tabu search and the SDP found the optimum on 90% to 100% of instances at every size, against 70% falling to 15% at n=20n = 20 for per-instance optimized QAOA (exact-distribution sampler), and no comparison of transferred QAOA with tuned SA or tabu search was significant (P≥0.31P \ge0.31, at most five non-tied pairs). Section VII-F therefore measures cost at budgets small enough not to saturate.

Figure 4. Fixed budget of 768 evaluations, n=12n = 12 to 24. (a) Probability of the optimum under the transferred p=2p = 2 and p=3p = 3 states and under uniform sampling, mean of log⁡10q\log_{10} q over instances with 95% interval. (b) Fraction of instances on which the optimum was found: exact value for the transferred p=2p = 2 state (dashed, no markers) and one 768-evaluation run per solver (markers).

SettingSamplerPr⁡[opt]\Pr[\mathrm{opt}] BSPr⁡[opt]\Pr[\mathrm{opt}] ROPr⁡[opt]\Pr[\mathrm{opt}] Rand.gunifg_{\mathrm{unif}} BSgunifg_{\mathrm{unif}} ROgunifg_{\mathrm{unif}} Rand.rr (P) ROrr (P) BS
n=12n = 12, ρ=2\rho= 2circuit0.5520.2940.1770.0500.1280.081+0.859 (<10−10< 10^{-10})−0.833 (<10−10< 10^{-10})
n=12n = 12, ρ=0.5\rho= 0.5independent0.5710.1670.1680.0330.1630.078+0.993 (<10−10< 10^{-10})−0.994 (<10−10< 10^{-10})
n=12n = 12, ρ=1\rho= 1independent0.6010.1960.1660.0330.1580.079+0.965 (<10−10< 10^{-10})−0.982 (<10−10< 10^{-10})
n=12n = 12, ρ=1.5\rho= 1.5independent0.6260.2260.1730.0350.1700.081+0.982 (<10−10< 10^{-10})−0.976 (<10−10< 10^{-10})
n=12n = 12, ρ=2\rho= 2independent0.6410.2140.1770.0370.1700.081+0.985 (<10−10< 10^{-10})−0.972 (<10−10< 10^{-10})
n=12n = 12, ρ=3\rho= 3independent0.6300.2730.1500.0370.1570.084+0.952 (<10−10< 10^{-10})−0.983 (<10−10< 10^{-10})
n=12n = 12, ρ=4\rho= 4independent0.6490.2470.1480.0350.1570.088+0.966 (<10−10< 10^{-10})−0.999 (<10−10< 10^{-10})
n=16n = 16, ρ=2\rho= 2independent0.3330.0750.0170.0780.2290.150+0.917 (6.1×10−46.1 \times10^{-4})−1.000 (6.1×10−56.1 \times10^{-5})
n=20n = 20, ρ=2\rho= 2independent0.1420.0080.0080.1140.2580.207+0.600 (0.041)−1.000 (6.1×10−56.1 \times10^{-5})

Table 2. TABLE II Optimized QAOA (p=2p = 2) against random search under the two scoring rules, ADMM-embedded. Pr⁡[OPT]\Pr[\mathrm{OPT}]: fraction of subproblems solved exactly; gunifg_{\mathrm{unif}}: mean normalized gap; each for QAOA under best-sample (BS) and read-out (RO) scoring and for random search; rr: rank-biserial effect of QAOA versus random search (r>0r > 0: QAOA worse), with exact signed-rank PP (all pairs non-tied). Rows 2 to 7: independent-draw replicate on the instances of row 1; last two rows: 15 instances, eight iterations, fixed budget of 768 evaluations.

A Planted Family With a Rugged Landscape

Landscape diagnostics of the second ADMM subproblem and of FF (medians over 80 instances at n=12n = 12 and 20 at $n = 16) show that the main family is easy: its subproblems have 4 single-flip local minima at n=12n = 12 and 7.5 at n=16n = 16, steepest descent from a random start reaches the optimum from 67% and 53% of all starting points, and at n=12n = 12 the Euclidean norm of the linear term hh is 0.79 times the Frobenius norm of the off-diagonal couplings. The planted subproblem have 45 and 204.5 local minima, basins of 6.0% and 2.1%, and a norm ratio of 0.021 at n=12n = 12, so the couplings set the landscape. Table IV and Fig. 3 repeat the comparisons on 80 planted instances. On the identical subproblems of the exact-solver trajectory (960 per solver), transferred QAOA, with angles

trained on held-out planted instances, found the exact optimum on 97.3% of them; SDP+LS (96.5%) and the SDP (93.8%) did not differ significantly from it (cluster-adjusted McNemar P=0.66P = 0.66 and 0.071), whereas every local heuristic was far behind (the four strongest: tabu search restarts 67.4%, local search 60.8%, tuned SA 53.8%, PT 50.6%; all P≤5×10−6P \le5 \times10^{-6}). Embedded in ADMM at ρ=2\rho= 2, the ordering is the same (97.4%, 88.8%, 79.8%, and 48.8% to 67.8% for the four strongest local heuristics), and transferred QAOA had a smaller normalized gap than every local heuristic (P<10−10P < 10^{-10}) and the SDP (P=2.9×10−3P = 2.9 \times10^{-3}); against SDP+LS it was smaller at ρ=1\rho= 1 (P=4.3×10−3P = 4.3 \times10^{-3}) but not at ρ=2\rho= 2 (P=0.40P = 0.40). The planted-family angles were trained at the test size; angles retrained at n=16n = 16 fit about as well but differ by at least 0.52 rad in one component, even after accounting for the symmetries of the QAOA output distribution, so neither transfer across sizes nor parameter concentration is established on this family.

Near-degenerate competitors. The Ising part of a planted subproblem is invariant under complementing all bits, and the symmetry-breaking field is weak, so the exact-optimum criterion also tests whether a solver resolves a few nearly degenerate low-energy states; for QAOA, whose mixer and initial state share the symmetry, only the cost layer can resolve them. We therefore re-scored the shared-trajectory runs from their logged costs by exhaustive enumeration of each subproblem, without rerunning any solver. The complement of the optimum, among the four best bitstrings on 724 of the 960 subproblems (median gunifg_{\mathrm{unif}} over all 960: 0.063), accounted for 22% to 33% of the strongest local heuristics’ misses. These heuristics succeeded on 64.2% to 74.6% of subproblems when it was credited, against 98.2% for transferred QAOA and 96.8% for SDP+LS; on 90.4% to 94.4% when any

of the four best bitstrings was credited, against 100% and 98.8%; and on 95.7% to 98.2% when every bitstring with gunif≤0.1g_{\mathrm{unif}} \le0.1 was credited, against 100%. Transferred QAOA stayed ahead of each under every criterion (instance-level signed-rank P≤4.9×10−4P \le4.9 \times10^{-4}, post hoc and outside the test log) and in mean gap at ρ=2\rho= 2 (Table IV), so its advantage is not an artifact of the criterion. That advantage, however, lies in resolving the best of a handful of nearly degenerate states: under the loosest criterion, the local heuristics missed only 1.8% to 4.3% of the subproblems.

The subproblem advantage did not carry over to the ADMM level. At ρ=1\rho= 1, transferred QAOA, the exact solver, and the four strongest local heuristics found the problem optimum on all 80 instances. At ρ=2\rho= 2, where the exact solver itself

Method103gunif10^3 g_{\mathrm{unif}}Pr[opt]PP vs transferredTime (s)
Transferred p=2p = 20.001.000n/a0.0025a^{a}
Tabu, restarts0.001.0001.0 (0)0.0018
SDP+LS0.001.0001.0 (0)0.016
Local search0.030.9991.0 (1)0.0012
SDP0.080.9940.13 (4)b^{b}0.015
PT0.250.9930.13 (4)0.0070
SA, tuned (small grid)0.440.9930.031 (6)0.011
Tabu0.600.9907.8×10−37.8 \times10^{-3} (8)0.0017
SA, restarts0.610.9832.0×10−32.0 \times10^{-3} (10)0.011
SA1.960.9661.5×10−51.5 \times10^{-5} (17)0.011
QAOA p=2p = 2, optimizedc^{c}50.10.552n/a0.071a^{a}
Random81.20.177<10−10< 10^{-10} (80)0.0002

Table 3. Stronger baselines (n=12n = 12, ADMM-embedded, 80 instances, B=768B = 768, ρ=2\rho= 2). 103gunif10^3 g_{\mathrm{unif}}: mean normalized gap ×103\times10^3; PP: exact signed-rank test of transferred QAOA against the row method on gunifg_{\mathrm{unif}} (non-tied pairs); Time: median wall-clock seconds per subproblem in the Kaggle CPU environment (serial Python implementations).

Methodρ=2\rho= 2ρ=1\rho= 1Sharedρ=2\rho= 2ρ=1\rho= 1ρ=2\rho= 2Direct
\multicolumn{3}{c}{Solved exactly}103gunif10^3 g_{\mathrm{unif}}\multicolumn{3}{c}{Problem optimum}
Transf. p=2p = 20.9740.9730.9731.21.0000.9381.000
Transf. p=3ap = 3^{a}0.9760.973n/a1.11.0000.9381.000
Transf. p=2p = 2, mainb^{b}0.8750.859n/a5.51.0000.975n/a
SDP+LS0.8880.8060.9653.20.9620.8750.912
SDP0.7980.7470.9387.40.8880.7500.788
Tabu, restarts0.6780.6490.67417.41.0000.9751.000
Local search0.6230.5820.60818.71.0000.9501.000
SA, tuned (ext.)0.5410.5050.53823.01.0001.0000.975
PT0.4880.4680.50626.21.0000.9880.988
QAOA p=2p = 2, optim.0.4070.3710.37342.20.9750.962n/a
SA0.3620.329n/a38.10.9751.000n/a
Tabu0.3530.2900.36940.90.9620.9380.262
Random0.1550.1650.16760.00.8880.8750.862
Exact1.0001.0001.0000.01.0000.912n/a

Table 4. Planted family (n=12n = 12, 80 instances, B=768B = 768). Pr[OPT]: fraction of subproblems solved exactly, ADMM-embedded (12 iterations) and on the identical subproblems of the exact-solver trajectory (960 per solver); 103gunif10^3 g_{\mathrm{unif}}: mean normalized gap ×103\times10^3; Problem optimum: fraction of instances on which the best feasible iterate is the global optimum, embedded in ADMM and from a direct solution of FF with KB=9,216KB = 9{,}216 evaluations.

missed it on 8.8% of instances, transferred QAOA found it on 93.8% and the strongest local heuristics on 95.0% to 100%; no logged ADMM-level comparison of transferred QAOA with tabu search with restarts, PT, tuned SA, or SDP+LS was significant (P≥0.0625P \ge0.0625). By Theorem 1(a), every iteration after the first at ρ=1\rho= 1 poses the same QUBO FF, so an ADMM run gives a solver K−1K - 1 attempts at FF.

Time to Solution

Because a single budget of 768 evaluations saturates the classical solvers on the main family, Table V and Figure 5 report TTS99\mathrm{TTS}_{99} on the second ADMM subproblem from n=12n = 12 to 20 (20 test instances per size and family). Transferred QAOA is scored by its exact probability of the optimum in noiseless simulation, with angles trained at n=12n = 12 and, separately, with angles retrained at n=16n = 16. No local-heuristic or QAOA estimate was censored, and on the planted family, no local heuristic succeeded in every run on more than 10% of instances. Tuning the classical solvers' other parameters at n=12n = 12 and keeping them at larger nn favors QAOA in the comparison of exponents.

MethodMain family, evaluations n=12n = 12Main family, evaluations n=20n = 20Main family, evaluations κ\kappaPlanted family, evaluations n=12n = 12Planted family, evaluations n=20n = 20Planted family, evaluations κ\kappaPlanted, secondsa^{a} n=12n = 12Planted, secondsa^{a} n=20n = 20
Transferred p=2p = 2, angles from n=12n = 12898030.37 [0.25, 0.48]92322,0010.57 [0.54, 0.59]0.337.8
Transferred p=2p = 2, angles from n=16n = 16978410.36 [0.25, 0.46]73913,8450.52 [0.49, 0.56]0.264.9
Tabu, restartsb^{b}1928090.29 [0.21, 0.35]2,81723,2640.37 [0.31, 0.43]0.00610.050
SA, tunedc^{c}2921,3080.29 [0.19, 0.40]4,46655,5880.45 [0.39, 0.50]0.0591.1
PTb^{b}5121,5360.22 [0.16, 0.32]4,37852,9500.45 [0.38, 0.49]0.0220.41
Local searchb^{b}3841,6730.28 [0.23, 0.36]3,34650,2890.48 [0.44, 0.53]0.00490.068
SDP+LSd^{d}902870.25 [0.16, 0.32]921,7410.44 [0.30, 0.75]0.0310.11
SDP roundingd^{d}13240.14 [0.06, 0.24]104830.52 [0.05, ∞\infty]0.0310.11
Random18,8604.8×1064.8 \times10^{6}1.0018,8604.8×1064.8 \times10^{6}1.00n/an/a

Table V. TABLE V Time to solution TTS99_{99} (noiseless simulation for QAOA, p=2p = 2) on the second ADMM subproblem (median over 20 test instances), the exponent κ\kappa in TTS99∝2κn_{99} \propto2^{\kappa n} fitted to the medians over n=12n = 12 to 20 with 95% bootstrap interval (an interval reaching ∞\infty contains resamples with a censored median), and the planted-family TTS99_{99} in seconds. a^{a} QAOA: device time per shot measured on ibm_marrakesh at n=12n = 12 (3.56×10−43.56 \times10^{-4} s), applied to the noiseless TTS99_{99}; classical solvers: measured serial time per evaluation of our Python implementations in the Kaggle CPU environment. b^{b} Succeeded in every run on 10% to 60% of main-family instances at the selected budget, so the main-family values are upper bounds. c^{c} One anneal per run, temperatures of the tuned configuration. d^{d} Relaxation excluded from the evaluation count, included in seconds; censored on up to 25% (SDP+LS) and 35% (SDP rounding) of planted instances at some sizes; SDP+LS also succeeded in every run on up to 40% of planted instances, so its planted values are upper bounds as well.

Figure 5. Time to solution on the second ADMM subproblem, n=12n = 12 to 20, 20 test instances per size, for (a) the main and (b) the planted family: log⁡2\log_{2} of the median TTS99_{99} in evaluations; the band shows the 95% bootstrap interval for transferred QAOA. Run budgets of the classical solvers were chosen on held-out instances; SDP-based solvers exclude the relaxation; random search (TTS99∝2n_{99} \propto2^{n}) is omitted.

On the planted family, transferred QAOA needed 923 evaluations at n=12n = 12, three to five times fewer than the local heuristics (P=1.9×10−6P = 1.9 \times10^{-6} against each, the smallest exact PP with 20 pairs), but its cost grew faster, as 20.57n2^{0.57n} against 20.37n2^{0.37n} to 20.48n2^{0.48n}: the paired bootstrap places the excess of its exponent above zero against every local heuristic (by 0.08 to 0.20, P≤0.002P \le0.002), and at n=20n = 20 tabu search with restarts needed about as many evaluations (P=0.28P = 0.28). Angles retrained at n=16n = 16 lowered the exponent to 0.52 and the cost at n=20n = 20 but did not remove the excess against tabu search with restarts, PT, and tuned SA. These values count only the exact optimum; the near-degenerate competitors of § 7-E were not recorded here. The prefactor also depends on the evaluation convention in § 5: tabu search and local search incur nn evaluations per scan, and counting a scan as one evaluation would reduce their counts by up to a factor of nn and could reverse the prefactor in their favor. SDP+LS was the fastest classical solver with a run length on both families: on the planted family, it needed 10 and 13 times fewer evaluations than transferred QAOA at n=12n = 12 and 20, but its median was not monotone in nn and was censored on up to 25% of instances, so its exponent could not be distinguished from that of QAOA. On the main family, the medians of three local heuristics are upper bounds (Table V, note b), so neither the prefactor nor the exponents are resolved there, and we draw no conclusion from them.

The evaluation count also hides the cost of an evaluation: a device shot took 3.56×10−43.56 \times10^{-4} s, a classical evaluation 6.34×10−76.34 \times10^{-7} to 2.05×10−52.05 \times10^{-5} s. In seconds and before any hardware error, transferring QAOA on the planted family took 54 and 157 times longer than tabu search with restarts at n=12n = 12 and 20, and 11 and 72 times longer than SDP+LS, including its relaxation. In noiseless simulation at p=2p = 2, transferred QAOA thus has, on the planted family and under our evaluation convention, a prefactor advantage over local heuristics in evaluations, a larger exponent, and no advantage over SDP-based solvers or in time. This is a statement about p=2p = 2: the decay of the probability of the optimum was slower at p=3p = 3 on the main family and slows with depth in other fixed-angle studies [35], [36].

ADMM-Level Behavior and the Penalty

At the benchmark's penalty ρ=2\rho= 2, subproblem accuracy and the ADMM outcome diverge. With exact, SDP, or transferredangle subproblem solutions, the mean primal residual falls to 3×10−53 \times10^{-5} after 12 iterations, yet the best feasible iterate is the global optimum of (1) on only half of the instances (SA: 55%); optimized QAOA and random search, whose noisy trajectories keep changing zz, find it on 76% and 75% (optimized QAOA with independent draws: 78.8%). In the exact-solver runs, the residual of 79 of the 80 instances is divided by exactly 1+ρ=31 + \rho= 3 at each of the last six iterations, the signature of Theorem 1(b) for a binary iterate that no longer changes; by part (c), that iterate is a stalling point, which at ρ=2\rho= 2 can be suboptimal. Optimized QAOA’s advantage over the exact solver is therefore not a quantum effect; random search, also noisy, matches it.

Theorem 1 predicts that this advantage comes from the penalty. We repeated the embedded comparison on the same 80 instances at ρ∈{0.5,1,1.5,2,3,4}\rho\in\{0.5, 1, 1.5, 2, 3, 4\} (Figure 6). At ρ=1\rho= 1, exact subproblem solutions reached the global optimum by the second iteration on all 80 instances, as part (a) states; SA, tuned SA, transferred QAOA, and optimized QAOA also found it on every instance, random search on 87.5%, and every solver did better than at ρ=2\rho= 2 (P≤2.0×10−3P \le2.0 \times10^{-3} for each). For ρ>1\rho> 1, the exact solver stalled at a suboptimal bitstring increasingly often (31.2%, 50%, 82.5%, and 95% of instances at ρ=1.5\rho= 1.5, 2, 3, and 4), whereas noisy solvers degraded more slowly. As parts (b) and (c) state, every such stall satisfied (11), and the residual ratio equaled 1+ρ1 + \rho to within 10−710^{-7} whenever the bitstring was held. At ρ=0.5\rho= 0.5, no instance stalled at a suboptimal bitstring. For problem (1), the ADMMlevel advantage of noisy solvers at ρ=2\rho= 2 is therefore an artifact of the penalty.

Figure 6. Penalty sweep (n=12n = 12, 80 instances, 12 iterations; QAOA from the exact-distribution sampler). (a) Fraction of instances on which ADMM’s best feasible iterate is the global optimum of (1); the exact and transferred-angle curves coincide, and tuned SA and SA lie within one and four instances of them, respectively, at every penalty. (b) Exact solver: fraction of instances that reached the global optimum by the second iteration and that stalled at a suboptimal bitstring (held over the last three iterations). Means with 95% bootstrap intervals.

Solving the reduced QUBO directly. The natural reference is one solution of FF with the budget of a whole ADMM run, KB=9,216KB = 9{,}216 evaluations. On the main family, the direct solution differed from ADMM at ρ=1\rho= 1 on at most one instance for every solver except random search, and with every accurate solver it beat ADMM at ρ=2\rho= 2 by 38 to 40 instances; on this family, ADMM at ρ=1\rho= 1 thus amounts to a direct solution of FF, and ADMM at ρ=2\rho= 2 did worse. On the planted family, the direct solution found the optimum on every instance with transferred QAOA, local search, and tabu search with restarts, and the decomposition acted mainly as a restart mechanism for single-trajectory tabu search (26.2% directly, 96.2% inside ADMM at ρ=1\rho= 1) and the SDP.

Mixed-Binary Families That Do Not Reduce to a QUBO

To test what survives without the structure of Theorem 1, we generated 80 instances of

min⁡x,z 12xTHx−cTx+zTQzs.t.Ax+Bz=b, ∣xi∣≤1(12)\min_{x,z}\ \frac{1}{2}x^{\mathsf{T}}Hx-c^{\mathsf{T}}x+z^{\mathsf{T}}Qz\quad\text{s.t.}\quad Ax+Bz=b,\ \lvert x_i\rvert\le1 \tag*{(12)}

with z∈{0,1}12z \in\{0,1\}^{12}, x∈R16x \in\mathbb{R}^{16}, eight coupling constraints, a random Gaussian AA, and H=LLT+0.5IH = LL^{\mathsf{T}} + 0.5I with Gaussian LL. ADMM’s xx-update becomes a box-constrained convex quadratic program, the zz-update is still a QUBO, and neither Theorem 1 nor its extension to a general quadratic applies. We obtain the problem optimum from a box-constrained quadratic program for each feasible bitstring. The instances use seeds 10000 to 10079; of the first 40, 36 admit a feasible xx for every zz and all 40 admit one for at least 80% of the bitstrings, every ADMM iterate was feasible, and the box constraint is active at the continuous optimum for a median of 45% of bitstrings.

Transferred angles reproduced the exact solver’s best feasible solution on every instance at every penalty and solved exactly every subproblem whose accuracy was recorded (the first 40 instances, ρ=1\rho= 1 and 2). On those 40 instances, optimized QAOA (exact-distribution sampler) found the problem optimum on 85% and 57.5% at ρ=1\rho= 1 and 2, as often as random search, against 45% and 32.5% for exact solutions. At the ADMM level (Figure 7(a)), however, ρ=1\rho= 1 is no longer special, and accurate solvers do worse as the penalty grows. On all 80 instances, exact subproblem solutions found the problem optimum on 77.5%, 50%, 32.5%, and 8.8% at ρ=0.5\rho= 0.5, 1, 2, and 4, and tabu search with restarts and tuned SA matched them to within one instance; random search found it on 85%, 78.8%, 58.8%, and 31.2% and beat transferred QAOA at ρ=1\rho= 1, 2, and 4 ([3]) but not at ρ=0.5\rho= 0.5 (P=0.59P = 0.59). Restarts, the classical remedy for nonconvex ADMM [3], recover much of this advantage without a randomized subproblem solver: four exact-solver runs of three iterations from random continuous starting points found it on 87.5%, 78.8%, 53.8%, and 15.0%, and transferred QAOA was worse than this restarted exact ADMM at ρ=1\rho= 1, 2, and 4 (P≤5.0×10−5P \le5.0 \times10^{-5}).

Figure 7. General mixed-binary family (12) (12 ADMM iterations, 80 instances per panel) with (a) random couplings drawn as in the main family and (b) Wishart planted couplings. Fraction of instances on which the best feasible iterate is the problem optimum, against ρ\rho, for each subproblem solver and for ADMM with four restarts and exact subproblem solutions (dashed); mean and 95% bootstrap interval. In (a), the exact, transferred-angle, tabu-with-restarts, and tuned-SA curves nearly coincide.

With Wishart planted couplings (80 instances, seed offset 40000, BB from [−0.1,0.1][-0.1,0.1], planted-family angles; Figure 7(b)), the subproblem ranking carried over (at ρ=1\rho= 1, transferred QAOA solved 97.8% of subproblems exactly and SDP+LS 96.1%, against 64.9% to 75.3% for the four strongest local heuristics), but the ADMM ranking reversed: at ρ=1\rho= 1, the problem optimum was found on 77.5% of instances with transferred QAOA, 75.0% with exact solutions, and 76.2% with SDP+LS, against 92.5% to 96.2% with the local heuristics and 88.8% with restarted exact ADMM (P<1.6×10−3P < 1.6 \times10^{-3} at ρ=1\rho= 1 for transferred QAOA against each; at ρ=2\rho= 2 and 4, rr from +0.70 to +0.94; at ρ=0.5\rho= 0.5 no difference survived Holm correction). Accurate subproblem solutions stall, whereas errors from less-accurate heuristics move zz.

Verification and Statistical Accounting

The correctness gate passed at every level. We disclose two defects that benchmark results alone did not reveal: a Hamiltonian construction that halved the linear terms contributed by the couplings, which the gate now excludes, and the shared random stream of Section V-C. Of the 392 logged tests (157 confirmatory, 235 exploratory), 159 survive the global Bonferroni threshold (P<1.28×10−4P < 1.28 \times10^{-4}) and 233 remain significant after Holm correction within their families; the survivors include every best-sample comparison of a QAOA protocol with random search in the main setting (the budget control in the opposite direction) and every subproblem-level comparison of transferred QAOA with a local heuristic on the planted family at 768 evaluations and in time to solution up to n=18n = 18 (and n=20n = 20 except against tabu search with restarts). Of the 392 tests, 96 (50 confirmatory, 23 survivors) come from the mechanism, optimizer-ablation, Hamiltonian-defect, CVaR and initialization, size, noise, budget, coupling-density, and MaxCut studies, which this paper reports only where stated. No paired slope difference survives the global threshold, which its 4,000 bootstrap resamples cannot reach (P≥1/4001P \ge1/4001); all are exploratory, and several are not significant even nominally.

Discussion

Scoring and Budget Are Design Decisions

Best-sample scoring asks what a decomposition method asks of its subproblem solver and is how every classical baseline is implicitly scored [14]; read-out scoring raises the bar for QAOA by a factor of up to B/R\mathcal{B}/\mathcal{R} (Proposition 1). QAOA benchmarks should log every sampled bitstring, state the scoring rule and B/R\mathcal{B}/\mathcal{R}, report the evaluations actually used, draw the shots of every evaluation independently and test that they are, and report cost in seconds as well as in evaluations, because a matched number of evaluations hides a cost ratio of 17 to 560 between a device shot (3.56×10−43.56 \times10^{-4} s) and a classical evaluation in our implementations (§ 7-F).

What Transferred Angles Achieve

That transferred angles work on moving ADMM subproblems is consistent with parameter concentration [17], [18], [31], but on the benign main family, seven classical solvers also solve essentially every subproblem. On the planted family, the advantage over the local heuristics is real but bounded: it lies in resolving a handful of nearly degenerate low-energy states, is a prefactor with a larger exponent at p=2p = 2, and does not extend to SDP-based solvers or wall-clock time. The main open question, as in decay-rate comparisons of fixed-angle QAOA on other problems [25, 35, 36], is whether greater depth, angles trained for the probability of the optimum, or larger sizes change this comparison. The known limits of bounded-depth QAOA against local algorithms [37, 38, 39] concern approximation ratios, not time to solution.

The Penalty Decides What the Subproblem Is

For problem (1), the binary step is a proximal step on the reduced QUBO; at ρ=1\rho= 1 it is the reduced QUBO itself, and for ρ>1\rho> 1 exact solutions stall at suboptimal points increasingly often. That a noisy subproblem solver yields better ADMM-level solutions than an exact one at ρ=2\rho= 2 is therefore a statement about the penalty, not about the value of noise; the exploration that helps is also provided by random search or by restarts [3]. In the general families, where no penalty removes the proximal term, the same holds for ρ≥1\rho\ge1. Studies of QAOA inside ADMM should report ρ\rho, the ADMM-level outcome alongside subproblem quality, random-search and restart controls, and, when the problem reduces to a QUBO, a direct solution of it. The three-block heuristic of [4], which Qiskit Optimization implements with a penalty that starts at ρ=104\rho= 10^4 and grows during the run [15], is outside Theorem 1; whether its schedule causes stalling of the same kind is open, and these controls would answer it.

These results do not demonstrate a quantum advantage, but they indicate where one would have to come from: a family on which QAOA’s exponent, not only its prefactor, beats the strongest classical solvers, SDP-based ones included, in time rather than evaluations, on hardware that preserves the probability of good solutions, and inside a decomposition that does not simply repeat the reduced problem. The benchmark protocol lets the same controls be applied to deeper circuits, application-derived instances, and decomposition schemes used in practice.

Limitations

Scope. We studied the two-block ADMM scheme with a fixed penalty on a main problem class that reduces to a QUBO; only the two synthetic general families need a decomposition, and we did not run the three-block, adaptive-penalty heuristic of [4]. All instances are synthetic; the planted families come from a single ensemble parameter (α=0.5\alpha= 0.5), and their near-symmetry under complementation makes the exact-optimum rate partly a test of resolving a weak field. Most experiments use budgets that are a sizable fraction of the search space; the fixed budget extends to n=24n = 24, and the time to solution extends to n=20n = 20 on the second ADMM subproblem only.

Sampling. The circuit sampler reused one random stream per subproblem (§ 5-C). Only the main optimized-QAOA arm at ρ=2\rho= 2 has an independent-draw replicate, so the values of the other optimized variants in Figure 2, of the 40-instance shared-trajectory comparison, and of the budget sweep carry this caveat. We did not repeat these runs with the exact-distribution sampler. The scoring comparisons that support our conclusions, at n=12n = 12, 1616, and 2020 and at every penalty, used independent draws.

Depth, training, and cost. Transferred QAOA was scored in noiseless simulation at p=2p = 2 (also p=3p = 3 in several experiments, including the fixed budget) with angles trained on the mean gap, so the exponents are statements about p=2p = 2 over five sizes in a pre-asymptotic range. In a depolarizing-noise check (12 instances, five ADMM iterations, probability p1p_1 on single-qubit and 2p12p_1 on two-qubit gates), transferred angles kept a mean gap below 0.001 up to p1=1%p_1 = 1\% and reached 0.036 at 5% (random search: 0.078); hardware noise is outside the scope of this paper. Per-instance optimization used at most 56 optimizer evaluations per subproblem. Classical parameters other than the run budget were tuned at n=12n = 12; run budgets were selected on 20 held-out instances per size; and the conversion to seconds used serial Python implementations and the device time per shot at n=12n = 12, choices that favor QAOA.

Statistics. The planted-family and stronger-heuristic experiments were designed after the main-family results.

Conclusion

In every family we tested, QAOA, as the binary-subproblem solver of a two-block ADMM, did not give a better ADMM outcome than the best classical choice of solver and penalty. It was competitive at the subproblem level only when run with transferred angles and credited with its best sample, as classical solvers are; with 23 optimizer evaluations, read-out scoring reversed the comparison. At depth 2, it then matched seven classical solvers on the main family and, in noiseless simulation, beat the local heuristics on a rugged planted family by resolving nearly degenerate states and by a prefactor in evaluations, but with a larger exponent; it stayed behind SDP rounding with local search, and far behind in seconds. For problem (1), ADMM re-solves the reduced problem at ρ=1\rho= 1, and exact solutions increasingly stall for ρ>1\rho> 1; without this structure, less accurate solvers or restarts improved the ADMM outcome for ρ≥1\rho\ge1.

Data and Code Availability

The code, notebooks, per-instance results, test log, and analysis scripts are available at https://github.com/sanim-yousuf/qaoa-admm-benchmark.

Appendix

Proofs of the Analytical Results

Throughout, ∥⋅∥\lVert\cdot\rVert is the Euclidean norm, w=(ρ−1)/2w = (\rho- 1)/2 is the weight of the proximal term in Theorem 1, and line numbers in the proof of Theorem 1 refer to Algorithm 1.

Proof of Proposition 1. Idea: compare the probabilities that the two methods miss the good set Ω\Omega altogether.

(a) The read-out shots are among the logged shots (Algorithm 2), so the best logged bitstring is at least as good as the best read-out bitstring.

(b) The RR read-out shots are independent draws from the final state, and random search makes B\mathcal{B} independent uniform draws. Hence

Pr⁡[read-out misses Ω]=(1−π)R,\Pr[\text{read-out misses }\Omega] = (1-\pi)^R,
Pr⁡[random search misses Ω]=(1−u)B.\Pr[\text{random search misses }\Omega] = (1-u)^{\mathcal{B}}.

The read-out does at least as well if and only if (1−π)R≤(1−u)B(1-\pi)^R \le(1-u)^{\mathcal{B}}; taking the RR-th root gives π≥1−(1−u)B/R\pi\ge1-(1-u)^{\mathcal{B}/R}, which is (8). To size this threshold, let t=(B/R)u≤1t = (\mathcal{B}/R)u \le1, and note that B/R≥1\mathcal{B}/R \ge1 because the read-out is part of the budget. Two elementary inequalities give

1−e−t≤1−(1−u)B/R≤t.1-e^{-t} \le1-(1-u)^{\mathcal{B}/R} \le t.

The right inequality is Bernoulli’s inequality, (1−u)s≥1−su(1-u)^s \ge1-su for s≥1s \ge1; the left one uses 1−u≤e−u1-u \le e^{-u}. Finally, 1−e−t≥(1−e−1)t≈0.63t1-e^{-t} \ge(1-e^{-1})t \approx0.63t on [0,1][0,1], because the concave function 1−e−t1-e^{-t} lies above the chord joining its values at t=0t = 0 and t=1t = 1.

(c) If every shot is scored, the read-out is the whole budget; set R=BR = \mathcal{B} in (b).

Proof of Proposition 2. Idea: the shots are independent, so the optimum is missed only if every shot misses it.

Each shot misses the optimal set with probability 1−q1-q, so all B\mathcal{B} shots miss it with probability (1−q)B(1-q)^{\mathcal{B}}, and 1−q≤e−q1-q \le e^{-q} gives (9). The best sample has gap 0 when the optimum is found, and at most GG otherwise, so its expected gap is at most G(1−q)BG(1-q)^{\mathcal{B}}. Finally, e−qB≤ϵe^{-q\mathcal{B}} \le\epsilon if and only if q≥ln⁡(1/ϵ)/Bq \ge\ln(1/\epsilon)/\mathcal{B}.

Proof of Theorem 1. Idea: after the first iteration, the dual variable is fixed by the continuous iterate. Substituting this one identity into the QUBO gives the proximal form, and parts (b) and (c) then follow from how the anchor aka^k moves.

Step 1 (dual identity). Line 5 minimizes the augmented Lagrangian over xx, so, as in the standard analysis of nonconvex ADMM [23],

xk+1−c+λk+ρ(xk+1+Bzk+1−b)=0.(13)x^{k+1} - c + \lambda^k + \rho\left(x^{k+1} + Bz^{k+1} - b\right) = 0. \tag*{(13)}

Line 6 sets xk+1=xk+ρ(xk+1+Bzk+1−b)x^{k+1}=x^k+\rho\left(x^{k+1}+Bz^{k+1}-b\right), which by this equation is

λk+1=c−xk+1for every k≥0.(14)\lambda^{k+1}=c-x^{k+1}\qquad\text{for every }k\ge0. \tag*{(14)}

Step 2 (proximal form). Applying (14) with k−1k-1 in place of kk gives λk=c−xk\lambda^k=c-x^k for every k≥1k\ge1, which turns the linear term (3) into hk=B⊤c+(ρ−1)B⊤xk−ρB⊤bh^k=B^\top c+(\rho-1)B^\top x^k-\rho B^\top b. Expanding (4) gives, up to a constant, F(z)=z⊤Qz+12∥Bz∥2+(c−b)⊤BzF(z)=z^\top Qz+\frac{1}{2}\lVert Bz\rVert^2+(c-b)^\top Bz. Subtracting F(z)F(z) from the QUBO objective leaves, up to a constant,

w∥Bz∥2−2w(ak)⊤Bz=w∥Bz−ak∥2−w∥ak∥2,w\lVert Bz\rVert^2-2w(a^k)^\top Bz=w\lVert Bz-a^k\rVert^2-w\lVert a^k\rVert^2,

with ak=b−xka^k=b-x^k. The last term does not depend on zz, which proves (10). At ρ=1\rho=1, the weight ww is zero, so line 4 minimizes FF from the second iteration on. Because x=b−Bzx=b-Bz eliminates the constraint of (1), the minimizers of FF are exactly the zz-parts of the global optima of (1); with x=b−Bzx=b-Bz, the bitstring returned at the second iteration therefore gives a global optimum, which Algorithm 1 returns as its best feasible iterate. This proves (a).

Step 3 (the anchor moves toward BzˉB\bar{z}). Suppose line 4 returns zˉ\bar{z} at an iteration k≥1k\ge1, so zk+1=zˉz^{k+1}=\bar{z}, and let xˉ=b−Bzˉ\bar{x}=b-B\bar{z}. Inserting λk=c−xk\lambda^k=c-x^k (valid because k≥1k\ge1) into line 5 gives (1+ρ)(xk+1−xˉ)=xk−xˉ(1+\rho)(x^{k+1}-\bar{x})=x^k-\bar{x}, which in terms of the anchor reads

ak+1−Bzˉ=ak−Bzˉ1+ρ.(15)a^{k+1}-B\bar{z}=\frac{a^k-B\bar{z}}{1+\rho}. \tag*{(15)}

Each iteration that returns zˉ\bar{z} moves the anchor by the fraction ρ/(1+ρ)\rho/(1+\rho) of the remaining distance toward BzˉB\bar{z}.

Step 4 (part (b)). When zk+1=zˉz^{k+1}=\bar{z}, the residual of line 7 is δk+1=∥xk+1−xˉ∥=∥ak+1−Bzˉ∥\delta^{k+1}=\lVert x^{k+1}-\bar{x}\rVert=\lVert a^{k+1}-B\bar{z}\rVert. If also zk=zˉz^k=\bar{z}, that is, zˉ\bar{z} was returned at iteration k−1k-1, then δk=∥xk−xˉ∥=∥ak−Bzˉ∥\delta^k=\lVert x^k-\bar{x}\rVert=\lVert a^k-B\bar{z}\rVert, and (15) gives δk+1=δk/(1+ρ)\delta^{k+1}=\delta^k/(1+\rho), whether or not zˉ\bar{z} is optimal.

Step 5 (part (c), only if). Write

Φj(z)=F(z)+w∥Bz−aj∥2\Phi_j(z)=F(z)+w\lVert Bz-a^j\rVert^2

for the objective at iteration jj. If zˉ\bar{z} is returned at every iteration from kk on, then, because line 4 is solved exactly, Φj(z)≥Φj(zˉ)\Phi_j(z)\ge\Phi_j(\bar{z}) for all zz and all j≥kj\ge k; and (15), which applies at every j≥kj\ge k, gives aj→Bzˉa^j\to B\bar{z}. Letting j→∞j\to\infty yields

F(z)+w∥B(z−zˉ)∥2≥F(zˉ)for all z,F(z)+w\lVert B(z-\bar{z})\rVert^2\ge F(\bar{z})\qquad\text{for all }z,

which is (11).

Step 6 (part (c), if). Fix zz and let D(a)D(a) be the advantage of zˉ\bar{z} over zz when the anchor is aa, that is, the objective at zz minus the objective at zˉ\bar{z}. The term w∥a∥2w\lVert a\rVert^2 cancels, so DD is an affine function of aa. It is nonnegative at a=aka=a^k, because the exact solver returned zˉ\bar{z} at iteration kk, and at a=Bzˉa=B\bar{z}, by (11). By (15), ak+1a^{k+1} lies on the segment between these two points, so D(ak+1)≥0D(a^{k+1})\ge0. Hence zˉ\bar{z} is again a minimizer and, with ties broken in its favor, is returned at iteration k+1k+1. Repeating the argument at iterations k+1,k+2,…k+1,k+2,\ldots shows that zˉ\bar{z} is returned at every later iteration.

Step 7 (remaining statements). At ρ=1\rho=1, (11) reads F(zˉ)≤F(z)F(\bar{z})\le F(z) for all zz. For ρ>1\rho>1 the term w∥B(z−zˉ)∥2w\lVert B(z-\bar{z})\rVert^2 is nonnegative, so every global minimizer z∗z^\ast satisfies (11), and setting z=zˉz=\bar{z} in (11) gives F(zˉ)−F(z∗)≤w∥B(z∗−zˉ)∥2F(\bar{z})-F(z^\ast)\le w\lVert B(z^\ast-\bar{z})\rVert^2. The right side of (11) does not decrease as ρ\rho grows, so a stalling point for one penalty remains one for every larger penalty. Steps 5 and 6 do not use the sign of ww, so the characterization holds for every ρ>0\rho>0. For ρ<1\rho<1, w<0w<0, and setting z=z∗z=z^\ast in (11) gives F(zˉ)≤F(z∗)−∣w∣∥B(z∗−zˉ)∥2≤F(z∗)F(\bar{z})\le F(z^\ast)-|w|\lVert B(z^\ast-\bar{z})\rVert^2\le F(z^\ast), so zˉ\bar{z} is a global minimizer, and (11) is then the sharpness condition stated in the theorem. □

Proof of Remark 1. Idea: repeat Steps 1, 2, 3, and 5 of the proof of Theorem 1 with the weight ρI−H\rho I-H in place of (ρ−1)I(\rho-1)I. With continuous part 12x⊤Hx−c⊤x\frac{1}{2}x^\top Hx-c^\top x, the optimality condition of the xx-update (line 5 with HH in place of II) reads Hxk+1−c+λk+ρ(xk+1+Bzk+1−b)=0Hx^{k+1}-c+\lambda^k+\rho(x^{k+1}+Bz^{k+1}-b)=0, so line 6 gives λk+1=c−Hxk+1\lambda^{k+1}=c-Hx^{k+1}, and hence λk=c−Hxk\lambda^k=c-Hx^k for k≥1k\ge1. With ak=b−xka^k=b-x^k, the objective of line 4 is, up to a constant, z⊤Qz+(λk)⊤Bz+ρ2∥Bz−ak∥2z^\top Qz+(\lambda^k)^\top Bz+\frac{\rho}{2}\lVert Bz-a^k\rVert^2, and the residual objective is F(z)=12(b−Bz)⊤H(b−Bz)−c⊤(b−Bz)+z⊤QzF(z)=\frac{1}{2}(b-Bz)^\top H(b-Bz)-c^\top(b-Bz)+z^\top Qz. Substituting λk=c−Hb+Hak\lambda^k=c-Hb+Ha^k and subtracting F(z)F(z) leaves, up to a constant,

(ak)⊤HBz−12∥Bz∥H2+ρ2∥Bz−ak∥2=12∥Bz−ak∥ρI−H2+12∥ak∥H2,(a^k)^\top HBz-\frac{1}{2}\lVert Bz\rVert_H^2+\frac{\rho}{2}\lVert Bz-a^k\rVert^2 = \frac{1}{2}\lVert Bz-a^k\rVert_{\rho I-H}^2+\frac{1}{2}\lVert a^k\rVert_H^2,

and the last term does not depend on zz. For H=IH=I, this is the proximal term of (10). If line 4 returns zˉ\bar{z} at an iteration k≥1k\ge1 and xˉ=b−Bzˉ\bar{x}=b-B\bar{z}, line 5 now gives (H+ρI)(xk+1−xˉ)=H(xk−xˉ)(H+\rho I)(x^{k+1}-\bar{x})=H(x^k-\bar{x}), that is, ak+1−Bzˉ=(H+ρI)−1H(ak−Bzˉ)a^{k+1}-B\bar{z}=(H+\rho I)^{-1}H(a^k-B\bar{z}). This matrix contraction reduces to (14) for H=IH=I. Its eigenvalues are ηi/(ηi+ρ)\eta_i/(\eta_i+\rho), with ηi≥0\eta_i\ge0 the eigenvalues of HH, lie in (0,1)(0,1), so the anchor still converges to BzˉB\bar{z} and Step 5 applies with Φj(z)=F(z)+12∥Bz−aj∥ρI−H2\Phi_j(z)=F(z)+\frac{1}{2}\lVert Bz-a^j\rVert_{\rho I-H}^2, giving F(z)+12∥B(z−zˉ)∥ρI−H2≥F(zˉ)F(z)+\frac{1}{2}\lVert B(z-\bar{z})\rVert_{\rho I-H}^2\ge F(\bar{z}) for all zz. In general, however, the contraction does not keep ak+1a^{k+1} on the segment between aka^k and BzˉB\bar{z}, and the residual is not divided by a single scalar, so Steps 4 and 6 do not apply. For H=ηIH=\eta I, the weight ρI−H\rho I-H vanishes at ρ=η\rho=\eta, where line 4 minimizes FF from the second iteration on, as in Step 2. □

Acknowledgment

We acknowledge the use of IBM Quantum services for this work. The views expressed are those of the authors and do not reflect the official policy or position of IBM or the IBM Quantum team. The authors used Claude (Anthropic), an AI assistant, to help draft and edit the text of all sections, including the appendix, to draw the schematic diagram of Figure 1, and to help write part of the analysis code. The authors designed the study, ran all experiments and all code, checked every reported number against the computed outputs, and take full responsibility for the content.

Figure 1. Method overview. (a) ADMM for problem (1) delegates its binary update to a QUBO solver once per iteration; by Theorem 1, this QUBO is a proximal step on the reduced problem. (b) Every solver receives the same budget of B\mathcal{B} objective evaluations, all logged. (c) How optimized and transferred-angle QAOA spends the budget in the main protocol, and which shots each scoring rule credits.

References

References

  1. [1]R. Mahroo and A. Kargarian, “Hybrid quantum-classical unit commitment,” in Proc. IEEE Texas Power Energy Conf. (TPEC), College Station, TX, USA, 2022, pp. 1–5.DOI
  2. [2]S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Mach. Learn., vol. 3, no. 1, pp. 1–122, 2011.
  3. [3]R. Takapoui, N. Moehle, S. Boyd, and A. Bemporad, “A simple effective heuristic for embedded mixed-integer quadratic programming,” Int. J. Control, vol. 93, no. 1, pp. 2–12, 2020.
  4. [4]C. Gambella and A. Simonetto, “Multiblock ADMM heuristics for mixed-binary optimization on classical and quantum computers,” IEEE Trans. Quantum Eng., vol. 1, pp. 1–22, 2020, art. no. 3102022.DOI
  5. [5]E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” 2014, arXiv:1411.4028.arxiv.org/abs/1411.4028
  6. [6]J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum, vol. 2, p. 79, 2018.DOI
  7. [9]A. Abbas et al., “Challenges and opportunities in quantum optimization,” Nat. Rev. Phys., vol. 6, no. 12, pp. 718–735, 2024.
  8. [10]T. Lubinski et al., “Optimization applications as quantum performance benchmarks,” ACM Trans. Quantum Comput., vol. 5, no. 3, pp. 1–44, 2024, art. no. 18.DOI
  9. [11]T. Koch et al., “The quantum optimization benchmarking library,” Nat. Comput. Sci., vol. 6, no. 6, pp. 653–671, 2026.DOI
  10. [12]M. Streif and M. Leib, “Comparison of QAOA with quantum and simulated annealing,” 2019, arXiv:1901.01903.arxiv.org/abs/1901.01903
  11. [13]E. Pelofske, A. Bärtschi, and S. Eidenbenz, “Short-depth QAOA circuits and quantum annealing on higher-order Ising models,” npj Quantum Inf., vol. 10, no. 1, p. 30, 2024.DOI
  12. [14]D. Lykov, J. Wurtz, C. Poole, M. Saffman, T. Noel, and Y. Alexeev, “Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm,” npj Quantum Inf., vol. 9, p. 73, 2023.DOI
  13. [15]Qiskit Optimization contributors, “Qiskit Optimization: AD-MMOptimizer, ADMMParameters, and MinimumEigenOptimizer documentation,” 2026, version 0.7.0. Accessed: Oct. 1, 2026. [Online]. Available: https://qiskit-community.github.io/qiskit-optimization/
  14. [16]Qiskit Algorithms contributors, “Qiskit Algorithms: SamplingVQEResult documentation,” 2026, accessed: Oct. 1, 2026. [Online]. Available: https://qiskit-community.github.io/qiskit-algorithms/stubs/qiskit_algorithms.SamplingVQEResult.html
  15. [17]F. G. S. L. Brandão, M. Broughton, E. Farhi, S. Gutmann, and H. Neven, “For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances,” 2018, arXiv:1812.04170.arxiv.org/abs/1812.04170
  16. [18]K. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, “Parameter concentrations in quantum approximate optimization,” Phys. Rev. A, vol. 104, no. 1, p. L010401, 2021.DOI
  17. [19]F. Hamze, J. Raymond, C. A. Pattison, K. Biswas, and H. G. Katzgraber, “Wishart planted ensemble: A tunably rugged pairwise Ising model with a first-order phase transition,” Phys. Rev. E, vol. 101, no. 5, p. 052102, 2020.DOI
  18. [20]A. Peruzzo et al., “A variational eigenvalue solver on a photonic quantum processor,” Nat. Commun., vol. 5, no. 1, p. 4213, 2014.DOI
  19. [21]L. Braine, D. J. Egger, J. Glick, and S. Woerner, “Quantum algorithms for mixed binary optimization applied to transaction settlement,” IEEE Trans. Quantum Eng., vol. 2, pp. 1–8, 2021, art. no. 3101208.DOI
  20. [22]Y. Wang, W. Yin, and J. Zeng, “Global convergence of ADMM in nonconvex nonsmooth optimization,” J. Sci. Comput., vol. 78, no. 1, pp. 29–63, 2019.
  21. [23]G. Li and T. K. Pong, “Global convergence of splitting methods for nonconvex composite optimization,” SIAM J. Optim., vol. 25, no. 4, pp. 2434–2460, 2015.DOI
  22. [24]J. K. Golden, A. Bärtschi, D. O’Malley, and S. J. Eidenbenz, “Numerical evidence for exponential speed-up of QAOA over unstructured search for approximate constrained optimization,” in Proc. IEEE Int. Conf. Quantum Comput. Eng. (QCE), 2023, pp. 496–505.DOI
  23. [25]M. Dupont, N. Didier, M. J. Hodson, J. E. Moore, and M. J. Reagor, “Calibrating the classical hardness of the quantum approximate optimization algorithm,” PRX Quantum, vol. 3, no. 4, p. 040339, 2022.DOI
  24. [26]G. Nannicini, “Performance of hybrid quantum-classical variational heuristics for combinatorial optimization,” Phys. Rev. E, vol. 99, no. 1, p. 013304, 2019.
  25. [27]R. Shaydulin et al., “Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem,” Sci. Adv., vol. 10, no. 22, p. eadm6761, 2024.DOI
  26. [28]T. F. Rønnow et al., “Defining and detecting quantum speedup,” Science, vol. 345, no. 6195, pp. 420–424, 2014.DOI
  27. [29]T. Albash and D. A. Lidar, “Demonstration of a scaling advantage for a quantum annealer over simulated annealing,” Phys. Rev. X, vol. 8, p. 031016, 2018.
  28. [30]T. Bartz-Beielstein et al., “Benchmarking in optimization: Best practice and open issues,” 2020, arXiv:2007.03488.arxiv.org/abs/2007.03488
  29. [31]J. Wurtz and D. Lykov, “Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs,” Phys. Rev. A, vol. 104, no. 5, p. 052419, 2021.DOI
  30. [32]R. Shaydulin, P. C. Lotshaw, J. Larson, J. Ostrowski, and T. S. Humble, “Parameter transfer for quantum approximate optimization of weighted MaxCut,” ACM Trans. Quantum Comput., vol. 4, no. 3, pp. 1–15, 2023, art. no. 19.DOI
  31. [33]S. H. Sureshbabu et al., “Parameter setting in quantum approximate optimization of weighted problems,” Quantum, vol. 8, p. 1231, 2024.DOI
  32. [34]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,” Phys. Rev. X, vol. 10, no. 2, p. 021067, 2020.
  33. [35]S. Boulebnane and A. Montanaro, “Solving Boolean satisfiability problems with the quantum approximate optimization algorithm,” PRX Quantum, vol. 5, no. 3, p. 030348, 2024.
  34. [36]J. A. Montañez-Barrera and K. Michielsen, “Toward a linear-ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems,” npj Quantum Inf., vol. 11, p. 131, 2025.
  35. [37]E. Farhi, D. Gamarnik, and S. Gutmann, “The quantum approximate optimization algorithm needs to see the whole graph: A typical case,” 2020, arXiv:2004.09002.arxiv.org/abs/2004.09002
  36. [38]M. B. Hastings, “Classical and quantum bounded depth approximation algorithms,” Quantum Inf. Comput., vol. 19, no. 13&14, pp. 1116–1140, 2019.arxiv.org/abs/1905.07047
  37. [39]B. Barak and K. Marwaha, “Classical algorithms and quantum limitations for maximum cut on high-girth graphs,” in Proc. 13th Innov. Theor. Comput. Sci. Conf. (ITCS), ser. Leibniz International Proceedings in Informatics, vol. 215, 2022, pp. 14:1–14:21.DOI
  38. [40]M. Fernández-Pendás, E. Combarro, S. Vallecorsa, J. Ranilla, and I. F. Rúa, “A study of the performance of classical minimizers in the quantum approximate optimization algorithm,” J. Comput. Appl. Math., vol. 404, p. 113388, 2022.
  39. [41]P. K. Barkoutsos, G. Nannicini, A. Robert, I. Tavernelli, and S. Woerner, “Improving variational quantum optimization using CVaR,” Quantum, vol. 4, p. 256, 2020.DOI
  40. [42]D. J. Egger, J. Mareček, and S. Woerner, “Warm-starting quantum optimization,” Quantum, vol. 5, p. 479, 2021.DOI
  41. [43]G. Scriva, N. Astrakhantsev, S. Pilati, and G. Mazzola, “Challenges of variational quantum optimization with measurement shot noise,” Phys. Rev. A, vol. 109, no. 3, p. 032408, 2024.DOI
  42. [44]J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, “Barren plateaus in quantum neural network training landscapes,” Nat. Commun., vol. 9, no. 1, p. 4812, 2018.
  43. [45]M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” J. ACM, vol. 42, no. 6, pp. 1115–1145, 1995.DOI
  44. [46]I. Dunning, S. Gupta, and J. Silberholz, “What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO,” INFORMS J. Comput., vol. 30, no. 3, pp. 608–624, 2018.DOI
  45. [47]G. Palubeckis, “Multistart tabu search strategies for the unconstrained binary quadratic optimization problem,” Ann. Oper. Res., vol. 131, no. 1, pp. 259–282, 2004.DOI
  46. [48]K. Hukushima and K. Nemoto, “Exchange Monte Carlo method and application to spin glass simulations,” J. Phys. Soc. Jpn., vol. 65, no. 6, pp. 1604–1608, 1996.
  47. [49]D. J. Earl and M. W. Deem, “Parallel tempering: Theory, applications, and new perspectives,” Phys. Chem. Chem. Phys., vol. 7, no. 23, pp. 3910–3916, 2005.
  48. [50]M. P. Harrigan et al., “Quantum approximate optimization of non-planar graph problems on a planar superconducting processor,” Nat. Phys., vol. 17, no. 3, pp. 332–336, 2021.DOI
  49. [51]M. J. D. Powell, “A direct search optimization method that models the objective and constraint functions by linear interpolation,” in Advances in Optimization and Numerical Analysis, ser. Mathematics and Its Applications, S. Gomez and J.-P. Hennart, Eds. Dordrecht: Kluwer Academic, 1994, vol. 275, pp. 51–67.DOI
  50. [52]J. A. Nelder and R. Mead, “A simplex method for function minimization,” Comput. J., vol. 7, no. 4, pp. 308–313, 1965.DOI
  51. [53]S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.
  52. [54]F. Glover, “Tabu search—Part I,” ORSA J. Comput., vol. 1, no. 3, pp. 190–206, 1989.DOI
  53. [55]S. Diamond and S. Boyd, “CVXPY: A Python-embedded modeling language for convex optimization,” J. Mach. Learn. Res., vol. 17, no. 83, pp. 1–5, 2016.
  54. [56]J. C. Spall, “Implementation of the simultaneous perturbation algorithm for stochastic optimization,” IEEE Trans. Aerosp. Electron. Syst., vol. 34, no. 3, pp. 817–823, 1998.DOI
  55. [57]F. Wilcoxon, “Individual comparisons by ranking methods,” Biometrics Bull., vol. 1, no. 6, pp. 80–83, 1945.
  56. [58]B. Efron, “Bootstrap methods: Another look at the jackknife,” Ann. Stat., vol. 7, no. 1, pp. 1–26, 1979.
  57. [59]N. A. Obuchowski, “On the comparison of correlated proportions for clustered data,” Stat. Med., vol. 17, no. 13, pp. 1495–1507, 1998.pubmed.ncbi.nlm.nih.gov/9695194
  58. [60]S. Holm, “A simple sequentially rejective multiple test procedure,” Scand. J. Stat., vol. 6, no. 2, pp. 65–70, 1979.DOI
  59. [61]A. Javadi-Abhari et al., “Quantum computing with Qiskit,” 2024, arXiv:2405.08810.
  60. [62]C. R. Harris et al., “Array programming with NumPy,” Nature, vol. 585, no. 7825, pp. 357–362, 2020.
  61. [63]P. Virtanen et al., “SciPy 1.0: Fundamental algorithms for scientific computing in Python,” Nat. Methods, vol. 17, no. 3, pp. 261–272, 2020.DOI
  62. [64]M. Friedman, “The use of ranks to avoid the assumption of normality implicit in the analysis of variance,” J. Am. Stat. Assoc., vol. 32, no. 200, pp. 675–701, 1937.DOI

Paper details

vlnc:W_q75ykdbt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Claude

View statement
Looking for related papers…
Contents