CS Paper Radar

Initialization masks overcome decoding obstructions in compressed QAOA

Emilio Semre, Steven Frankel

cs.CC quant-ph ·submitted 2026-11-07 08:52 UTC · v1

Abstract

In compressed quantum optimization, a variational state is converted into a classical assignment by decoding noncommuting observables. We show that this step creates structural restrictions that changing the initialization can remove, even when increasing circuit depth cannot. For an explicit infinite family of connected cubic graphs on $n=3r$ vertices, with a fixed Pauli encoding and deterministic sign decoder, every all-plus QAOA circuit has cut at most $2r$, at every finite depth and every real angle sequence. A uniform signed product-state mask at fixed depth-one angles has expected cut $13r/4$, an additive advantage $5n/12$; an infinite subfamily admits an optimal mask. A second construction retains a linear depth-one separation under weak weighted couplings, a bounded cost-angle domain and a specified production-encoder ordering. Noiseless simulations then test classical mask selection before energy optimization. On 1,699 random cubic MaxCut instances, one selected mask achieves mean ratio $0.9100$, versus $0.7067$ for the all-plus $X$ baseline and $0.9125$ for the best of $r^2$ separately optimized random masks. On complete cohorts of weighted MaxCut, sparse Ising, Max-2-XOR and Max-2-SAT, the selected mask also improves on the baseline at every size, but it trails the pool at small sizes and leads it significantly only at the larger MaxCut and Ising sizes. Finite-pool order statistics separate the effect of selection from that of drawing a random mask. The results distinguish decoded expressivity from optimized energy and empirical performance; they do not establish a quantum computational advantage.

Comment
24 pages, 6 figures, including technical appendices

Closest papers

Nearest neighbours by meaning across the whole index.

Complexity Amplification from Compression in Quantum Random Access Optimization

cs.CC quant-ph ·2026-09-07 ·Stuart Hadfield
similarity 0.69
Abstract · Abstract shortened for arxiv submission

Compressed quantum encodings aim to overcome hardware limitations towards tackling challenging problems at scale, with many classical variables mapped onto noncommuting observables of fewer qubits. Classically, relaxations such as the semidefinite program formulation of MaxCut trade solution quality for computational efficiency. By contrast, quantum relaxations based on compression can amplify the worst-case complexity of the problem being solved. We study quantum random access optimization (QRAO), a special case of the Pauli correlation encoding (PCE) framework that assigns up to three binary variables to the Pauli $X$, $Y$, and $Z$ observables of each qubit, with the packing choices determining the compressed Hamiltonian to be optimized. We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two. Our problem reductions preserve inverse-polynomial promise gaps without requiring gadgets or ancillas. For any prescribed packing, we show that weighted MaxCut instances compress, up to a known shift and rescaling, to arbitrary nonnegative-weight pairwise Pauli couplings allowed by the packing. For QRAO, using one aligned axis gives an NP-complete energy problem. Using two or three positive aligned Pauli axes generally gives QMA-complete problems, with bipartite restrictions in BQP $\cap$ StoqMA. We show that this computational hardness survives compilation and is practically relevant. Notably, this result applies directly to the current QRAO compiler implementation in Qiskit Optimization 0.7.0, confirming our hardness results are not artifacts of artificial or contrived packing rules. Altogether our results identify worst-case complexity barriers arising from quantum compression, while making no broad claims about typical cases or the performance and trainability of algorithm pipelines that use it.

0.43

Complexity Barriers to State Preparation in Quantum Approximate Optimization

cs.CC quant-ph ·2026-09-25 ·Stuart Hadfield
theoryhighly cited similarity 0.68
Abstract

For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $Θ(1/n)$, while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.

0.39

Beyond the Mean Gap: What Transferred-Angle QAOA Retains on a Superconducting Processor

cs.AI quant-ph ·2026-11-07 ·Sanim Yousuf Fahim, Mohammad Arif Hossain
similarity 0.67
Abstract

