In this paper
AbstractIntroductionRelated WorkQAOA and ADMM for Mixed-Binary ProblemsBenchmarking QAOA Against Classical SolversFixed, Concentrated, and Transferred AnglesAngle Optimization and Classical BaselinesProblem FormulationADMM for Mixed-Binary OptimizationQAOA and the Cost HamiltonianNormalized GapAnalytical ResultsScoring Rules and Sampling BudgetsWhat the Binary Step of ADMM SolvesBenchmark DesignMatched Objective-Evaluation Budget and ScoringSolversSampling of QAOA ShotsPerformance MeasuresExperimental Designs and StatisticsCorrectness VerificationExperimental SetupResultsThe Scoring Rule Decides the ComparisonTransferred Angles Solve the ADMM SubproblemsStronger Classical Baselines and CostScaling at a Fixed BudgetA Planted Family With a Rugged LandscapeTime to SolutionADMM-Level Behavior and the PenaltyMixed-Binary Families That Do Not Reduce to a QUBOVerification and Statistical AccountingDiscussionScoring and Budget Are Design DecisionsWhat Transferred Angles AchieveThe Penalty Decides What the Subproblem IsLimitationsConclusionData and Code AvailabilityAppendixProofs of the Analytical ResultsAcknowledgmentReferencesWorksPhysics 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 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.
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 for every tested ADMM penalty from 0.5 to 4 and at and 20 for (inconclusively at , uncorrected ; the read-out tests are exploratory and, except at and , post hoc). By Proposition 1, read-out scoring requires the final state to amplify every small good set roughly -fold over uniform sampling (budget , read-out size ). This is an accounting caution for this regime, not a QAOA property.
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 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.
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 .
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.
Related Work
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 , 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 -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],
with , symmetric, and . With penalty and dual variable , the augmented Lagrangian is . Each iteration updates , then , then (Algorithm 1). For fixed the -update is the QUBO
followed by and , starting from . Because changes at every iteration, the solver faces a new QUBO each time. For any , the point is feasible, so every iterate defines a feasible solution of (1). Eliminating gives the reduced objective
itself a QUBO. Problem (1) is therefore a QUBO in disguise: an exact or heuristic QUBO solver applied to 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, with . Section VIII-H also studies two families that do not reduce to a QUBO.
Algorithm 1 ADMM with a QUBO subproblem solver
Require: ; penalty ; iterations ; subproblem solver with budget
for do
QUBO (2)
primal residual
end for
return best feasible iterate ,
QAOA and the Cost Hamiltonian
Writing with gives the cost as
whose operator form, with , defines the cost Hamiltonian . 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 prepares
with , , and , where and is the root-mean-square of the non-identity Pauli coefficients of ( in the unnormalized variant). The normalization makes angle scales comparable across subproblems with different energy scales [33].
Normalized Gap
For a subproblem with optimum , mean cost over all bitstrings, and maximum , the normalized gap of a bitstring is
which is 0 at the optimum, 1 for the expected result of a single uniform guess, and at most . For a distribution over bitstrings, denotes its mean normalized gap, so that 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 of bitstrings good (for example, all bitstrings whose normalized gap is at most some threshold), and let be the fraction of all bitstrings that lie in . Random search with budget finds with probability . 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 with a read-out of shots drawn independently from its final state, and let that state place probability on a good set . Then:
(a) the best-sample output is never worse than the read-out output;
(b) the read-out finds at least as often as random search if and only if
where the approximation holds when is small, and the exact threshold always lies between and once ;
(c) if all shots are drawn from one state and the best sample is scored, as with transferred angles, the condition is only .
In words, read-out scoring requires the final state to amplify every small good set by roughly 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, . Because the expected gap equals with , 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 on the optimal bitstrings and is sampled times independently, the optimum is missed with probability
and the expected normalized gap of the best sample is at most . Hence guarantees that the optimum is found with probability at least .
For uniform sampling at with a unique optimum, and give a success probability of . Success with probability 0.99 requires , 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 decays with (Section VII-D).
What the Binary Step of ADMM Solves
Theorem 1 concerns problem (1) as stated: a continuous part and the coupling , with no further constraints on .
Theorem 1 (The binary step is a proximal step): Run Algorithm 1 on problem (1) with any subproblem solver and penalty . For every iteration , the QUBO passed to the solver in line 4 is, up to an additive constant,
that is, the reduced problem (4) plus a proximal term that pulls toward the anchor set by the current iterate. Consequently:
(a) Penalty one. If , 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 from some iteration on, the residual of line 7 is divided by exactly at every subsequent iteration, whether or not is optimal.
(c) Stalling points. Suppose line 4 is solved exactly, with ties broken in favor of the previous bitstring, and returns , computed with the anchor , at some iteration . Then line 4 returns at every later iteration if and only if
We call such a a stalling point; the characterization holds for every . At , the stalling points are exactly the global minimizers of . For , every global minimizer is a stalling point, but suboptimal bitstrings can be as well; their excess cost is at most for a global minimizer , and the set of stalling points can only grow as increases. For a stalling point must be a global minimizer that is sharp, for all , and there may be none.
For , the weight in (10) is negative; we keep the name proximal for brevity. An experiment with 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 , an exact subproblem solver never leaves a stalling point once it returns one, whereas a stochastic solver keeps changing 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 .
Remark 1 (A general quadratic): The proximal form extends to a strongly convex quadratic : for the QUBO of line 4 equals up to a constant, where is the corresponding reduced objective and is a quadratic form, not a norm when is indefinite. The anchor now contracts toward by the matrix rather than by the scalar . The residual ratio of part (b) therefore needs not be , and of part (c) only the “only if” direction is proved to carry over, with the weight in place of . Part (a) carries over when , at (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 evaluations per scan of the one-flip neighbors, although an incremental implementation computes the flip differences in time. Every solver receives the same budget 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 evaluations.
Algorithm 2 QAOA subproblem solver with shot logging
Require: QUBO ; budget ; depth ; mode; read-out size ; shots per evaluation ; fixed angles
build from (5); log of all shots
if mode is transferred then
draw shots at into ;
else mode is optimized
uniform sample from
while optimizer runs and do
draw shots at into
return their mean cost to the optimizer; update
end while
draw read-out shots at into
draw shots at into top-up
end if
return best-sample output and read-out output
Solvers
Optimized QAOA runs constrained optimization by linear approximation (COBYLA) [51] (SciPy; initial step 1.0, tolerance ) from initial angles uniform on : 23 optimizer evaluations of 32 shots, each returning the mean sampled cost, then a 32-shot read-out at the returned angles (, ). The main comparison (Figure 2) adds depths 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 (, 80 instances, , circuit sampler). (a) Normalized gap 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 . Under read-out scoring, most optimized protocols fall to or behind random search; Table II gives independent-draw values for optimized QAOA with .
Transferred-angle QAOA fixes 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 at by minimizing the mean exact expected normalized gap 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 , and the time-to-solution study also uses angles retrained at on 18 subproblems of six held-out instances, starting from the 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 single-bit-flip Metropolis proposals with geometric cooling from to ; 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 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 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 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 (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 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, . Exhaustive enumeration provides and for every subproblem up to . 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 in (4) and normalized as in (7) with in place of .
Scaling is measured by the time to solution , 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 on the optimum (transferred QAOA with exact , uniform sampling, and SDP rounding with estimated from 4,096 roundings), . For solvers with a run length, the run budget is chosen per solver, size, and family from 25 values between 8 and 32,768 as the one minimizing the median over 20 held-out instances (256 runs per budget). Each test instance is then scored from 1,024 runs at as , with the fraction of runs that found the optimum, or as , an upper bound, when every run succeeds; an instance with no successful run is censored. The exponent is the least-squares slope of of the median against , 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 , which is a lower bound for larger .
Experimental Designs and Statistics
ADMM-embedded runs execute 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 for from 12 to 24. Direct runs apply a solver once to with the total budget of an ADMM run.
The unit of analysis is the instance. We write for -values, for the matched-pairs rank-biserial effect size of the exact two-sided Wilcoxon signed-rank test [57], with 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 . 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] ( from 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 , 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 plus its offset must equal the exact QUBO cost of every bitstring (). At the circuit level (), the cost layer with zero mixer angle must prepare , and the full ansatz must reproduce the output probabilities of the independent NumPy simulator used for angle training. At the sampling level (, 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 uniformly from (symmetrized), from , and from , and use unless stated otherwise. The planted family takes from the Wishart planted ensemble [19]: Ising couplings with zero diagonal, where the Gaussian columns of () 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 ( from , from ) 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 with , 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 circuits of this benchmark at (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, and 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.
| Question | Finding |
| 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 and (inconclusive at ; 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 to 12, equivalent within 2 percentage points to seven classical solvers; at a fixed budget, decays as up to at (Sections VII-B to VII-D). |
| Is there an advantage on a rugged planted family? | Over local heuristics only (noiseless, ): 97.3% against at most 67.4% solved exactly; fewer evaluations to solution at 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 ADMM re-solves ; for , exact solutions stall more often; in two non-QUBO families, less accurate solvers found the problem optimum more often for (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 , with QAOA drawn by the circuit sampler. Scored on its final read-out, optimized QAOA () is significantly worse than random search ( [0.72, 0.96], ); scored on the best bitstring sampled within the same budget, on the same runs, it is significantly better ( [−0.96, −0.68], , 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 (, ) and the best sample wins (, ); 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 ( for each; Table II; post hoc and outside the test log). The unnormalized protocol reverses in the same way but more weakly (, ), whereas multi-start, whose four pooled 16-shot read-outs halve to 12, beats random search even under read-out scoring (, ), as Proposition 1 allows, although the circuit sampler’s bias toward the read-out (§ 5-C) may inflate this result. Depth () had no detectable effect (Friedman test [64], ), 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 (, ) and loses under read-out scoring (mean 0.127 against 0.093, , , post hoc). Embedded in ADMM at 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 (, ) and, inconclusively, at (, ; both solved 0.8% of subproblems exactly), and the best sample a smaller gap on all 15 instances at both sizes (; all uncorrected, post hoc, and outside the test log). A circuit-sampled budget sweep at from 5% to 45% of the space (30 instances, eight ADMM iterations) shows the reversal at 10% (read-out loss uncorrected, ), 18.75%, and 45%, with inconclusive nulls for the read-out at 5% () and the best sample at 30% (); 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 (, ), and with independent draws optimized QAOA () remains far behind SA in mean gap ( of 36.8 against 1.96; Table III).
Transferred Angles Solve the ADMM Subproblems
Transferred-angle QAOA ( and 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; , 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 and solve 99.8% and 99.9% of the subproblems exactly, and the three angle sets differ by at most 0.07 rad in any component, consistent with parameter concentration. Angles trained at gave a mean 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 and the whole space at ) 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 (, 80 instances, 960 subproblems per solver, ). (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 to 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 grows from 12 to 24, where it covers of the space (Figure 4; second ADMM subproblem; 20 instances per size, 10 at and 24), the probability of the optimum under the transferred state falls as for and for (least-squares fits over instances), while 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 () and 0.966 (). 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 for per-instance optimized QAOA (exact-distribution sampler), and no comparison of transferred QAOA with tuned SA or tabu search was significant (, 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, to 24. (a) Probability of the optimum under the transferred and states and under uniform sampling, mean of over instances with 95% interval. (b) Fraction of instances on which the optimum was found: exact value for the transferred state (dashed, no markers) and one 768-evaluation run per solver (markers).
| Setting | Sampler | BS | RO | Rand. | BS | RO | Rand. | (P) RO | (P) BS |
| , | circuit | 0.552 | 0.294 | 0.177 | 0.050 | 0.128 | 0.081 | +0.859 () | −0.833 () |
| , | independent | 0.571 | 0.167 | 0.168 | 0.033 | 0.163 | 0.078 | +0.993 () | −0.994 () |
| , | independent | 0.601 | 0.196 | 0.166 | 0.033 | 0.158 | 0.079 | +0.965 () | −0.982 () |
| , | independent | 0.626 | 0.226 | 0.173 | 0.035 | 0.170 | 0.081 | +0.982 () | −0.976 () |
| , | independent | 0.641 | 0.214 | 0.177 | 0.037 | 0.170 | 0.081 | +0.985 () | −0.972 () |
| , | independent | 0.630 | 0.273 | 0.150 | 0.037 | 0.157 | 0.084 | +0.952 () | −0.983 () |
| , | independent | 0.649 | 0.247 | 0.148 | 0.035 | 0.157 | 0.088 | +0.966 () | −0.999 () |
| , | independent | 0.333 | 0.075 | 0.017 | 0.078 | 0.229 | 0.150 | +0.917 () | −1.000 () |
| , | independent | 0.142 | 0.008 | 0.008 | 0.114 | 0.258 | 0.207 | +0.600 (0.041) | −1.000 () |
Table 2. TABLE II Optimized QAOA () against random search under the two scoring rules, ADMM-embedded. : fraction of subproblems solved exactly; : mean normalized gap; each for QAOA under best-sample (BS) and read-out (RO) scoring and for random search; : rank-biserial effect of QAOA versus random search (: QAOA worse), with exact signed-rank (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 (medians over 80 instances at and 20 at $n = 16) show that the main family is easy: its subproblems have 4 single-flip local minima at and 7.5 at , steepest descent from a random start reaches the optimum from 67% and 53% of all starting points, and at the Euclidean norm of the linear term 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 , 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 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 ). Embedded in ADMM at , 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 () and the SDP (); against SDP+LS it was smaller at () but not at (). The planted-family angles were trained at the test size; angles retrained at 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 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 was credited, against 100%. Transferred QAOA stayed ahead of each under every criterion (instance-level signed-rank , post hoc and outside the test log) and in mean gap at (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 , transferred QAOA, the exact solver, and the four strongest local heuristics found the problem optimum on all 80 instances. At , where the exact solver itself
| Method | Pr[opt] | vs transferred | Time (s) | |
| Transferred | 0.00 | 1.000 | n/a | 0.0025 |
| Tabu, restarts | 0.00 | 1.000 | 1.0 (0) | 0.0018 |
| SDP+LS | 0.00 | 1.000 | 1.0 (0) | 0.016 |
| Local search | 0.03 | 0.999 | 1.0 (1) | 0.0012 |
| SDP | 0.08 | 0.994 | 0.13 (4) | 0.015 |
| PT | 0.25 | 0.993 | 0.13 (4) | 0.0070 |
| SA, tuned (small grid) | 0.44 | 0.993 | 0.031 (6) | 0.011 |
| Tabu | 0.60 | 0.990 | (8) | 0.0017 |
| SA, restarts | 0.61 | 0.983 | (10) | 0.011 |
| SA | 1.96 | 0.966 | (17) | 0.011 |
| QAOA , optimized | 50.1 | 0.552 | n/a | 0.071 |
| Random | 81.2 | 0.177 | (80) | 0.0002 |
Table 3. Stronger baselines (, ADMM-embedded, 80 instances, , ). : mean normalized gap ; : exact signed-rank test of transferred QAOA against the row method on (non-tied pairs); Time: median wall-clock seconds per subproblem in the Kaggle CPU environment (serial Python implementations).
| Method | Shared | Direct | |||||
| \multicolumn{3}{c}{Solved exactly} | \multicolumn{3}{c}{Problem optimum} | ||||||
| Transf. | 0.974 | 0.973 | 0.973 | 1.2 | 1.000 | 0.938 | 1.000 |
| Transf. | 0.976 | 0.973 | n/a | 1.1 | 1.000 | 0.938 | 1.000 |
| Transf. , main | 0.875 | 0.859 | n/a | 5.5 | 1.000 | 0.975 | n/a |
| SDP+LS | 0.888 | 0.806 | 0.965 | 3.2 | 0.962 | 0.875 | 0.912 |
| SDP | 0.798 | 0.747 | 0.938 | 7.4 | 0.888 | 0.750 | 0.788 |
| Tabu, restarts | 0.678 | 0.649 | 0.674 | 17.4 | 1.000 | 0.975 | 1.000 |
| Local search | 0.623 | 0.582 | 0.608 | 18.7 | 1.000 | 0.950 | 1.000 |
| SA, tuned (ext.) | 0.541 | 0.505 | 0.538 | 23.0 | 1.000 | 1.000 | 0.975 |
| PT | 0.488 | 0.468 | 0.506 | 26.2 | 1.000 | 0.988 | 0.988 |
| QAOA , optim. | 0.407 | 0.371 | 0.373 | 42.2 | 0.975 | 0.962 | n/a |
| SA | 0.362 | 0.329 | n/a | 38.1 | 0.975 | 1.000 | n/a |
| Tabu | 0.353 | 0.290 | 0.369 | 40.9 | 0.962 | 0.938 | 0.262 |
| Random | 0.155 | 0.165 | 0.167 | 60.0 | 0.888 | 0.875 | 0.862 |
| Exact | 1.000 | 1.000 | 1.000 | 0.0 | 1.000 | 0.912 | n/a |
Table 4. Planted family (, 80 instances, ). Pr[OPT]: fraction of subproblems solved exactly, ADMM-embedded (12 iterations) and on the identical subproblems of the exact-solver trajectory (960 per solver); : mean normalized gap ; Problem optimum: fraction of instances on which the best feasible iterate is the global optimum, embedded in ADMM and from a direct solution of with 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 (). By Theorem 1(a), every iteration after the first at poses the same QUBO , so an ADMM run gives a solver attempts at .
Time to Solution
Because a single budget of 768 evaluations saturates the classical solvers on the main family, Table V and Figure 5 report on the second ADMM subproblem from 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 and, separately, with angles retrained at . 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 and keeping them at larger favors QAOA in the comparison of exponents.
| Method | Main family, evaluations | Main family, evaluations | Main family, evaluations | Planted family, evaluations | Planted family, evaluations | Planted family, evaluations | Planted, seconds | Planted, seconds |
| Transferred , angles from | 89 | 803 | 0.37 [0.25, 0.48] | 923 | 22,001 | 0.57 [0.54, 0.59] | 0.33 | 7.8 |
| Transferred , angles from | 97 | 841 | 0.36 [0.25, 0.46] | 739 | 13,845 | 0.52 [0.49, 0.56] | 0.26 | 4.9 |
| Tabu, restarts | 192 | 809 | 0.29 [0.21, 0.35] | 2,817 | 23,264 | 0.37 [0.31, 0.43] | 0.0061 | 0.050 |
| SA, tuned | 292 | 1,308 | 0.29 [0.19, 0.40] | 4,466 | 55,588 | 0.45 [0.39, 0.50] | 0.059 | 1.1 |
| PT | 512 | 1,536 | 0.22 [0.16, 0.32] | 4,378 | 52,950 | 0.45 [0.38, 0.49] | 0.022 | 0.41 |
| Local search | 384 | 1,673 | 0.28 [0.23, 0.36] | 3,346 | 50,289 | 0.48 [0.44, 0.53] | 0.0049 | 0.068 |
| SDP+LS | 90 | 287 | 0.25 [0.16, 0.32] | 92 | 1,741 | 0.44 [0.30, 0.75] | 0.031 | 0.11 |
| SDP rounding | 13 | 24 | 0.14 [0.06, 0.24] | 10 | 483 | 0.52 [0.05, ] | 0.031 | 0.11 |
| Random | 18,860 | 1.00 | 18,860 | 1.00 | n/a | n/a |
Table V. TABLE V Time to solution TTS (noiseless simulation for QAOA, ) on the second ADMM subproblem (median over 20 test instances), the exponent in TTS fitted to the medians over to 20 with 95% bootstrap interval (an interval reaching contains resamples with a censored median), and the planted-family TTS in seconds. QAOA: device time per shot measured on ibm_marrakesh at ( s), applied to the noiseless TTS; classical solvers: measured serial time per evaluation of our Python implementations in the Kaggle CPU environment. Succeeded in every run on 10% to 60% of main-family instances at the selected budget, so the main-family values are upper bounds. One anneal per run, temperatures of the tuned configuration. 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, to 20, 20 test instances per size, for (a) the main and (b) the planted family: of the median TTS 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 (TTS) is omitted.
On the planted family, transferred QAOA needed 923 evaluations at , three to five times fewer than the local heuristics ( against each, the smallest exact with 20 pairs), but its cost grew faster, as against to : the paired bootstrap places the excess of its exponent above zero against every local heuristic (by 0.08 to 0.20, ), and at tabu search with restarts needed about as many evaluations (). Angles retrained at lowered the exponent to 0.52 and the cost at 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 evaluations per scan, and counting a scan as one evaluation would reduce their counts by up to a factor of 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 and 20, but its median was not monotone in 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 s, a classical evaluation to 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 and 20, and 11 and 72 times longer than SDP+LS, including its relaxation. In noiseless simulation at , 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 : the decay of the probability of the optimum was slower at 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 , subproblem accuracy and the ADMM outcome diverge. With exact, SDP, or transferredangle subproblem solutions, the mean primal residual falls to 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 , 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 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 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 (Figure 6). At , 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 ( for each). For , the exact solver stalled at a suboptimal bitstring increasingly often (31.2%, 50%, 82.5%, and 95% of instances at , 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 to within whenever the bitstring was held. At , no instance stalled at a suboptimal bitstring. For problem (1), the ADMMlevel advantage of noisy solvers at is therefore an artifact of the penalty.
Figure 6. Penalty sweep (, 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 with the budget of a whole ADMM run, evaluations. On the main family, the direct solution differed from ADMM at on at most one instance for every solver except random search, and with every accurate solver it beat ADMM at by 38 to 40 instances; on this family, ADMM at thus amounts to a direct solution of , and ADMM at 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 ) 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
with , , eight coupling constraints, a random Gaussian , and with Gaussian . ADMM’s -update becomes a box-constrained convex quadratic program, the -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 for every 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, and 2). On those 40 instances, optimized QAOA (exact-distribution sampler) found the problem optimum on 85% and 57.5% at and 2, as often as random search, against 45% and 32.5% for exact solutions. At the ADMM level (Figure 7(a)), however, 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 , 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 , 2, and 4 ([3]) but not at (). 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 , 2, and 4 ().
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 , 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, from , planted-family angles; Figure 7(b)), the subproblem ranking carried over (at , 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 , 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 ( at for transferred QAOA against each; at and 4, from +0.70 to +0.94; at no difference survived Holm correction). Accurate subproblem solutions stall, whereas errors from less-accurate heuristics move .
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 () 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 (and 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 (); 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 (Proposition 1). QAOA benchmarks should log every sampled bitstring, state the scoring rule and , 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 ( 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 , 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 it is the reduced QUBO itself, and for exact solutions stall at suboptimal points increasingly often. That a noisy subproblem solver yields better ADMM-level solutions than an exact one at 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 . Studies of QAOA inside ADMM should report , 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 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 (), 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 , and the time to solution extends to 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 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 , , and and at every penalty, used independent draws.
Depth, training, and cost. Transferred QAOA was scored in noiseless simulation at (also in several experiments, including the fixed budget) with angles trained on the mean gap, so the exponents are statements about over five sizes in a pre-asymptotic range. In a depolarizing-noise check (12 instances, five ADMM iterations, probability on single-qubit and on two-qubit gates), transferred angles kept a mean gap below 0.001 up to 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 ; 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 , 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 , and exact solutions increasingly stall for ; without this structure, less accurate solvers or restarts improved the ADMM outcome for .
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, is the Euclidean norm, 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 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 read-out shots are independent draws from the final state, and random search makes independent uniform draws. Hence
The read-out does at least as well if and only if ; taking the -th root gives , which is (8). To size this threshold, let , and note that because the read-out is part of the budget. Two elementary inequalities give
The right inequality is Bernoulli’s inequality, for ; the left one uses . Finally, on , because the concave function lies above the chord joining its values at and .
(c) If every shot is scored, the read-out is the whole budget; set 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 , so all shots miss it with probability , and gives (9). The best sample has gap 0 when the optimum is found, and at most otherwise, so its expected gap is at most . Finally, if and only if .
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 moves.
Step 1 (dual identity). Line 5 minimizes the augmented Lagrangian over , so, as in the standard analysis of nonconvex ADMM [23],
Line 6 sets , which by this equation is
Step 2 (proximal form). Applying (14) with in place of gives for every , which turns the linear term (3) into . Expanding (4) gives, up to a constant, . Subtracting from the QUBO objective leaves, up to a constant,
with . The last term does not depend on , which proves (10). At , the weight is zero, so line 4 minimizes from the second iteration on. Because eliminates the constraint of (1), the minimizers of are exactly the -parts of the global optima of (1); with , 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 ). Suppose line 4 returns at an iteration , so , and let . Inserting (valid because ) into line 5 gives , which in terms of the anchor reads
Each iteration that returns moves the anchor by the fraction of the remaining distance toward .
Step 4 (part (b)). When , the residual of line 7 is . If also , that is, was returned at iteration , then , and (15) gives , whether or not is optimal.
Step 5 (part (c), only if). Write
for the objective at iteration . If is returned at every iteration from on, then, because line 4 is solved exactly, for all and all ; and (15), which applies at every , gives . Letting yields
which is (11).
Step 6 (part (c), if). Fix and let be the advantage of over when the anchor is , that is, the objective at minus the objective at . The term cancels, so is an affine function of . It is nonnegative at , because the exact solver returned at iteration , and at , by (11). By (15), lies on the segment between these two points, so . Hence is again a minimizer and, with ties broken in its favor, is returned at iteration . Repeating the argument at iterations shows that is returned at every later iteration.
Step 7 (remaining statements). At , (11) reads for all . For the term is nonnegative, so every global minimizer satisfies (11), and setting in (11) gives . The right side of (11) does not decrease as grows, so a stalling point for one penalty remains one for every larger penalty. Steps 5 and 6 do not use the sign of , so the characterization holds for every . For , , and setting in (11) gives , so 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 in place of . With continuous part , the optimality condition of the -update (line 5 with in place of ) reads , so line 6 gives , and hence for . With , the objective of line 4 is, up to a constant, , and the residual objective is . Substituting and subtracting leaves, up to a constant,
and the last term does not depend on . For , this is the proximal term of (10). If line 4 returns at an iteration and , line 5 now gives , that is, . This matrix contraction reduces to (14) for . Its eigenvalues are , with the eigenvalues of , lie in , so the anchor still converges to and Step 5 applies with , giving for all . In general, however, the contraction does not keep on the segment between and , and the residual is not divided by a single scalar, so Steps 4 and 6 do not apply. For , the weight vanishes at , where line 4 minimizes 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 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]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]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]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]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]E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” 2014, arXiv:1411.4028.arxiv.org/abs/1411.4028
- [6]J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum, vol. 2, p. 79, 2018.DOI
- [9]A. Abbas et al., “Challenges and opportunities in quantum optimization,” Nat. Rev. Phys., vol. 6, no. 12, pp. 718–735, 2024.
- [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
- [11]T. Koch et al., “The quantum optimization benchmarking library,” Nat. Comput. Sci., vol. 6, no. 6, pp. 653–671, 2026.DOI
- [12]M. Streif and M. Leib, “Comparison of QAOA with quantum and simulated annealing,” 2019, arXiv:1901.01903.arxiv.org/abs/1901.01903
- [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
- [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
- [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/
- [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
- [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
- [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
- [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
- [20]A. Peruzzo et al., “A variational eigenvalue solver on a photonic quantum processor,” Nat. Commun., vol. 5, no. 1, p. 4213, 2014.DOI
- [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
- [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.
- [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
- [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
- [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
- [26]G. Nannicini, “Performance of hybrid quantum-classical variational heuristics for combinatorial optimization,” Phys. Rev. E, vol. 99, no. 1, p. 013304, 2019.
- [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
- [28]T. F. Rønnow et al., “Defining and detecting quantum speedup,” Science, vol. 345, no. 6195, pp. 420–424, 2014.DOI
- [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.
- [30]T. Bartz-Beielstein et al., “Benchmarking in optimization: Best practice and open issues,” 2020, arXiv:2007.03488.arxiv.org/abs/2007.03488
- [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
- [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
- [33]S. H. Sureshbabu et al., “Parameter setting in quantum approximate optimization of weighted problems,” Quantum, vol. 8, p. 1231, 2024.DOI
- [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.
- [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.
- [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.
- [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
- [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
- [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
- [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.
- [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
- [42]D. J. Egger, J. Mareček, and S. Woerner, “Warm-starting quantum optimization,” Quantum, vol. 5, p. 479, 2021.DOI
- [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
- [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.
- [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
- [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
- [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
- [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.
- [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.
- [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
- [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
- [52]J. A. Nelder and R. Mead, “A simplex method for function minimization,” Comput. J., vol. 7, no. 4, pp. 308–313, 1965.DOI
- [53]S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.
- [54]F. Glover, “Tabu search—Part I,” ORSA J. Comput., vol. 1, no. 3, pp. 190–206, 1989.DOI
- [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.
- [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
- [57]F. Wilcoxon, “Individual comparisons by ranking methods,” Biometrics Bull., vol. 1, no. 6, pp. 80–83, 1945.
- [58]B. Efron, “Bootstrap methods: Another look at the jackknife,” Ann. Stat., vol. 7, no. 1, pp. 1–26, 1979.
- [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
- [60]S. Holm, “A simple sequentially rejective multiple test procedure,” Scand. J. Stat., vol. 6, no. 2, pp. 65–70, 1979.DOI
- [61]A. Javadi-Abhari et al., “Quantum computing with Qiskit,” 2024, arXiv:2405.08810.
- [62]C. R. Harris et al., “Array programming with NumPy,” Nature, vol. 585, no. 7825, pp. 357–362, 2020.
- [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
- [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






