pith. machine review for the scientific record. sign in

arxiv: 1411.4028 · v1 · submitted 2014-11-14 · 🪐 quant-ph

Recognition: 4 theorem links

· Lean Theorem

A Quantum Approximate Optimization Algorithm

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Authors on Pith no claims yet

Pith reviewed 2026-05-09 01:30 UTC · model claude-opus-4-7

classification 🪐 quant-ph MSC 68Q1281P6890C27 PACS 03.67.Ac03.67.Lx
keywords quantum approximate optimizationQAOAMaxCutcombinatorial optimizationadiabatic quantum computationbounded-degree graphsvariational quantum algorithmsapproximation ratio
0
0 comments X

The pith

A depth-p alternation of cost and mixer unitaries gives a tunable quantum approximation algorithm with a 0.6924 guarantee for MaxCut on 3-regular graphs at p=1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a recipe for approximate combinatorial optimization on a quantum computer: prepare the uniform superposition, then apply p alternations of two unitaries — one generated by the objective function C, one generated by a sum of single-qubit X operators — and measure. The 2p angles are tuned to maximize the expected objective. Two pieces of structure make the recipe usable. When the objective is local and each variable appears in a bounded number of clauses, the expected value at fixed p depends only on counts of small subgraph types, so the best angles can be found classically without scaling in n. And as p grows, the construction becomes a Trotterized adiabatic path, so the achievable expectation converges to the true optimum. Concretely, on the 2-regular ring the algorithm reaches an approximation ratio (2p+1)/(2p+2) at depth independent of n, and on every 3-regular graph it returns a cut at least 0.6924 times optimal already at p=1.

Core claim

The authors propose a family of quantum algorithms, indexed by an integer p, that approximate the maximum of a combinatorial objective function C by preparing a state of the form U(B,β_p)U(C,γ_p)···U(B,β_1)U(C,γ_1)|s⟩ — alternating evolutions under the cost Hamiltonian C and a transverse-field mixer B — and then measuring. Two structural facts make this more than a heuristic. First, for bounded-degree problems with fixed p the expected cut value depends only on local subgraph counts, so the optimal angles can be found by a classical preprocessor whose cost is independent of n. Second, as p→∞ the construction is a Trotterization of an adiabatic path, so M_p approaches the true optimum. As a w

What carries the argument

The state |γ,β⟩ = ∏_{k=1}^{p} U(B,β_k)U(C,γ_k)|s⟩, where U(C,γ)=e^{−iγC} encodes the objective and U(B,β)=e^{−iβ∑σ^x_j} is a transverse-field mixer. Locality of C makes the expected cost a sum over local subgraph contributions f_g(γ,β) weighted by subgraph counts w_g, so optimization over angles decouples from n. Taking p→∞ with small angles recovers a Trotterized adiabatic evolution from B to C, which by Perron–Frobenius reaches the top eigenstate of C.

If this is right

  • For any bounded-degree constraint problem and any fixed p, the angles that maximize the expected objective can be precomputed classically using only local subgraph statistics; the quantum computer is then run with one fixed parameter set.
  • Circuit depth scales as O(pm) in the worst case and as O(p) when the constraint graph admits a constant-color edge decomposition (as on the ring), so the algorithm fits naturally on shallow-depth quantum hardware.
  • Increasing p is monotone (M_p ≥ M_{p−1}) and reaches the global optimum in the limit, giving a tunable depth-vs-quality dial absent from one-shot adiabatic runs.
  • On the n-vertex ring, p as small as O(1) suffices to get within additive O(1) of the optimal cut, with circuit depth independent of n.
  • The same alternating-unitary template extends to constrained search: replacing B with the adjacency operator on legal strings (e.g., independent sets) yields a quantum-walk variant that still has an adiabatic limit theorem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Because F_p is a sum of fixed local functions weighted by subgraph counts, the optimal angles for one instance transfer to other instances with similar local statistics — suggesting that angle-finding on small graphs can be reused on much larger ones in the same problem family.
  • The 0.6924 figure is set by the worst point on the (s,t) simplex, which lies at s=t=0 (no triangles, no crossed squares); locally tree-like 3-regular graphs are therefore the hard case for p=1, and instances rich in short odd cycles should fare strictly better.
  • The independent-set variant points toward a general design principle: replace the hypercube mixer by the adjacency operator of the feasible-set graph to bake hard constraints directly into the unitary, trading a tensor-product Hilbert space for a problem-specific one.
  • Monotonicity in p plus the adiabatic limit means that, in principle, gathering data at successive p values gives an a priori certificate that the ceiling has not yet been reached — useful as a stopping criterion when running on real hardware.

Load-bearing premise

The 0.6924 bound rests on numerical (not closed-form) optimizations: the maximum of F_1 over three subgraph types and the minimum of a two-variable ratio over a triangle-square density region, combined with a simple upper bound on the true MaxCut that ignores graph structure beyond isolated triangles and crossed squares.

What would settle it

Find a connected 3-regular graph and a setting of (γ_1,β_1) achieving the optimum of F_1 such that, after enough samples, the measured cut value divided by the true MaxCut is below 0.6924; equivalently, exhibit a point (s,t) in the feasible region 4s+3t≤1, s,t≥0 where M_1(1,s,t)/(3/2 − s − t) drops below 0.6924.

