When a quantum subproblem solver makes ADMM worse

How should a solver be judged when it proposes many candidate answers but reports only a few? This matters when the solver is part of a larger algorithm: a strong answer to one subproblem need not produce the best final solution.

In a preprint posted to arXiv, Mohammad Arif Hossain and Sanim Yousuf Fahim examine this issue for the quantum approximate optimization algorithm (QAOA), a quantum circuit method for searching binary choices. They use it as the binary-step solver in a two-block version of the alternating direction method of multipliers (ADMM). ADMM alternates between updating continuous variables and binary ones, while adjusting a coupling term to encourage consistency. The authors compare QAOA with classical search methods under equal counts of objective evaluations, then ask whether subproblem performance translates into better full-problem outcomes.

What counts as a win?

The benchmark distinguishes two ways to score optimized QAOA. In its final-readout score, only the best bitstring from the last 32 measurement shots counts. In best-sample scoring, the best candidate from all 768 shots drawn during the run counts, matching how classical search methods are credited for their best result. The optimizer receives 23 batches of 32 shots before that readout.

For the main tests at 12 binary variables, optimized depth-2 QAOA lost to random search when judged by the final readout, but won when judged by its best sample from those very same runs. In the independent-draw replicate, its best-sample score solved 64.1% of subproblems exactly, compared with 17.7% for random search; the readout score solved 21.4%. The authors explain the reversal mathematically: when 768 candidates are paid for but only 32 are scored, the final quantum state needs to concentrate probability on good answers to compensate for the discarded samples. This is an accounting lesson for this setup, not a general claim that readout scoring always hurts QAOA. A longer angle-optimization run could change the balance.

A solver inside a solver

The paper also tests transferred-angle QAOA: circuit angles trained once on small instances and reused as ADMM’s binary subproblem changes. In noiseless simulation on a deliberately rugged, planted family of 12-variable problems, depth-2 transferred QAOA found the exact subproblem optimum in 97.3% of cases. The four strongest local heuristics ranged from 50.6% to 67.4%; semidefinite rounding followed by local search reached 96.5%, not significantly different from QAOA. That edge was narrow: the planted instances have near-complement symmetry, so many misses were nearly degenerate alternatives. QAOA’s advantage over local heuristics was a prefactor in evaluation counts, but its estimated scaling exponent was larger; it had no advantage over the semidefinite method, and took about 54 times as long as tabu search with restarts in seconds at 12 variables.

Why might better subproblem answers fail to help ADMM? For the paper’s main mathematical model, the authors prove that from the second iteration onward, ADMM’s binary step is a proximal version of the reduced full problem. At penalty one, an exact subproblem solver solves that reduced problem again at every step. At larger penalties, even exact solutions can settle at suboptimal “stalling” points. In two additional synthetic families that do not have this reduction, the less accurate solvers more often found the original problem optimum at unit or higher penalties.

Across the tested families, no QAOA configuration and penalty produced a better ADMM outcome than the best classical solver-and-penalty choice. The result is about specific synthetic benchmarks, not a proof that QAOA cannot help other optimization tasks. The authors studied fixed-penalty, two-block ADMM, not the adaptive three-block variant used in a common tutorial; the planted cases use one ensemble setting, and most evaluations were simulations. They report a circuit-sampler flaw that reused random numbers across optimizer calls, making parts of the optimized-QAOA comparison less reliable; an independent-draw replication supported the scoring reversal. The work is a preprint, not evidence of a hardware speedup.