⚛️ quantum physics

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

This paper benchmarks the Quantum Approximate Optimization Algorithm (QAOA) as a subproblem solver within an ADMM framework for mixed-binary problems, finding that while QAOA can outperform classical local heuristics in noiseless simulations under specific evaluation criteria, it ultimately fails to deliver superior overall solutions compared to the best classical solvers across the tested problem families.

Original author: Mohammad Arif Hossain, Sanim Yousuf Fahim

Published 2026-11-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original author: Mohammad Arif Hossain, Sanim Yousuf Fahim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of complex decision-making, computers often face problems with millions of possible answers, where finding the single best one is like searching for a needle in a haystack that keeps changing shape. To tackle this, scientists use a strategy called decomposition, which breaks a massive, tangled problem into smaller, manageable pieces that can be solved separately. One popular method for doing this is called the alternating direction method of multipliers, or ADMM. It works by alternating between solving the continuous parts of a problem and the discrete, on-or-off parts, passing information back and forth until the pieces fit together. For years, researchers have wondered if quantum computers, which operate on the strange rules of quantum mechanics, could solve these discrete pieces faster than classical computers. The leading candidate for this job is an algorithm known as the quantum approximate optimization algorithm, or QAOA, which is designed to find good solutions by exploring many possibilities at once. The big question has been whether this quantum approach is actually worth the cost and effort compared to the very strong classical methods we already have.

A team of researchers set out to answer this by putting the quantum algorithm to a rigorous test inside the ADMM framework. They did not just run the quantum computer and hope for the best; they built a fair comparison where both the quantum and classical solvers were given the exact same amount of computational effort, or "budget," to solve the smaller pieces of the puzzle. The study focused on a specific type of problem where the variables are binary, meaning they can only be zero or one. The researchers ran simulations on a noiseless, perfect version of a twelve-qubit quantum computer to see how the quantum solver performed against a suite of classical solvers, including random search, simulated annealing, and more advanced techniques like tabu search. They tested the system on two different types of problem families: one that was relatively smooth and easy, and another that was rugged and difficult, designed to mimic the complex landscapes found in real-world applications.

The most surprising discovery came from how the results were counted. In the world of quantum computing, a single run of an algorithm produces a stream of potential answers, or bitstrings, and the algorithm spends most of its time adjusting its internal settings to improve these answers. The researchers found that the final verdict depended entirely on which answer was chosen to represent the run. If the researchers credited the quantum computer with only its very last set of answers, as is common in some standard software tutorials, the quantum solver performed worse than a simple random search. It failed to find the best solution more often than a computer that just guessed randomly. However, when the researchers credited the quantum solver with its single best answer found at any point during its entire run, the story flipped completely. Under this "best-sample" scoring, the quantum solver outperformed the random search and even beat several sophisticated classical methods on the difficult, rugged problems at the subproblem level. This revealed that the perceived failure of the quantum approach was often an artifact of how the data was scored, not a failure of the physics itself.

When the researchers looked deeper at the performance of a specific version of the quantum algorithm that used pre-trained settings, known as transferred angles, they found it could solve the difficult sub-problems with remarkable accuracy. On the rugged problem family, this quantum approach found the exact best solution more often than tuned local search methods (97.3% versus 67.4% for the strongest local heuristics), though it did not outperform a classical technique based on semidefinite programming (SDP+LS). However, this advantage did not carry over to the final result of the overall problem. The study found that no family gave QAOA a better final ADMM outcome than the best classical solver and penalty. The researchers calculated that for the same problem size, the quantum approach took roughly fifty times longer in seconds than a classical method called tabu search. Furthermore, the quantum method's performance did not scale as well as the classical ones; as the problems grew larger, the quantum solver's advantage in the number of attempts disappeared, and it fell behind a classical technique based on semidefinite programming.

The study also uncovered a subtle but critical flaw in how the decomposition method itself works. The researchers discovered that for certain types of problems, the way the pieces are reassembled depends heavily on a parameter called the penalty. When this penalty was set to a specific value, the decomposition method essentially solved the entire problem directly, making the quality of the sub-solver irrelevant. But when the penalty was higher, the method would sometimes get stuck on a sub-optimal solution, refusing to move forward even if a better one existed. In these cases, the "noisy" nature of the quantum solver, which kept changing its answers, actually helped the system escape these traps and find a better overall solution than a perfect, exact solver that would have gotten stuck. This suggested that the quantum solver's success was not always due to its quantum nature, but sometimes because it behaved like a random search, which is a known way to escape local traps in difficult optimization landscapes.

Ultimately, the paper concludes that while quantum algorithms show promise in solving specific sub-problems with high accuracy, they have not yet demonstrated a clear advantage over the best classical methods when the entire system is considered. The quantum solver did not provide a better final outcome for the overall problem than the best classical solver could achieve with the right settings. The study highlights that for quantum computing to be truly useful in these hybrid systems, it must not only find good answers but do so in less time and with better scaling than the classical alternatives. The researchers found that while the quantum approach could match classical solvers in accuracy under specific conditions, it was significantly slower and did not scale as efficiently. The work serves as a necessary reality check, showing that the path to quantum advantage is not just about building better quantum hardware, but about carefully designing how these machines are used within larger, classical frameworks.

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