read the original abstract

We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer p and the quality of the approximation improves as p is increased. The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought. The depth of the circuit grows linearly with p times (at worst) the number of constraints. If p is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing. If p grows with the input size a different strategy is proposed. We study the algorithm as applied to MaxCut on regular graphs and analyze its performance on 2-regular and 3-regular graphs for fixed p. For p = 1, on 3-regular graphs the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal cut.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

4 major / 7 minor

Summary. The authors introduce a general quantum algorithm (QAOA) for approximate combinatorial optimization. For an instance with objective C = Σ_α C_α and mixing operator B = Σ_j σ^x_j, the algorithm prepares |γ,β⟩ = U(B,β_p)U(C,γ_p)···U(B,β_1)U(C,γ_1)|s⟩ and measures in the computational basis. They establish: (i) circuit depth grows linearly with p times (at worst) m; (ii) for fixed p and bounded-occurrence instances, F_p decomposes into a finite sum over local subgraph types, giving an efficient classical procedure to find optimal (γ,β) (§II); (iii) lim_{p→∞} M_p = max_z C(z) via Trotterized adiabatic evolution (§VI); (iv) for MaxCut on the 2-regular ring, M_p = n(2p+1)/(2p+2) (numerically verified for p≤6); (v) for MaxCut on connected 3-regular graphs, p=1 gives an approximation ratio ≥ 0.6924 (§V). A variant for constrained problems (independent set) is proposed in §VII.

Significance. This paper introduces a clean, broadly applicable variational quantum algorithmic framework that is now a foundational reference in near-term quantum optimization. The formulation is transparent, the locality/depth bounds are honest, the reduction to a finite set of subgraph functions (§II, Eqs. 24–25) is a genuinely useful structural result, and the connection to Trotterized adiabatic evolution (§VI) is correctly identified as a convergence proof rather than a practical strategy. The 3-regular MaxCut p=1 worst-case ratio (§V) provides a concrete, falsifiable performance guarantee on a nontrivial problem class, and the comparison to known classical algorithms is appropriately candid (the authors note the bound is weaker than Halperin–Livnat–Zwick). The independent-set variant (§VII), with B taken as the adjacency matrix of the legal-subspace hypercube, is a novel suggestion for handling constrained search spaces. The work is short, clearly written, and makes its limitations explicit.

major comments (4)
  1. [§V, Eq. (35) and the 0.6924 claim] The headline approximation ratio 0.6924 is reported as the result of a numerical minimization of M_1(1,s,t)/(3/2 − s − t) over {s,t ≥ 0, 4s+3t ≤ 1}, with the minimum asserted at s=t=0. Two pieces are not made rigorous in the manuscript: (a) that the joint maximization of F_1(γ,β) over (γ,β) (whose optimizer depends on (s,t)) produces a ratio that is genuinely minimized at the corner s=t=0 rather than at, e.g., s=1/4,t=0 (pure crossed-square saturation) or some interior point; (b) the discretization/precision of the numerical search. f_{g4}, f_{g5}, f_{g6} are closed-form trigonometric polynomials in (γ,β), so an analytic or interval-arithmetic argument should be feasible. Please either provide the closed-form expressions for f_{g_i}(γ,β) and a short analytic argument that the corner is the minimizer, or document the grid resolution and a Lipschitz/derivative bound that certifies the nume
  2. [§IV, ring of disagrees] The statement 'M_p = n(2p+1)/(2p+2) for all p' is supported by numerical maximization to 13 decimal places for p=1,…,6 and then extrapolated. Given that for the ring the subgraph is a single 2p+2 line segment, the f_g(γ,β) is a moderately small trigonometric expression and a clean inductive or generating-function proof seems within reach. Since this is the only closed-form performance claim for arbitrary p in the paper, an analytic proof (or at least a clear statement that the formula is conjectural beyond p=6) would substantially strengthen §IV.
  3. [§V, denominator bound] The denominator in (34)–(35) uses MaxCut ≤ 3n/2 − S − T, which is tight only for graphs whose only odd-cycle obstructions are isolated triangles and crossed squares. At s=t=0 it gives 3n/2, attainable only on bipartite 3-regular graphs, so the ratio at the corner is M_1/(3n/2). It would be helpful to state explicitly that 0.6924 is therefore a lower bound on the true worst-case approximation ratio (since the true optimum is generally smaller than 3n/2 − S − T), and to indicate whether the authors expect the true ratio at p=1 to be meaningfully larger.
  4. [§II, classical preprocessing cost] The text states the classical preprocessing 'could require space doubly exponential in p' (§VIII). For a reader trying to gauge the practical regime where the fixed-p algorithm is useful, a more precise statement of the scaling of the classical optimization of F_p in p and v (degree) — even just the dimension 2^{q_tree} from Eq. (26) and the cost of optimizing in 2p continuous angles — would be valuable. This is presentation-level but load-bearing for the 'efficient classical preprocessing' claim in the abstract.
