pith. sign in

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

A Quantum Approximate Optimization Algorithm

Edward Farhi , Jeffrey Goldstone , Sam Gutmann This is my paper

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.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

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. Reductions of QAOA Induced by Classical Symmetries: Theoretical Insights and Practical Implications

    quant-ph 2026-02 conditional novelty 8.0

    Symmetry reductions in QAOA for MaxCut can collapse DLA dimensions from exponential to quadratic depending on the fixed variable, with graph embeddings ensuring expressivity and improved trainability.

  4. Constraint-Aware Quantum Optimization via Hamming Weight Operators

    quant-ph 2026-01 unverdicted novelty 8.0

    Hamming Weight Operators and an adaptive QAOA variant confine evolution to feasible states by construction, delivering faster convergence and roughly half the gate count versus penalty methods on finance and physics tasks.

  5. Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement

    quant-ph 2025-11 conditional novelty 8.0

    Standard QAOA faces an intrinsic feasibility bottleneck on permutation problems that CE QAOA overcomes with an exponential gain in feasible probability for sublinear-to-linear depths under mild hypergraph growth.

  6. A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

    cs.CC 2025-11 unverdicted novelty 8.0

    A hybrid lifting theorem unifies classical query-to-communication and quantum approximate-degree lifting to prove c + q² = Ω(max{deg(f), bs(f)} log n) for protocols computing f ∘ G^n.

  7. Quantum Glassiness From Efficient Learning

    quant-ph 2025-04 unverdicted novelty 8.0

    Efficient learning algorithms for energy estimation imply that stable quantum algorithms cannot prepare low-energy states in systems exhibiting the quantum overlap gap property, as proven for a sparsified quantum p-sp...

  8. SAFE ma-QAOA: Surrogate-Assisted and Fine-Tuning Enhanced Multi-Angle QAOA with Parameter Distillation

    quant-ph 2026-05 unverdicted novelty 7.0

    SAFE ma-QAOA achieves 64.3% fewer active parameters and 94.5% lower estimated QPU workload via surrogate pre-training and parameter distillation on Sherrington-Kirkpatrick, 2D spin glass, and Max-Cut instances.

  9. Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning

    quant-ph 2026-05 unverdicted novelty 7.0

    CRiSP uses neural-guided MCTS and curriculum learning to insert Clifford prefixes before parameterized rotations in VQAs, yielding mean 3.17x and max 45x gains in energy accuracy on 22-qubit QAOA benchmarks versus pri...

  10. Truncated-Binary Encoding: Spectral Degree Reduction of Combinatorial Optimization Problems for Quantum Hardware

    quant-ph 2026-05 unverdicted novelty 7.0

    Truncated-binary encoding approximates high-cardinality CFN problems as low-degree HUBO Hamiltonians with an L^∞ error bound, conditions preserving the global minimum, and a smoothness-based criterion for choosing the cutoff.

  11. Mutually Unbiased Bases for Variational Quantum Initialization: Basis-Union Optimality and Adaptive Family Search

    quant-ph 2026-05 unverdicted novelty 7.0

    Complete MUB ensembles are optimal for isotropic Gaussian random-Hamiltonian width among d+1 basis unions, enabling adaptive MUB-XRot QAOA that is non-worse than standard QAOA in 80% of 1500 benchmark cases.

  12. Bias Analysis and Regularization of Sequential Minimal Optimization in Variational Quantum Eigensolvers

    quant-ph 2026-05 unverdicted novelty 7.0

    Bias in SMO-VQE can be estimated without extra measurements; a regularization method that mimics error accumulation while preserving unbiased estimates improves performance across system sizes and Hamiltonians.

  13. QUACOD: Quantum Optimization via Coordinate Descent for Scalable Drone Scheduling

    quant-ph 2026-05 unverdicted novelty 7.0

    QUACOD decomposes drone scheduling into quantum-solvable subproblems via coordinate descent, outperforming prior quantum methods in completion time while scaling to 5x more drones and 35x more routes.

  14. 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.

  15. 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.

  16. 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.

  17. Multivariate Decoded Quantum Interferometry for Weighted Optimization

    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...

  18. Multivariate Decoded Quantum Interferometry for Weighted Optimization

    quant-ph 2026-05 unverdicted novelty 7.0

    Multivariate DQI uses N-variable polynomials for weighted Max-LINSAT, derives closed-form asymptotics for expectation and concentration, provides a single-decoder preparation circuit, and shows outperformance over wei...

  19. 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.

  20. 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...

  21. 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.

  22. 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.

  23. 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.

  24. 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...

  25. 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.

  26. 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...

  27. 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.

  28. 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.

  29. 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.

  30. 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.

  31. 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.

  32. 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.

  33. 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.

  34. 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.

  35. 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.

  36. 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.

  37. 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...

  38. 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.

  39. 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...

  40. 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).

  41. 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.

  42. 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.

  43. 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.

  44. 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.

  45. Finite-Depth, Finite-Shot Guarantees for Constrained Quantum Optimization via Fej\'er Filtering

    quant-ph 2026-03 unverdicted novelty 7.0

    CE-QAOA with finite layers achieves dimension-free success probability bounds q0 ≥ x/(1+x) via Fejér filtering under a wrapped phase-separation condition.

  46. Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut

    quant-ph 2026-02 unverdicted novelty 7.0

    QAOA on qudit-encoded integer graph problems outperforms the Frieze-Jerrum SDP for Max-k-Cut at p≤4 in regimes k=3 d≤10 and k=4 d≤40, while a new degree-of-saturation heuristic beats both on GSet but may be overtaken ...

  47. Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing

    quant-ph 2025-11 unverdicted novelty 7.0

    Closed-form tight penalty coefficients for two QUBO reformulations of max-k-cut that depend on the weighted degrees of graph vertices.

  48. Requirements for Early Quantum Utility and Quantum Utility in the Capacitated Vehicle Routing Problem

    quant-ph 2025-09 unverdicted novelty 7.0

    A resource-estimation framework places CVRP instances on a go/no-go decision diagram and shows that a higher-order encoding needs far fewer qubits than standard QUBO for early-advantage benchmarks such as Golden-5.

  49. Classical Neural Networks on Quantum Devices via Tensor Network Disentanglers: A Case Study in Image Classification

    quant-ph 2025-09 unverdicted novelty 7.0

    A hybrid classical-quantum scheme compresses and disentangles bottleneck layers of pre-trained neural networks into MPO form for execution on quantum devices, validated via proof-of-concept on MNIST and CIFAR-10 image...

  50. From Membership-Privacy Leakage to Quantum Machine Unlearning

    quant-ph 2025-09 unverdicted novelty 7.0

    Quantum neural networks exhibit membership privacy leakage that a proposed quantum machine unlearning framework with three mechanisms can mitigate in simulations and cloud device tests.

  51. Partitioned-Constraint QAOA (PC-QAOA): Structural State Preparation and Penalty Enforcement for Quantum Optimization

    quant-ph 2025-08 unverdicted novelty 7.0

    PC-QAOA partitions constraints into structural enforcement via feasible-state preparation and Grover mixers plus energetic penalties, reporting improved feasibility and quality over penalty-only QAOA across 413 instances.

  52. Inference of maximum parsimony phylogenetic trees with model-based classical and quantum methods

    quant-ph 2025-08 unverdicted novelty 7.0

    Introduces branch-based and other optimization models for maximum parsimony trees, with classical validation outperforming heuristics on GAPDH data and quantum simulations solving small instances exactly.

  53. The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization

    quant-ph 2025-05 unverdicted novelty 7.0

    The paper decomposes dynamical Lie algebras of XY-mixer topologies and demonstrates warm-starting QAOA via pre-training on restricted generators to improve convergence on constrained optimization problems.

  54. Iceberg Beyond the Tip: Co-Compilation of a Quantum Error Detection Code and a Quantum Algorithm

    quant-ph 2025-04 unverdicted novelty 7.0

    Co-optimization of flexible Iceberg error-detection gadgets with QAOA via tree search improves success probability and post-selection on Quantinuum H2-1 hardware up to 34 algorithmic qubits.

  55. Efficient measurement of neutral-atom qubits with matched filters

    quant-ph 2025-04 conditional novelty 7.0

    Two matched-filter algorithms for neutral-atom qubit readout reduce measurement errors by 32-43% versus Gaussian thresholds and use 100x fewer parameters than CNNs while remaining scalable.

  56. Counting with the quantum alternating operator ansatz

    quant-ph 2025-03 unverdicted novelty 7.0

    VQCount applies QAOA as a solution sampler to achieve approximate counting with an exponentially reduced number of samples, demonstrated via proof and tensor-network simulations on two #P-hard problems.

  57. Efficient Compilation for Shuttling Trapped-Ion Machines via the Position Graph Architectural Abstraction

    quant-ph 2025-01 unverdicted novelty 7.0

    Position graph abstraction plus SHAPER/SHAW heuristics enable shuttling-aware compilation on trapped-ion machines, succeeding on extreme cases where baselines fail and yielding 1.45x average (up to 4x) speedups.

  58. Magic states are rarely the best resource to optimize: An analytical tool for qubit resource estimation in concatenated codes

    quant-ph 2024-11 conditional novelty 7.0

    A closed-form resource estimation tool for concatenated quantum error correction reveals that magic-state operations rarely dominate qubit costs, with general optimizations providing orders-of-magnitude larger reducti...

  59. High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization

    quant-ph 2024-08 conditional novelty 7.0

    Search-based approximate diagonalization followed by analytical inversion yields high-precision multi-qubit Clifford+T circuits with 95% fewer non-Clifford gates on real-algorithm benchmarks.

  60. Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives

    quant-ph 2024-08 unverdicted novelty 7.0

    Product-State Lifting (PSL) upgrades any basis-state vQSDP to k-degree polynomial optimization via product-register encoding, with linear resource scaling and k-independent constraints.

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages · cited by 213 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 Using the Quantum Adiabatic Algorithm

    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 Pith review 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