Hardware executions of the quantum approximate optimization algorithm (QAOA) are often validated by comparing the device's mean cost with a simulation, a check that can miss what matters for optimization. Under global depolarization, the mean normalized gap and the floor-corrected probability of every set of bitstrings, the optimum included, retain the same fraction of their noiseless improvement over uniform sampling. We test this prediction with depth-2, transferred-angle QAOA circuits for binary subproblems of an alternating-direction decomposition on the IBM Heron processor \texttt{ibm\_marrakesh}, with and without dynamical decoupling and twirling. At 12 qubits, the main-family circuits retained 29\% to 46\% of their mean-gap improvement but only 5\% to 15\% of their probability of the optimum, lower on at least nine of ten instances per run. Near-optimal bitstrings were lost about as much as the optimum, whereas the avoidance of poor bitstrings was retained best. In the first submission, a device-matched noise model reproduced the pattern but overestimated the retention of the optimum five- to eightfold. On a rugged planted family, the device found the optimum in 62\% of 768-shot blocks (noiseless: 98\%), within the range of local heuristics. Validations of optimization circuits should report retention of the optimum and of near-optimal sets.

0.26

Rand-SEMI-QAOA: Finite-Budget Depth-One MaxCut Ensembles on Compressed Quantum Registers

cs.ET quant-ph ·2026-08-16 ·Emilio Semre, Steven Frankel
similarity 0.66
Abstract · 27 pages, 4 figures

We introduce Rand-SEMI-QAOA, a finite-budget QRAO--QAOA ensemble for MaxCut based on a $(3,1)$-QRAC relaxation. The method samples labels uniformly without replacement from the product-$X$ family of an implemented Galois stabilizer mutually unbiased basis (MUB) system. Each selected state--mixer pair is optimized independently for relaxed QRAO energy and then evaluated by deterministic Pauli-sign decoding. Exhaustive scans of the implemented noncomputational MUB catalog place the product-$X$ family first in 18 of 20 validated family-mean cells and in every tested cell for $r=5,6,7$. On a complete cohort of $2{,}400$ random connected 3-regular MaxCut instances with $n\in\{18,20,22\}$, the capped matched-cardinality schedule attains a graph-mean decoded best-of-set approximation ratio of $0.9421$ with one QAOA layer, while the $K=r^2$ schedule attains $0.9319$. These statistics are conditional on the disclosed frozen selector pools and do not estimate variability over selector seeds. An exact gauge identity shows that product-family labels generate the orbit of the QRAO Hamiltonian under an $r$-dimensional sign-gauge group. For common angles and relaxed energy, deterministic syndrome analysis proves branchwise dephasing, while an anisotropic Gaussian surrogate controls the coherent label-averaged response on the scale $β=b/r$. The theory does not order independently optimized decoded maxima. The results are finite-size and resource-explicit and do not establish quantum advantage.

0.47

QAOA for Layered Architecture Recovery: Feasibility, Limits, and the Role of Decomposition

cs.SE ·2026-11-06 ·Julien Cardinal, Andrew Chedid, Imen Benzarti, Ghizlane El Boussaidi, Christophe Pere +1 more
similarity 0.66
Abstract

Layered architecture recovery (LAR) reconstructs a system's architectural layers from its package dependencies, and is defined as a combinatorial optimisation problem solved with classical search. We investigate whether the Quantum Approximate Optimization Algorithm (QAOA) can be applied to LAR, and with what practical limitations. We formulate LAR as a Quadratic Semi-Assignment Problem, transform it into a Quadratic Unconstrained Binary Optimisation (QUBO) problem in which each package is penalised unless it is assigned to exactly one layer, and encode it as an Ising Hamiltonian solved by QAOA. To reach instances beyond the qubit budget of a single circuit, we also apply an impact-guided decomposition that solves the problem as a sequence of smaller sub-problems. We evaluate the approach on three real Java systems ($15$, $18$, and $24$ qubits), studying the effect of circuit depth and sampling budget (RQ1), a comparison with a classical Tabu Search baseline (RQ2), robustness to simulated quantum noise (RQ3), and the decomposition (RQ4). We find that monolithic QAOA is feasible and accurate on the two smaller systems but fails on the $24$-qubit instance, that the sampling budget rather than circuit depth governs its accuracy, and that it is competitive with but does not outperform Tabu Search. Decomposition restores reliable recovery on the $24$-qubit instance, raising the optimal rate from $6.7\%$ to $93.3\%$; its accuracy is governed by the size of each sub-problem and, unlike the monolithic pipeline, improves as the sampling budget is reduced. Our results indicate that, in the current noisy intermediate-scale regime, problem decomposition, rather than larger circuits or more sampling, is the key to applying QAOA to software architecture recovery.