minor comments (7)
  1. [Eq. (24)] Typographical: U(B_{g(j,x)}β_p) should presumably be U(B_{g(j,k)},β_p).
  2. [§II, Eq. (18)] The three subgraph types g_4, g_5, g_6 are referenced verbally in §V but the labels do not appear in the figure (18). Adding the labels under the figure would aid the reader.
  3. [§III, Eq. (30)] The bound is stated for v,p fixed, but the special case v=2 gives 4p+4 rather than the formula evaluated at v=2 (which is indeterminate). Please consolidate the v=2 caveat into a single footnote rather than repeating in (26) and (29).
  4. [§V, p=2 paragraph] The 0.7559 figure for the 14-vertex tree subgraph is presented without specifying numerical method or precision; one sentence on the optimization (grid + local refinement, dimension 4) would help reproducibility.
  5. [§VII, Eq. (41)] The variant uses p real numbers b and only p−1 angles γ, breaking the symmetry with the basic algorithm (6). A brief remark on why the final U(C,γ) is dropped (since |z=0⟩ is already a C-eigenstate, an initial U(C,γ_0) is a global phase) would clarify the indexing.
  6. [Abstract / §I] The abstract says 'positive integer p' while §I writes 'integer p ≥ 1'; consistent phrasing is fine.
  7. [References] It would be useful to cite the Goemans–Williamson 0.878 SDP bound for MaxCut alongside [1] when contrasting with classical algorithms in §V.

Simulated Author's Rebuttal

4 responses · 0 unresolved

We thank the referee for a careful and constructive report and for the recommendation to accept. The four major comments all concern places where the manuscript's claims are correct but their rigor or presentation can be tightened, and we agree with each. In revision we will: (1) supplement the 0.6924 claim in §V with the closed-form expressions for f_{g4}, f_{g5}, f_{g6}, an argument exploiting affineness of F_1/n in (s,t), and an explicit grid/derivative certificate; (2) restate the ring-of-disagrees formula M_p = n(2p+1)/(2p+2) as a conjecture proved numerically for p≤6, and indicate the free-fermion route to a full proof; (3) state explicitly that 0.6924 is a lower bound on the true worst-case p=1 ratio, since the denominator 3n/2 − S − T is tight only on bipartite 3-regular graphs at the corner; and (4) replace the loose 'efficient classical preprocessing' language with a precise statement of the 2^{q_tree} scaling from Eq. (26), clarifying that efficiency is in n at fixed (p,v). None of these revisions alter the technical content of the paper; they sharpen the statements the referee correctly identified as load-bearing.

read point-by-point responses

  1. Referee: §V, Eq. (35), 0.6924 claim: the minimization of M_1(1,s,t)/(3/2 − s − t) over the feasible region is asserted to occur at the corner s=t=0 on numerical grounds. Please either give closed-form f_{g_i}(γ,β) and a short analytic argument that the corner is the minimizer, or document grid resolution and a Lipschitz/derivative bound that certifies the numerical conclusion.

    Authors: We agree this point deserves to be made rigorous. The functions f_{g4}, f_{g5}, f_{g6} are indeed closed-form trigonometric polynomials in (γ_1,β_1) of low degree (at most degree 4 in cos/sin of γ_1 and degree 2 in cos/sin of 2β_1), obtainable by direct expansion of (24) on the three subgraphs in (18). In the revised version we will (a) record the explicit closed forms of f_{g4}, f_{g5}, f_{g6}; (b) note that for fixed (s,t), F_1/n is the affine combination s·f_{g4} + (4s+3t)·f_{g5} + (3/2 − 5s − 3t)·f_{g6}, so M_1(1,s,t) is a maximum of an affine family in (s,t) and is therefore convex in (s,t); (c) give a derivative bound on (35) that, combined with a grid of spacing 10^{-3} in (γ,β) and 10^{-3} in (s,t), certifies the minimum at the corner s=t=0 to the stated four digits. The grid resolution actually used was finer than this (sub-millradian), and the second-best candidate corner s=1/4, t=0 was checked separately and gives a strictly larger ratio. A formal interval-arithmetic certification is straightforward but we did not include it in v1. revision: yes

  2. Referee: §IV, ring of disagrees: M_p = n(2p+1)/(2p+2) is verified numerically to 13 decimals for p≤6 and extrapolated. An analytic proof, or at least a clear statement that the formula is conjectural beyond p=6, would strengthen §IV.

    Authors: The referee is correct that we have not given a proof. For p≤6 the numerics agree with n(2p+1)/(2p+2) to the precision stated, which is why we wrote 'we conclude'; strictly speaking the statement for general p is a conjecture supported by these six data points and by consistency with the p→∞ adiabatic limit (10). We will rephrase §IV to state this explicitly: the formula is a conjecture proved for p≤6 by direct numerical maximization of (24) on the 2p+2-vertex line segment, with the closed-form value matching to 13 decimal places. We agree a clean inductive or generating-function proof exploiting the line-segment structure looks within reach (the relevant subgraph operator decouples into Jordan–Wigner free fermions on an open chain, and the optimization at level p reduces to a quadratic form), and we will note this as the natural route to a proof, but we do not include it in this version. revision: yes

  3. Referee: §V, denominator bound: the bound MaxCut ≤ 3n/2 − S − T is tight only when the only odd-cycle obstructions are isolated triangles and crossed squares; at s=t=0 it is 3n/2, attainable only on bipartite 3-regular graphs. Please state explicitly that 0.6924 is a lower bound on the worst-case approximation ratio and indicate whether the true ratio at p=1 is expected to be larger.

    Authors: We agree and will say so explicitly. The quantity 0.6924 is a lower bound on the true worst-case p=1 approximation ratio: at the corner s=t=0 the bound 3n/2 − S − T equals 3n/2, which is achieved by the maximum cut only on bipartite 3-regular graphs; for non-bipartite graphs with no isolated triangles or crossed squares the true MaxCut is strictly less than 3n/2, so the true ratio is strictly larger than M_1/(3n/2) at the worst case. We expect the true worst-case p=1 ratio to be modestly larger than 0.6924, but pinning it down requires using a tighter upper bound on MaxCut as a function of additional graph statistics (e.g., short odd-cycle counts) and we have not done this. The revised §V will add a sentence making the lower-bound nature explicit and noting that closing the gap is left open. revision: yes

  4. Referee: §II/§VIII, classical preprocessing cost: the abstract advertises 'efficient classical preprocessing' while §VIII notes the space could be doubly exponential in p. Please give a more precise scaling of the cost of optimizing F_p in p and v, e.g., the dimension 2^{q_tree} from (26) and the cost of optimizing 2p continuous angles.

    Authors: This is a fair criticism of the presentation. The cost of evaluating each f_g at fixed (γ,β) is dominated by simulating a Hilbert space of dimension at most 2^{q_tree} with q_tree = 2[(v−1)^{p+1}−1]/(v−2) (Eq. 26), i.e., doubly exponential in p for fixed v>2 and exponential in p for v=2. The number of subgraph types is bounded by a function of v and p only, also doubly exponential in p in the worst case. Optimization is over 2p continuous angles on a compact domain; using a grid of polynomial size in n suffices because the partial derivatives of F_p are bounded (as noted after Eq. (8)), but the per-grid-point cost carries the 2^{q_tree} factor. The phrase 'efficient' in the abstract refers to efficiency in n (the cost is independent of n once v and p are fixed), not in p. We will revise §II and §VIII to (i) state the 2^{q_tree} scaling explicitly, (ii) clarify that 'efficient' means 'polynomial in n at fixed p, v', and (iii) flag that for moderate p and v=3 the preprocessing is already demanding. revision: yes