Problem Formulation
The paper investigates the efficacy of the Quantum Approximate Optimization Algorithm (QAOA) when employed as the binary subproblem solver within a two-block Alternating Direction Method of Multipliers (ADMM) framework for mixed-binary optimization. The specific problem class studied is the quadratic-plus-convex mixed-binary problem, where continuous variables can be eliminated to reveal an underlying Quadratic Unconstrained Binary Optimization (QUBO) structure. The authors analyze the performance of QAOA against classical solvers under strictly matched objective-evaluation budgets. A critical focus is placed on how the scoring rule—whether crediting the solver with its best sample found during the entire budget or only the best sample from a final "read-out"—impacts the comparative results.

Methodology
The study utilizes a fixed-penalty two-block ADMM scheme (Algorithm 1). In each outer iteration, the continuous variables are updated, and the binary update is delegated to a QUBO solver. The binary subproblem is mathematically characterized as a proximal step on the reduced QUBO problem, where the penalty parameter $\rho$ dictates the nature of the subproblem.

The benchmark compares several solvers under a fixed budget of $B=768$ evaluations per subproblem:

Optimized QAOA: Parameters are optimized per instance using a classical optimizer (COBYLA) with 23 evaluations, followed by a final read-out of 32 shots.
Transferred-Angle QAOA: Parameters are trained offline on smaller instances and fixed for the benchmark. All 768 shots are drawn at these fixed angles.
Classical Baselines: Includes Simulated Annealing (SA), Tabu Search, Parallel Tempering, Local Search, Random Search, and Semidefinite Programming (SDP) rounding with local search (SDP+LS). Tuned versions of these solvers are also included.

Two scoring rules are applied:

Best-Sample Scoring: Credits the solver with the best bitstring found across the entire budget (consistent with how classical heuristics are typically evaluated).
Read-Out Scoring: Credits the solver only with the best bitstring from the final read-out (mimicking the default behavior in the Qiskit Optimization tutorial).

The experiments cover two problem families: a "main" family of random instances and a "planted" family based on the Wishart ensemble with a rugged landscape. Performance is measured by the fraction of subproblems solved exactly, the normalized gap, and the Time to Solution (TTS) at the ADMM level.

Key Contributions

The Decisive Role of Scoring Rules: The authors demonstrate that the choice between read-out and best-sample scoring can reverse the outcome of a matched-budget comparison. With a small training budget (23 optimizer evaluations), optimized QAOA loses to random search under read-out scoring but wins under best-sample scoring. This is attributed to the requirement that the final state must amplify good sets by a factor of $B/R$ (where $R$ is the read-out size) to match random search under read-out scoring, a condition not required for best-sample scoring.
Performance of Transferred Angles: Depth-2 transferred-angle QAOA matches or exceeds tuned classical solvers on the main family and outperforms local heuristics on the rugged planted family in terms of the fraction of subproblems solved exactly. However, this advantage is limited to resolving nearly degenerate states and does not extend to SDP-based solvers or wall-clock time.
Characterization of ADMM Binary Steps: The paper proves (Theorem 1) that for the studied problem class, the binary subproblem is a proximal step on the reduced problem. Crucially, it shows that for penalties $\rho > 1$ , exact solvers can "stall" at suboptimal bitstrings, whereas noisy solvers (like QAOA or random search) may continue to explore and escape these stalling points, leading to better ADMM-level outcomes despite lower subproblem accuracy.
Benchmark Protocol with Correctness Gates: The study introduces a rigorous benchmark protocol including correctness gates at the matrix, circuit, and sampling levels, and maintains a log of hypothesis tests to ensure statistical validity.

Results

Scoring Reversal: At $n=12$ and $n=16$ , optimized QAOA significantly underperforms random search under read-out scoring but significantly outperforms it under best-sample scoring.
Subproblem Accuracy: Transferred-angle QAOA solves nearly 100% of subproblems exactly on the main family and 97.3% on the planted family, outperforming local heuristics (which solve 50.6%–67.4% on the planted family) but performing comparably to SDP+LS.
Time to Solution (TTS): While transferred QAOA requires fewer evaluations than local heuristics to find the optimum on the planted family, its TTS scales with a larger exponent. In wall-clock time (seconds), it is significantly slower (10 to 54 times) than classical solvers like SDP+LS and Tabu Search.
ADMM-Level Outcomes: Higher subproblem accuracy does not guarantee better ADMM outcomes. For $\rho > 1$ , exact solvers often stall at suboptimal points, while noisy solvers (including random search) find the global optimum more frequently. No QAOA configuration yielded a better ADMM outcome than the best classical solver and penalty combination across any tested family.

Significance and Claims
The paper modestly claims that it does not demonstrate a quantum advantage. Instead, it highlights that the perceived success of QAOA in decomposition methods is highly sensitive to evaluation protocols (scoring rules) and problem structure (penalty parameters). The authors argue that for QAOA to demonstrate a genuine advantage in such hybrid frameworks, it must achieve a better scaling exponent than the strongest classical solvers (including SDP-based ones) in wall-clock time, not just in evaluation counts, and must operate on problem families where decomposition does not simply reduce to solving the original problem directly. The study serves as a cautionary benchmark, emphasizing that "subproblem wins" do not automatically translate to "decomposition wins."

More like this