0.28

Exact Diagonal Completion on Reachable Subspaces: Application to QAOA Placement

cs.AR quant-phcs.ET ·2026-09-30 ·Owen Friedewald, Ali Shiri Sichani, Chi-Ren Shyu
hot direction similarity 0.65
Abstract · 26 pages, 5 figures, Under review at ACM Transactions on Quantum Computing

Unused encoding states offer opportunities to simplify quantum circuits. For algorithms restricted to reachable subspaces, unspecified diagonal-operator entries can be optimized without changing ideal computation. We investigate exact diagonal completion for the quantum approximate optimization algorithm (QAOA) applied to placement, using permutation-preserving register swaps. We construct exact Manhattan-distance operators through weighted-$\ell_1$ optimization of Walsh coefficients and a sparse recurrence requiring $O(\sqrt{m})$ terms on balanced rectangles, avoiding $O(m^4)$ dense constraint storage. Across 160 geometries, weighted-$\ell_1$ completion reduces controlled-NOT (CX) counts relative to four alternative extensions in all 96 cases with unused binary codes under Gray-code synthesis. On an independently specified 60-case cohort, median reductions relative to virtual-coordinate extension are 28.0\%, 53.9\%, and 21.6\% at six, nine, and twelve sites. Under generic diagonal synthesis, reductions decrease to 10.9\%, 1.3\%, and 0.7\%, demonstrating compiler dependence. Additional ancillas reduce mixer serialization, but token circuits remain deeper than one-hot baselines. Ideal placement simulations show baseline-dependent solution quality, with classical search performing better. OpenROAD integration takes 72 QAOA and 216 classical placements across six RTL designs through clock-tree synthesis and global routing with zero overflow. Completion improves phase construction; no end-to-end advantage is established.

0.36

Plateau-Constrained Selection: Exploiting Degeneracy for Lower-Depth Quantum Compilation

cs.ET quant-ph ·2026-08-27 ·Owen Friedewald, Ali Shiri Sichani, Chi-Ren Shyu
theory similarity 0.63
Abstract · 11 pages, 4 figures. Under review at IEEE Transactions on Quantum Engineering

Minimum-cost orders of commuting phase terms can produce substantially different routed circuits. On the same 36-term instances, three orders with identical support cost 74 yield mean routed depths of 228.6, 233.8, and 256.7. We exploit this degeneracy under fixed placement and maintained-parity lowering: Stage 1 attains the support optimum, and Stage 2 selects minimum routed depth among 24 equal-cost orders. For distinct pair supports, we characterize orders attaining the support lower bound through Hamiltonian paths of the support line graph and count optima exactly through 20 terms. On synthetic 16-qubit assignment-Ising instances, selection reduces depth by 12.83% under a different SABRE routing seed, with lower depth in all 20 instances. The selected orders lie a median 1.57 pool standard deviations below the pool mean, consistent with ordinary best-of-24 selection; the useful feature is that candidate rankings persist across routing seeds. Depth reductions extend to 48 terms and a random-MaxCut generator, whereas evaluation with BasicSwap reverses the gain. A 40-instance IBM Heron study measures a 0.59% error reduction on the executed stabilizer-probe panel, but the primary confidence interval across instances includes zero. Plateau selection therefore improves routed depth in the tested SABRE pipeline while preserving the logical support optimum.

0.49

Evaluating QAOA expectation values can be as hard as counting optimal solutions

cs.CC quant-ph ·2026-08-11 ·Stuart Hadfield
similarity 0.63
Abstract

Evaluating expectation values is a critical task for variational quantum eigensolvers, parameterized quantum circuits, and many other quantum algorithms. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth $p\geq 2$, complementing past results showing efficiently computable formulas for $p=1$ with arbitrary problem graphs. We sharpen this dichotomy showing that for $p\geq 2$ exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at $p\geq 2$ is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from $p=1$ to $p=2$ is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.

0.40