Circularity Check

0 steps flagged

No significant circularity: QAOA's derivation chain is self-contained; the 0.6924 bound is a numerical claim, not a circular one.

full rationale

The paper introduces QAOA and derives its properties from independently-stated definitions. The key claims have content beyond their inputs: (1) Eq. (10), lim_{p→∞} M_p = max_z C(z), is proved via Trotterization of the adiabatic algorithm citing Farhi-Goldstone-Gutmann-Sipser (quant-ph/0001106) — this is a self-citation, but the cited adiabatic theorem result is a well-established external fact, not a load-bearing claim that reduces to the present paper. (2) The ring-of-disagrees result M_p = n(2p+1)/(2p+2) is stated as a numerical observation extrapolated from p≤6, which is a correctness/rigor concern but not circularity — the formula is not defined in terms of itself. (3) The 0.6924 bound for 3-regular MaxCut at p=1 is obtained by (a) deriving F_1 in terms of subgraph contributions f_{g4}, f_{g5}, f_{g6} from the QAOA definition, (b) numerically maximizing over (γ,β), and (c) numerically minimizing the ratio M_1(1,s,t)/(3/2−s−t) over the (s,t) simplex. None of these steps fits a parameter to the data being predicted; the denominator (3n/2−S−T) is a combinatorial counting bound, not a fitted quantity. The reader's skeptical critique is real but it is about numerical rigor and bound looseness, not circularity. The comparison to classical algorithms (Halperin-Livnat-Zwick) is an external benchmark, not a self-citation. Self-citations to [2,3,4,5] are background pointers (adiabatic algorithm, prior counterexamples, quantum walks) that motivate but do not serve as load-bearing premises for the algorithmic results. Score: 1 for the routine self-citation pattern around the adiabatic-limit claim, with no manufactured circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

QAOA introduces no new physical entities and no fitted free parameters in the usual sense — the angles (γ,β) are the variables being optimized, not parameters fitted to benchmark data to make the result come out right. The mathematical scaffolding leans on standard results (adiabatic theorem, Perron–Frobenius, Trotterization, Suzuki–Lie product formula in spirit). The paper's claims rest cleanly on these standard ingredients plus numerical optimization on small fixed-size Hilbert spaces.

pith-pipeline@v0.9.0 · 9488 in / 5784 out tokens · 94439 ms · 2026-05-09T01:30:27.272450+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Forward citations

Cited by 60 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization

    quant-ph 2026-04 unverdicted novelty 8.0

    A new qubit-efficient HUBO encoding for graph partitioning problems like minimum coloring uses logarithmic bits and a lexicographic penalty to cut resources while providing provable optimality conditions.

  2. Enabling Lie-Algebraic Classical Simulation beyond Free Fermions

    quant-ph 2026-04 unverdicted novelty 8.0

    New Pauli orbit and modified Gell-Mann bases enable polynomial-cost Lie-algebraic simulation for permutation-equivariant and bounded-excitation quantum dynamics.

  3. QLAM: A Quantum Long-Attention Memory Approach to Long-Sequence Token Modeling

    cs.LG 2026-05 unverdicted novelty 7.0

    QLAM extends state-space models with quantum superposition in the hidden state for linear-time long-sequence modeling and reports consistent gains over RNN and transformer baselines on sequential image tasks.

  4. QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning

    quant-ph 2026-05 unverdicted novelty 7.0

    QAP-Router models qubit routing as dynamic QAP and applies RL with a solution-aware Transformer to cut CNOT counts by 12-30% versus industry compilers on real circuit benchmarks.

  5. TuniQ: Autotuning Compilation Passes for Quantum Workloads at Scale for Effectiveness and Efficiency

    quant-ph 2026-05 unverdicted novelty 7.0

    TuniQ uses RL with a dual-encoder, shaped rewards, and action masking to autotune quantum compilation passes, improving fidelity and speed over Qiskit while generalizing across backends and scaling to large circuits.

  6. Decoded Quantum Interferometry for Weighted Optimization Problems

    quant-ph 2026-05 unverdicted novelty 7.0

    The work develops multivariate DQI states for weighted Max-LINSAT over prime fields, derives closed-form asymptotic expressions for expectation values and concentration, provides an explicit single-decoder preparation...

  7. Optimal FALQON for Quantum Approximate Optimization via Layer-wise Parameter Tuning

    quant-ph 2026-05 unverdicted novelty 7.0

    Optimal FALQON optimizes per-layer δ_k and M_k via classical methods, yielding statistically significant gains in success probability and efficiency over standard FALQON on 94 non-isomorphic 3-regular graphs with 12 vertices.

  8. Per-Phase Fidelity Attribution for Quantum Compilers using HBR Decomposition

    cs.ET 2026-05 unverdicted novelty 7.0

    HBR decomposition quantifies per-phase fidelity loss in quantum compilers, revealing that routing causes up to 60% loss in search circuits while synthesis dominates Hamiltonian simulation, and correctly predicts SDK r...

  9. Breaking QAOA's Fixed Target Hamiltonian Barrier: A Fully Connected Quantum Boltzmann Machine via Bilevel Optimization

    quant-ph 2026-05 unverdicted novelty 7.0

    A bilevel optimization method turns QAOA into a fully connected QBM that achieves 0.9559 target state probability noiseless and retains top probability under realistic noise levels.

  10. The finite-shot help-harm boundary of zero-noise extrapolation

    quant-ph 2026-05 unverdicted novelty 7.0

    Zero-noise extrapolation has a finite-shot help-harm boundary below which it increases local mean-squared error due to variance penalties outweighing bias reduction.

  11. Adversarial Effects on Expressibility and Trainability in Distributed Variational Quantum Algorithms

    quant-ph 2026-05 unverdicted novelty 7.0

    Adversaries perturbing shared entanglement in distributed VQAs can manipulate a new Kraus expressibility metric to keep gradients large but steer training to incorrect solutions.

  12. Constraint Preserving XY-Mixers under Trotterized Adiabatic Evolution

    quant-ph 2026-05 unverdicted novelty 7.0

    Trotter errors in XY-mixers scale with individual constraint size and locality rather than total problem size, making them superior to X-mixers for local constraints but inferior for global ones, with a new mixer prop...

  13. Q3SAT-GPT: A Generative Model for Discovering Quantum Circuits for the 3-SAT Problem

    quant-ph 2026-04 unverdicted novelty 7.0

    A generative model learns patterns from adaptive QAOA circuits to generate high-quality shallow quantum circuits for Max-E3-SAT that scale better than variational baselines.

  14. Formulating Subgroup Discovery as a Quantum Optimization Problem for Network Security

    quant-ph 2026-04 unverdicted novelty 7.0

    Subgroup discovery is encoded as a QUBO and solved via QAOA on NISQ hardware to find interpretable feature groups that distinguish attack traffic, with results competitive to beam search and better at some multi-featu...

  15. QAOA Parameter Transfer for Hypergraphs

    quant-ph 2026-04 unverdicted novelty 7.0

    Analytical reweighting rules for QAOA parameters on hypergraphs improve performance by adjusting mixing terms beyond previous graph-based methods.

  16. Beyond Single Trajectories: Optimal Control and Jordan-Lie Algebra in Hybrid Quantum Walks for Combinatorial Optimization

    quant-ph 2026-04 unverdicted novelty 7.0

    Hybrid quantum walks with optimal dynamical coin operators outperform QAOA on Max-Cut and MIS by accessing a strictly larger Jordan-Lie algebra that enables faster convergence and higher accuracy.

  17. Graph-Conditioned Meta-Optimizer for QAOA Parameter Generation on Multiple Problem Classes

    quant-ph 2026-04 unverdicted novelty 7.0

    A graph-conditioned meta-optimizer learns QAOA parameter trajectories from one problem class and transfers them to others, yielding better initializations than standard methods in an empirical study of 64 settings.

  18. Optimization Using Locally-Quantum Decoders

    quant-ph 2026-04 unverdicted novelty 7.0

    A quantum decoder for LDPC codes with coherent errors outperforms belief propagation on average-case D-regular max-k-XORSAT for several k and D, matching an enhanced version of Prange's algorithm.

  19. A Spectral Gap Informed Parameter Schedule for QAOA

    quant-ph 2026-04 unverdicted novelty 7.0

    SGIR-QAOA uses spectral gap information to create non-linear parameter schedules that outperform linear ramps on Grover's problem and MIS, achieving target probabilities at lower depths even under mild noise.

  20. Hybrid Path-Sums for Hybrid Quantum Programs

    cs.PL 2026-04 unverdicted novelty 7.0

    Hybrid Path-Sums offer a new symbolic framework with rewriting rules and assertions to represent, simplify, and verify properties of hybrid quantum-classical programs.

  21. Exhaustive and feasible parametrisation with applications to the travelling salesperson problem

    quant-ph 2026-04 unverdicted novelty 7.0

    Exhaustively parametrised feasibility-respecting quantum circuits can reach every feasible solution to problems like TSP with certainty using fixed parameters by leveraging group actions and generating sequences.

  22. Query-Efficient Quantum Approximate Optimization via Graph-Conditioned Trust Regions

    cs.LG 2026-04 unverdicted novelty 7.0

    A GNN predicts Gaussians over QAOA parameters to create graph-conditioned trust regions that reduce circuit evaluations for MaxCut from 85-343 down to 45 while keeping approximation ratios within 3 points of heuristics.

  23. Architecture-aware Unitary Synthesis

    quant-ph 2026-04 unverdicted novelty 7.0

    A new method for unitary synthesis on quantum hardware cuts CNOT gates by up to 36% and compiles up to 553 times faster than standard tools on square and heavy-hex lattices.

  24. Constrained Quantum Optimization meets Model Reduction

    quant-ph 2026-04 unverdicted novelty 7.0

    A projection-based model reduction enables exponential state-space reduction for constrained quantum optimization applied to random 3-SAT and agent coordination on graphs.

  25. Replay-buffer engineering for noise-robust quantum circuit optimization

    quant-ph 2026-04 unverdicted novelty 7.0

    Treating the replay buffer as a central lever in RL for quantum circuit optimization yields 4-32x sample efficiency gains, up to 67.5% faster episodes, and 85-90% fewer steps to accuracy on noisy molecular and compila...

  26. Divide-and-Conquer Neural Network Surrogates for Quantum Sampling: Accelerating Markov Chain Monte Carlo in Large-Scale Constrained Optimization Problems

    quant-ph 2026-04 unverdicted novelty 7.0

    Divide-and-conquer QAOA samples and Hamming-weight-conditioned neural network surrogates accelerate MCMC mixing for constrained Ising problems by average factors of 20.3 and 7.6 over classical pair-flip baselines.

  27. Obstructions to universality in globally controlled qubit graphs

    quant-ph 2026-04 unverdicted novelty 7.0

    The conjecture that breaking all non-trivial graph automorphisms suffices for universality in globally controlled qubit systems is disproved by connected graphs with trivial automorphism groups whose generated Lie alg...

  28. Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly

    quant-ph 2026-04 unverdicted novelty 7.0

    Iterative-QAOA solves pangenome assembly instances on current quantum hardware by using a fixed-ramp QAOA schedule with warm-start updates and a new HUBO encoding that cuts variables from O(N^{2}) to O(N log N).

  29. Characterizing and Benchmarking Dynamic Quantum Circuits

    quant-ph 2026-04 unverdicted novelty 7.0

    Dynamarq is a new scalable benchmarking framework that defines structural features for dynamic quantum circuits and uses statistical models to predict hardware fidelity with transferable parameters.

  30. A Unified Poisson Summation Framework for Generalized Quantum Matrix Transformations

    quant-ph 2026-04 unverdicted novelty 7.0

    A dual Fourier-PSF and contour-PSF framework resolves the smoothness-sparsity trade-off for efficient quantum simulation of singular and holomorphic matrix functions.

  31. RFOX (Rotated-Field Oscillatory eXchange) quantum algorithm: Towards Parameter-Free Quantum Optimizers

    quant-ph 2026-04 unverdicted novelty 7.0

    RFOX keeps the instantaneous spectral gap flat across interpolation and disorder by using a constant XX catalyst plus derived ZX counter-diabatic drive, yielding faster ground-state convergence on small RFIM instances.

  32. Scalable Determination of Penalization Weights for Constrained Optimizations on Approximate Solvers

    quant-ph 2026-04 unverdicted novelty 7.0

    A pre-computation method sets penalization weights for constrained QUBO problems with provable guarantees for Gibbs solvers and polynomial scaling for many problem classes.

  33. CO-MAP: A Reinforcement Learning Approach to the Qubit Allocation Problem

    quant-ph 2026-05 unverdicted novelty 6.0

    Reinforcement learning policy for qubit mapping reduces SWAP overhead by 65-85% versus standard quantum compilers on MQTBench and Queko benchmark circuits.

  34. BoolXLLM: LLM-Assisted Explainability for Boolean Models

    cs.AI 2026-05 unverdicted novelty 6.0

    BoolXLLM augments an existing Boolean rule learner with LLMs for feature selection, discretization thresholds, and natural-language rule translation to improve interpretability while preserving accuracy.

  35. Runtime Calibration as State-Trajectory Feedback Control in Quantum-Classical Workflows

    quant-ph 2026-05 unverdicted novelty 6.0

    Feedback calibration policies outperform open-loop baselines in low-latency quantum runtime regimes when workloads are quality-sensitive and start with aged calibrations.

  36. Quantum Hypergraph Partitioning

    quant-ph 2026-05 unverdicted novelty 6.0

    QAOA produces distributional solutions for hypergraph partitioning that outperform classical SDP approximations on fairness-style objectives like greatest expected imbalance.

  37. SCALAR: A Neurosymbolic Framework for Automated Conjecture and Reasoning in Quantum Circuit Analysis

    quant-ph 2026-05 unverdicted novelty 6.0

    SCALAR generates conjectures linking optimal QAOA parameters to graph invariants, recovers known periodicity and parameter-transfer properties, and identifies correlations with optimization landscapes across thousands...

  38. Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

    quant-ph 2026-05 unverdicted novelty 6.0

    Qudit encodings for EV trip assignments cut the Hilbert space dimension exponentially and match or exceed qubit-based QAOA performance on constrained uni- and bi-directional charging problems.

  39. Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization

    quant-ph 2026-05 unverdicted novelty 6.0

    Position graph abstraction with memoized SABRE heuristics scales qubit mapping and routing for TI-QCCD architectures by caching repeated evaluations without altering decisions.

  40. Don't Get Your Kroneckers in a Twist: Gaussian Processes on High-Dimensional Incomplete Grids

    cs.LG 2026-05 unverdicted novelty 6.0

    CUTS-GPR performs numerically exact Gaussian process regression with near-linear scaling in training points N and low-order polynomial scaling in dimensions D by exploiting additive kernels on incomplete grids.

  41. Constrained Counterdiabatic Quantum Approximate Optimization Algorithm for Portfolio Optimization

    quant-ph 2026-05 unverdicted novelty 6.0

    CCD-QAOA incorporates counterdiabatic terms into the QAOA ansatz and shows higher approximation ratios than standard XY-mixer, Grover-mixer, and penalty QAOA for portfolio problems with budget and risk constraints.

  42. Why Global LLM Leaderboards Are Misleading: Small Portfolios for Heterogeneous Supervised ML

    cs.LG 2026-05 conditional novelty 6.0

    Global Bradley-Terry rankings of LLMs are misleading due to structured heterogeneity in user preferences, and small (λ, ν)-portfolios recover coherent subpopulations that cover over 96% of votes with just five rankings.

  43. Quantum Optimization for Electromagnetics: Physics-Informed QAOA for Reconfigurable Intelligent Surfaces

    cs.CE 2026-05 unverdicted novelty 6.0

    Sparse distance-penalized Ising models are required for feasible QAOA execution on NISQ devices when optimizing RIS with mutual coupling, at the cost of reduced beamforming precision compared to dense models.

  44. Dynamic Quantum-Assisted Co-Design of Control Tuning and Lyapunov Stability Synthesis for Nonlinear Systems

    eess.SY 2026-05 unverdicted novelty 6.0

    A quantum-assisted co-design method jointly optimizes controller gains and Lyapunov stability parameters online for nonlinear systems by contracting the search space, building an Ising Hamiltonian via quadratic surrog...

  45. Dynamic Quantum-Assisted Co-Design of Control Tuning and Lyapunov Stability Synthesis for Nonlinear Systems

    eess.SY 2026-05 unverdicted novelty 6.0

    A two-step quantum-assisted method contracts the parameter search region via Black-Hole calibration, builds a quadratic pseudo-Boolean surrogate for an Ising Hamiltonian, and solves it with imaginary time evolution to...

  46. Quantum Resource Estimation for Minimising Energy Grid Losses

    quant-ph 2026-05 unverdicted novelty 6.0

    The paper maps distribution network reconfiguration for loss minimization to a HUBO problem without auxiliary variables and estimates quantum resources for a real Dutch MV network.

  47. Quantum Tilted Loss in Variational Optimization: Theory and Applications

    quant-ph 2026-05 unverdicted novelty 6.0

    QTL unifies expectation-value minimization with CVaR and Gibbs heuristics under one tunable operator, amplifying gradients in structured cases while preserving global minima and shifting the bottleneck to measurement ...

  48. Quantum Hypergraph Partitioning

    cs.SI 2026-05 unverdicted novelty 6.0

    Balanced k-way hypergraph partitioning is cast as QUBO and higher-order binary problems for quantum optimization, with small-instance tests confirming effectiveness for the all-or-nothing cut on 3-uniform hypergraphs.

  49. Accelerating Noisy Variational Quantum Algorithms with Physics-Informed Denoising Networks

    quant-ph 2026-05 unverdicted novelty 6.0

    PIDN replaces repeated multi-noise ZNE evaluations with a trained network that denoises expectation values and gradients from noisy data plus history, achieving comparable optimization on quantum models with 4-6x fewe...

  50. Structured Parameterization and Non-Stabilizerness in Hypergraph QAOA

    quant-ph 2026-05 unverdicted novelty 6.0

    kA-QAOA matches MA-QAOA approximation ratios on 3-uniform hypergraphs while using significantly fewer function evaluations.

  51. A Quantum Approach to Stochastic Optimization in Insurance Underwriting

    quant-ph 2026-05 unverdicted novelty 6.0

    A hybrid quantum-classical method with knapsack-specific QAOA circuits and classical recovery produces solutions indicating improvement over classical schemes for chance-constrained knapsack problems in insurance on I...

  52. Finite Imaginary-Time Evolution for Polynomial Unconstrained Binary Optimization

    quant-ph 2026-04 unverdicted novelty 6.0

    FinITE gives an exact identity linking LCU success probability to ground-subspace fidelity for diagonal Pauli-Z Hamiltonians, yielding a closed-form imaginary-time threshold beta-star based on spectral gap and initial...

  53. Protein folding on a 64 qubit trapped-ion hardware via counterdiabatic quantum optimization

    quant-ph 2026-04 unverdicted novelty 6.0

    A 64-qubit trapped-ion system using BF-DCQO optimizes lattice protein folding Hamiltonians for six peptides, reaching classical reference energies in multiple cases after hybrid post-processing.

  54. Efficient mapping of multi-constraint satisfaction problems to Rydberg platforms

    quant-ph 2026-04 unverdicted novelty 6.0

    A compact xor_1 gadget enforces exactly-one constraints on Rydberg arrays via fixed-detuning blockade, cutting detuning range by up to 99% and atom/connectivity overhead by up to 54% versus QUBO for gate assignment an...

  55. Solving a Linear System of Equations on a Quantum Computer by Measurement

    quant-ph 2026-04 unverdicted novelty 6.0

    A new quantum algorithm solves linear equations by measuring and optimizing the fidelity of a phase-estimation-prepared state, handling dense matrices with 1/N accuracy scaling.

  56. Iterative warm-start optimization with quantum imaginary time evolution

    quant-ph 2026-04 unverdicted novelty 6.0

    An iterative nonvariational quantum algorithm using warm-start states and classically computed imaginary time evolution circuits achieves median solutions within 95% of optimal for MaxCut on small 3-regular graphs usi...

  57. Quantum Optimization Methods for the Generalized Traveling Salesman Problem

    quant-ph 2026-04 unverdicted novelty 6.0

    Quantum optimization for GTSP yields competitive solutions on small instances but shows higher runtimes and sharp drops in feasibility and scalability on larger graphs compared to classical solvers.

  58. A SWAP-free Framework for QAOA

    quant-ph 2026-04 unverdicted novelty 6.0

    A MISDP formulation approximates QAOA cost matrices for native hardware embedding without SWAPs, backed by NP-completeness proof and Lovasz-number bounds, yielding competitive performance on cardinality-constrained qu...

  59. Qubit-Scalable CVRP via Lagrangian Knapsack Decomposition and Noise-Aware Quantum Execution

    quant-ph 2026-04 unverdicted novelty 6.0

    A hybrid quantum framework decomposes CVRP into bounded-width knapsack subproblems, trains a reinforcement learning controller for Lagrangian multipliers, and uses a contextual bandit to adapt quantum hardware executi...

  60. A Complex-Valued Continuous-Variable Quantum Approximation Optimization Algorithm (CCV-QAOA)

    quant-ph 2026-04 unverdicted novelty 6.0

    CCV-QAOA is a new complex-valued continuous-variable variant of QAOA that solves real and complex multivariate optimization problems via a variational framework.

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages · cited by 116 Pith papers

  1. [1]

    MAX CUT in cubic graphs, 2004

    Eran Halperin, Dror Livnat, Uri Zwick. MAX CUT in cubic graphs, 2004. Journal of Algorithms, Volume 53 Issue 2, Pages 169-185

    work page 2004

  2. [2]

    Quantum Computation by Adiabatic Evolution

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sip ser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106

    work page Pith review arXiv 2000

  3. [3]

    arXiv preprint quant-ph/0201031 , year=

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann. Quantum Adiabatic Evolution Algorithms versus Simulated A nnealing, 2002. arXiv:quant-ph/0201031

    work page arXiv 2002

  4. [4]

    Different strategies for optimization with the quantum adiab atic algorithm, 2014

    Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin, Han -Hsuan Lin, Peter Shor. Different strategies for optimization with the quantum adiab atic algorithm, 2014. arXiv:1401.7320 [quant-ph]

    work page arXiv 2014

  5. [5]

    Quantum Computation and Decision Trees, 1997

    Edward Farhi, Sam Gutmann. Quantum Computation and Decision Trees, 1997. Phys. Rev. A 58, 915 arXiv:quant-ph/9706062. 16

    work page arXiv 1997