Pith. sign in

REVIEW 3 major objections 5 minor 50 references

Polynomial Time Quantum Approximation Schemes for Constrained Optimisation

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims that a constrained-QAOA sampler followed by deterministic feasibility repair and exact scoring becomes an exact-hit FPRASq in polynomial time whenever its ideal output puts inverse-polynomial probability on the optimal set.

desk verdict A readable, honest conditional framework for quantum optimization whose central inverse-polynomial optimal-mass premise is never instanced, and whose own dephased envelope analysis actually fails for the flagship assignment/TSP kernel. read the letter →

arxiv 2608.01121 v3 pith:CQ547HIA submitted 2026-08-02 quant-ph cs.CCcs.DMmath-phmath.MPphysics.app-ph

Chinonso Onah , Kristel Michielsen This is my paper · ORCID
classification quant-phcs.CCcs.DMmath-phmath.MPphysics.app-ph MSC 68Q1268Q1768W2090C27 PACS 03.67.Ac
keywords quantumapproximationschemeconstrainedoptimizationQAOAFPRASfeasibilityrepairheavy-hitterfilteringNISQquantum-classicalseparation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper sets out to close the loop between a quantum sampler and a classical optimizer: rather than treating QAOA as a heuristic whose raw outputs are used directly, it wraps the CE-QAOA sampling distribution in a deterministic checker, repair map, and scorer, and analyzes the pipeline's end-to-end runtime and success probability. The central claim is that if the ideal CE-QAOA circuit assigns at least $c n^{-k}$ probability to the globally optimal set, then the full pipeline is an exact-hit fully polynomial randomized approximation scheme (FPRASq): with $O(n^{k+1}\log(1/\delta))$ shots under noise it returns a global optimum with probability at least $1-\delta$, in polynomial total runtime. The paper also claims a conditional separation: no polynomial-time classical sampler equipped with the same repair and scoring can reproduce that inverse-polynomial optimal overlap on an NP-hard kernel-admissible promise family unless NP is contained in BPP. The result pinpoints the sampling distribution, not the classical post-processing, as the locus of any quantum advantage, and it gives near-term hardware experiments a concrete performance target.

What carries the argument

The load-bearing mechanism is the inverse-polynomial optimal-mass premise $q_0 \ge c n^{-k}$, obtained from the factorized reference distribution $\Pr_p^{\mathrm{ref}}[z] \propto W_p(z;\beta)\, F_p(\theta(z)-\theta^\star)$, where $W_p$ is the mixer-envelope distribution induced by the block-local XY mixer and $F_p$ is the Fejér phase filter of order $p$ peaking at the optimal wrapped phase $\theta^\star$. This identity converts a circuit-success question into a geometric one: whether the optimal-set envelope weight $C_\beta$ and the wrapped phase gap $\delta$ satisfy $C_\beta \ge c_0 n^{-a}$ and $\sin^2(\delta/2) \ge c_1$, which yields $q_0 = \Omega(n^{-a})$ dimension-free. The rest of the pipeline, deterministic feasibility repair by nearest-permutation projection (solved by the Hungarian algorithm) and exact scoring, preserves or increases the mass on the optimal set and turns the bound into a Chernoff-amplified shot count.

What would settle it

Compute the ideal (noiseless) CE-QAOA output distribution for a sequence of TSP or QAP instances with $n=10,20,40,80$; if the optimal-set probability $q_0$ decays faster than every inverse polynomial, or the envelope weight $C_\beta$ drops below $c_0 n^{-a}$ with growing $a$, the exact-hit FPRASq premise fails on those instances.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that constrained quantum optimization can be made a provable polynomial-time randomized approximation scheme by composing three ingredients: the CE-QAOA kernel (a one-hot encoded subspace evolved by a block-local XY mixer and a diagonal cost Hamiltonian), a factorized reference model in which the mixer envelope and a Fejér phase filter control the output distribution, and a classical repair stage that projects any measured bit-matrix to the nearest permutation in Hamming distance. Given the inverse-polynomial optimal-mass premise $q_0 = \Omega(n^{-k})$, Theorem 17 shows the output is exactly optimal with probability at least $1-\delta$ after $O(n^k \log(1/\delta))$ shots; under a total-variation noise bound the shot budget becomes $O(p n^{k+1} \log(1/\delta))$ while retaining inverse-polynomial optimal mass. Outside that window, deterministic repair still guarantees feasibility and an instance-dependent $(1+\varepsilon)$ approximation whenever the repair inflation is controlled. The separation theorem is conditional: if any polynomial-time classical sampler achieved inverse-polynomial optimal overlap uniformly on an NP-hard kernel-admissible promise family, standard amplification would put the promise search problem in BPP.

Load-bearing premise

The load-bearing premise is that the ideal circuit's probability on the optimal set is at least an inverse polynomial in $n$, a condition the paper derives from further untested conditions on the mixer envelope weight and the wrapped phase gap but does not certify for any concrete NP-hard family.

Editorial extensions

If this is right

  • Under the inverse-polynomial optimal-mass premise, the NP-HQ pipeline is an exact-hit FPRASq: it returns a global optimum with probability at least $1-\delta$ in $O(n^k \log(1/\delta))$ shots, with no dependence on $\varepsilon$.
  • Within the noise window of Theorem 5, retaining a $1/G(n,p)$ fraction of the ideal optimal mass keeps the guarantee, at the price of one extra power of $n$ in the shot budget, $O(p n^{k+1} \log(1/\delta))$.
  • Heavy-Hitter QAOA cuts the retained candidate set and classical post-processing by one power of $n$ (from $O(n^{k+1})$ to $O(n^k)$) without weakening the exact-hit guarantee.
  • The separation theorem locates any quantum advantage in the sampling distribution itself, because a classical sampler granted the same repair and perfect constraint-structure access would imply NP$\subseteq$BPP if it matched the inverse-polynomial overlap.
  • On IBM Eagle r3 hardware, the repair pipeline matches or improves the published QOptlib reference tours on all tested instances with up to 100 logical variables.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the theorem's premise is the practical crux; a reader should treat the FPRASq guarantee as conditional until some concrete kernel-admissible problem family is shown to satisfy the envelope-weight and phase-gap bounds.
  • Editorial inference: the checker-repair-scorer template transfers beyond TSP to any constraint class with a polynomial-time feasibility oracle and a bounded repair map, so the same three-part pipeline could be instantiated for scheduling, packing, or matching problems.
  • Editorial inference: the quantum-informed heavy-hitter threshold provides a device-calibration diagnostic, because the threshold's validity window is exactly the regime where the noisy output distribution stays within total-variation distance of the ideal one.
  • Editorial inference: a natural testable extension is to measure the empirical optimal-mass exponent $k$ on larger instances and check whether it stays bounded; a growing exponent would falsify the premise for those instances.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper develops a hybrid quantum–classical optimization pipeline (NP-HQ) built on the CE–QAOA/OFM kernel. Its main theoretical claim is that if the ideal CE–QAOA distribution assigns inverse-polynomial probability mass q0 ≥ c n^{-k} to the optimal feasible set, then independent-shot amplification, polynomial-time feasibility repair, and exact scoring yield an exact-hit FPRASq; the claim is extended to a noise-robust form via a total-variation Lipschitz bound, to a complexity-theoretic separation against classical samplers, and to a Heavy-Hitter QAOA refinement that reduces classical post-processing cost. The paper also reports hardware experiments on IBM Eagle r3 processors for QOptlib TSP instances with up to 100 logical variables, claiming to match or improve the reference tours. The theoretical derivations are conditional on the inverse-polynomial optimal-mass premise, which the paper sources to self-cited references and to an appendix (Appendix A.5) that requires additional envelope and phase-gap conditions.

Significance. If the inverse-polynomial optimal-mass premise were established for a concrete NP-hard family, the paper's FPRASq theorem, noise-to-shot-complexity translation, and repair-based post-processing framework would constitute a useful template for end-to-end quantum optimization. The conditional proofs are mostly elementary and correct: the Chernoff amplification argument in Theorem 17, the total-variation noise bound in Appendix A.6, and the repair lemmas in Section 3.1 are all cleanly presented. The heavy-hitter analysis is also logically sound. However, the paper does not provide any concrete instance where the central premise q0 ≥ c n^{-k} is verified. The only derivation offered (Corollary 37) requires Cβ ≥ c0 n^{-a} and sin²(δ/2) ≥ c1, and for the flagship assignment/TSP specialization, the dephased envelope weight is exactly uniform, giving Cβ = |Ω*|/n^n ≤ n!/n^n = exp(-Θ(n)), so the premise cannot be instantiated in that model. The hardware section lacks error bars, shot counts in the comparison tables, and any classical baseline. The paper's value is therefore as a rigorous conditional framework, not as an established polynomial-time quantum approximation scheme.

major comments (3)
  1. [§2.3, Eq. (10); Appendix A.5 (Corollary 37)] The central premise q0 ≥ c n^{-k}, on which Theorems 5, 17, and 30 all rest, is not instantiated for any concrete NP-hard family. Appendix A.5 derives it from the two further conditions Cβ ≥ c0 n^{-a} and sin²(δ/2) ≥ c1, but for the assignment/TSP specialization of Definition 1 with m = nloc = n, the initial diagonal v(0)(z) = |⟨z|s0⟩|² = n^{-n} is uniform, and each mixer transition matrix Mβ is doubly stochastic (Lemma 34). Hence Wp(z;β) = n^{-n} for every z and every β, giving Cβ = Σ_{x∈Ω*} Wp(x;β) = |Ω*|/n^n ≤ n!/n^n = exp(-Θ(n)). Thus Cβ ≥ c0 n^{-a} fails for every fixed a at sufficiently large n, so Corollary 37 cannot supply the inverse-polynomial premise on the paper's flagship kernel. The paper explicitly disclaims a pointwise ordering between coherent and dephased probabilities (§2.3), so the premise remains an unsupported assumption. The authors should either prove q0 ≥ c n^{-k} for a concrete kernel-admissible family (coherently, not only via the dephased reference law), or explicitly state that all main results are conditional on an assumption that is not established in this paper.
  2. [§3.4, Theorems 21 and 22] The claimed quantum–classical separation is not a demonstrated separation. Theorem 21 shows that if a classical sampler achieved inverse-polynomial optimal overlap, standard repetition would place the promise search problem in BPP, implying NP ⊆ BPP; this is a valid conditional statement, but it does not establish that NP-HQ actually has such overlap, since that is precisely the unproven q0 premise. Theorem 22 is titled 'Perfect structural oracles do not yield inverse-polynomial optimal overlap,' but its proof merely assumes that some algorithm with oracle (A)–(C) achieves such overlap and derives a BPP containment; no lower bound against the oracles is proved. The separation is therefore entirely contingent on the uninstantiated premise, and the wording overstates what has been shown.
  3. [§4, Tables 3 and 5] The hardware demonstration, which the abstract summarizes as matching or improving every tested QOptlib reference tour, is not statistically supported. Tables 3 and 5 report a single best repaired cost per instance with no error bars, no number of shots used in the comparison, no repetition statistics, and no classical baseline such as random sampling plus Hungarian repair or a standard TSP heuristic. Without these, the reported improvements (e.g., 12.5% on dj9) cannot be distinguished from noise or from the repair routine's deterministic output. The empirical section should report shot counts, multiple runs or confidence intervals, and a classical comparison before the 'match or improve' claim is made.
minor comments (5)
  1. [§4.1] The text refers to 'the prolem Hamiltonian' (typo for 'problem Hamiltonian') near the beginning of Section 4; please correct.
  2. [§4.2 and Reference [49]] The implementation section states Qiskit 1.1.2, but Reference [49] cites Qiskit version 0.47; please reconcile the version and the reference.
  3. [Throughout] The benchmark name is spelled inconsistently as 'QOptlib' and 'QOPTLib'; please standardize to the official name used in Reference [3].
  4. [§3.2, Lemma 16] Lemma 16 (column-swap repair with C(~x) ≤ C(x) + 3n w_max) is stated without proof or a precise pointer to the argument in Reference [46]; since Proposition 19 relies on this bound, a proof or a more specific reference should be provided.
  5. [§5.4, Tables 6 and 7] The gap columns in Tables 6 and 7 report percentage deviations from exhaustive analysis of the raw histogram, but the table captions do not clarify this; please make the baseline explicit and consider whether the top-L compression gaps (e.g., 0.19% in Table 6) are within the noise of the hardware runs.

Circularity Check

2 steps flagged · score 6.0 of 10

Central FPRASq and separation claims reduce to an assumed inverse-polynomial optimal mass: the promise family is defined to admit that bound, Appendix A.5 only restates it under uninstanced envelope/phase conditions, and the flagship TSP/assignment dephased envelope makes Cβ exponentially small.

  1. self definitional [Section 2 (scope statement) and Section 3.5 (Connection to NP-HQ)]
    "The subsequent complexity results apply to problem families admitting this interface together with the stated instance-dependent lower bound on optimal sampling mass. ... In contrast, on the kernel-admissible family Kn the CE layer biases amplitude so that the optimaltour receives inverse–polynomial mass (with suitable instance-dependent angles)"

    The promise family on which the main results are claimed is defined to already admit "the stated instance-dependent lower bound on optimal sampling mass", i.e. inverse-polynomial optimal overlap. The paper then asserts that NP-HQ achieves inverse-polynomial optimal-hit probability on this family. The quantum advantage is thus placed into the definition of the promise class rather than derived for any concrete instance. Since no NP-hard instance family is exhibited that satisfies the bound, and the appendix's sufficient conditions fail for the canonical assignment/TSP specialization, the central claim is true by construction of the promise class rather than by an independent derivation.

  2. self citation load bearing [Section 2.3, Eq. (10); Appendix A.5, Corollary 37; Refs [1,24]]
    "The analysis of Ref. [1] provides conditions under which the ideal CE–QAOA sampler can assign inverse-polynomial probability p0 = Ω(n−k) to the set of optimal solutions. ... Suppose that ... Cβ≥c0 n−a, sin2(δ/2)≥c1 ... Then ... q0≥ ... = Ω(n−a). Setting k:=a, this supplies the inverse-polynomial premise q0 = Ω(n−k) used in Theorem 5 and the FPRASq analysis."

    Every downstream guarantee (Theorems 5, 17, 21, 30) is conditioned on the inverse-polynomial optimal mass. That premise is sourced from Refs [1,24], both authored by the present authors, and Appendix A.5 re-derives it only by assuming Cβ≥c0 n−a and sin2(δ/2)≥c1. For the canonical assignment/TSP kernel of Definition 1, v(0)(z)=n−n and each Mβ is doubly stochastic, so Wp(z;β)=n−n and Cβ=|Ω*|/n^n ≤ n!/n^n = exp(−Θ(n)); hence the assumed polynomial envelope condition cannot hold for fixed a on the flagship kernel. The central premise is therefore an unverified, load-bearing self-citation rather than an independently established result.

full rationale

The conditional theorems in Sections 2.5 and 3 are internally valid: if the ideal CE–QAOA output assigns inverse-polynomial mass to the optimum, Chernoff amplification gives a polynomial-shot exact-hit FPRASq, and a matching classical sampler would put the promise search problem in BPP. That part is not circular. The circularity lies in the grounding of the premise. The paper defines its kernel-admissible promise family to already admit the instance-dependent inverse-polynomial optimal-mass lower bound, then asserts that NP-HQ achieves that bound on the family; the only formal derivation (Appendix A.5, Corollary 37) assumes Cβ≥c0n−a and sin2(δ/2)≥c1 and concludes q0=Ω(n−a) with the same exponent. These assumptions are sourced from same-author preprints [1,24] and are never instantiated. Moreover, the paper's own dephased analysis for the assignment/TSP specialization yields an exactly uniform mixer envelope, making Cβ=|Ω*|/n^n exponentially small; the paper explicitly declines to assume a pointwise coherent-versus-dephased ordering. Thus no concrete NP-hard instance family is demonstrated to satisfy the central premise, and the headline FPRASq and quantum–classical separation claims reduce to that assumed premise. The noise-to-runtime translation, Hungarian repair, and heavy-hitter post-processing analyses have independent content, so the circularity is partial rather than total.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The central claim rests on an unproven inverse-polynomial optimal-mass premise, which is itself derived from additional untested envelope and phase-gap conditions. The theoretical pipeline otherwise uses standard probability, matching, and quantum-information tools. The hardware demonstration introduces warm-start angles and heavy-hitter thresholds that are set by hand.

free parameters (5)
  • k = unspecified constant k≥0
    Exponent in the assumed optimal-mass bound q0 ≥ c n^{-k}; controls all shot-complexity exponents, but no instance is shown to realize a particular k.
  • c = unspecified constant c>0
    Multiplicative constant in the optimal-mass assumption; value never computed or bounded.
  • Cβ envelope constants c0, a = unspecified
    Used in Corollary 37 to turn mixer-envelope assumptions into q0 = Ω(n^{-a}); no numerical values or instance verification are given.
  • Hardware warm-start angles (γgen, βgen) = listed in Table 1 for wi4-dj10
    Obtained from generic-QAOA optimization and reused for CE-QAOA hardware runs; they affect the empirical tour costs but are not part of the theoretical guarantee.
  • Heavy-hitter exponent k and top-L window = k=3 or 4, L=25k
    Chosen by hand in the empirical heavy-hitter tables (Tables 6-9); not fitted by a stated rule.
assumptions (6)
  • standard math Chernoff/Hoeffding bounds, total-variation triangle inequality, and Hungarian algorithm correctness.
    Used pervasively in Theorems 5, 17, and 26; standard results not proved in the preprint.
  • domain assumption OFM kernel encoding and one-hot structure (Definition 1) hold for the problem family.
    All guarantees are stated only for kernel-admissible instances.
  • domain assumption The factorized reference distribution (Eq. 8) reflects the coherent CE-QAOA output under the phase-alignment conditions of Ref. [24].
    This bridges the dephased reference model to the actual circuit; not proved in this preprint.
  • ad hoc to paper Envelope and phase conditions Cβ ≥ c0 n^{-a} and sin^2(δ/2) ≥ c1 hold uniformly over the family (Corollary 37).
    These are the load-bearing conditions that produce q0 = Ω(n^{-k}); no concrete family is exhibited.
  • domain assumption The noise model is a per-effective-layer channel with diamond distance at most ε, plus independent measurement shots.
    Used in Theorem 5; depends on scheduling assumptions and gate error uniformity.
  • domain assumption The kernel-admissible promise family K_n contains an NP-hard subfamily under polynomial-time reductions.
    Theorem 21's separation requires this; the paper states it conditionally.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Polynomial Time Quantum Approximation Schemes for Constrained Optimisation." pith.science (2026). https://pith.science/paper/CQ547HIA

@misc{pith2026260801121,
  author       = {Pith},
  title        = {Pith review of: Polynomial Time Quantum Approximation Schemes for Constrained Optimisation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CQ547HIA}},
  note         = {Machine review of arXiv:2608.01121}
}
read the original abstract

When does a noisy quantum sampler yield an end-to-end polynomial-time optimization algorithm with performance guarantees? Building on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA, we show that inverse-polynomial ideal probability on the optimal set, together with independent sampling, polynomial-time feasibility repair, and scoring, produces an exact-hit fully polynomial randomized approximation scheme, which we call an FPRASq. This guarantee survives device noise within an instance-dependent window. For effective circuit depth linear in the product of layer count and problem size, preserving an inverse-depth fraction of the ideal optimal mass increases the required shot complexity by one power of the problem size. Beyond this window, deterministic repair guarantees feasibility and provides an instance-dependent approximation guarantee whenever the induced objective inflation is controlled. The resulting NP-HQ algorithm fits the Chen-Cotler-Huang-Li oracle model. On any NP-hard kernel-admissible promise family, reproducing its inverse-polynomial optimal overlap with a polynomial-time classical sampler would imply that NP is contained in BPP, even with identical repair and perfect access to the constraint structure. Thus, the separation lies in generating the sampling distribution. We further introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical post-processing cost by one power of the problem size. Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables and match or improve every tested QOptlib reference tour.

Figures

Figures reproduced from arXiv: 2608.01121 by the authors.

Figure 1
Figure 1. Raw versus post-repair feasible fraction for the QOptlib benchmark instances executed on ibm_brisbane. Hungarian repair maps all samples back into the feasible permutation set. 4.4.1 Comparison with published QOptlib tours [PITH_FULL_IMAGE:figures/full_fig_p021_1.png] view at source ↗
Figure 2
Figure 2. Raw versus post-repair feasible fraction for ibm_sherbrooke. As on ibm_brisbane, raw feasibility is very small and deterministic repair restores all outputs to feasibility [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗
Figure 3
Figure 3. Depth-compression effect. Trading a tiny compiler error δ for a large gate-count reduction G < G ˜ reduces total TV error, lets you raise τ , and shrinks the heavy-hitter set. The associated circuit compression is discussed in App. A.8 Markov (classical) |Hτ | ≤ 1/τ = n k+1 Block factorisation |Hτ | = O(n k ) Top-L compression |Hτ | = O(1) post-proc O(n k+4) post-proc O(n k+3) post-proc O(n 3 ) [PITH_FULL_IMAGE:fig… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Shrinking the scan set. Structure in CE–QAOA collapses the heavy-hitter list from n k+1 to O(1), cutting classical time from O(n k+4) to O(n 3 ). 24 [PITH_FULL_IMAGE:figures/full_fig_p024_4.png]
Figure 5
Figure 5. Figure 5: Empirical CPU runtimes for the three post-processing stages. The classical heavy-hitter stage has the largest footprint, the block-prefiltering stage is substantially cheaper, and the optional top-L compression is cheapest of all. The empirical results illustrate that …
Figure 6
Figure 6. Figure 6: Maximum heavy-hitter threshold θmax(α, δ) as a function of the depth fac￾tor α and approximation error δ. At fixed δ, depth compression increases θmax linearly; at fixed α, increasing δ decreases it one-to-one. The bottom-left region shows that aggres￾sive depth reduct…

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 9 linked inside Pith

  1. [1]

    Chinonso Onah and Kristel Michielsen.Finite-Depth, Finite-Shot Guarantees for Constrained Quantum Optimization via Fejér Filtering. 2026. arXiv:2603.01809 [quant-ph].url:https://arxiv.org/abs/2603.01809

    arXiv 2026

  2. [2]

    The complexity of NISQ

    Sitan Chen et al. “The complexity of NISQ”. In:Nature Communications14 (2023), p. 6001.doi: 10.1038/s41467-023-41217-6

    doi:10.1038/s41467-023-41217-6 2023

  3. [3]

    QOPTLib: a Quantum-Computing-Oriented Benchmark for Combinatorial Optimisation Problems

    Eneko Osaba and Erika Villar-Rodríguez. “QOPTLib: a Quantum-Computing-Oriented Benchmark for Combinatorial Optimisation Problems”. In:Proc.Quantum Tech. 2024. 2024

    2024

  4. [4]

    Papadimitriou and Kenneth Steiglitz.Combinatorial Optimization: Al- gorithms and Complexity

    Christos H. Papadimitriou and Kenneth Steiglitz.Combinatorial Optimization: Al- gorithms and Complexity. Prentice Hall, 1982

    1982

  5. [5]

    Ising formulations of many NP problems

    Andrew Lucas. “Ising formulations of many NP problems”. In:Frontiers in Physics 2 (2014), p. 5.doi: 10.3389/fphy.2014.00005

    arXiv 2014

  6. [6]

    Lawler et al.The Traveling Salesman Problem: A Guided Tour of Com- binatorial Optimization

    Eugene L. Lawler et al.The Traveling Salesman Problem: A Guided Tour of Com- binatorial Optimization. Wiley, 1985

    1985

  7. [7]

    Garey and David S

    Michael R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979

    1979

  8. [8]

    Assignment Problems and the Location of Economic Activities

    Tjalling C. Koopmans and Martin Beckmann. “Assignment Problems and the Location of Economic Activities”. In:Econometrica25.1 (1957), pp. 53–76.doi: 10.2307/1907742

    doi:10.2307/1907742 1957

Show all 50 references
  1. [9]

    A Survey for the Quadratic Assignment Problem

    E. M. Loiola et al. “A Survey for the Quadratic Assignment Problem”. In: European Journal of Operational Research176.2 (2007), pp. 657–690.doi: 10.1016/j.ejor.2005.09.032

    2007 doi

  2. [10]

    Paolo Toth and Daniele Vigo.Vehicle Routing: Problems, Methods, and Applications. 2nd ed. MOS-SIAM Series on Optimization. SIAM, 2014.doi: 10.1137/1.9781611973594

    2014 doi

  3. [11]

    P-Complete Approximation Problems

    Sartaj Sahni and Teofilo Gonzalez. “P-Complete Approximation Problems”. In: Journal of the ACM23.3 (1976), pp. 555–565.doi: 10.1145/321958.321975

    1976

  4. [12]

    Wiley, 1990

    Silvano Martello and Paolo Toth.Knapsack Problems: Algorithms and Computer Implementations. Wiley, 1990

    1990

  5. [13]

    Reducibility among Combinatorial Problems

    Richard M. Karp. “Reducibility among Combinatorial Problems”. In:Complexity of Computer Computations. Plenum, 1972, pp. 85–103

    1972

  6. [14]

    Garey and David S

    Michael R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman and Company, 1979

    1979

  7. [15]

    QUEST: QUantum-Enhanced Shared Transportation

    Chinonso Onah et al. “QUEST: QUantum-Enhanced Shared Transportation”. In: 2025 IEEE International Conference on Quantum Computing and Engineering (QCE). Vol. 01. 2025, pp. 2149–2160.doi: 10.1109/QCE65121.2025.00235

    2025

  8. [16]

    Juan F. R. Hernandez et al.Quantum optimization beyond QUBO for industrial logistics and scheduling. 2026. arXiv:2605 . 30252 [quant-ph].url:https : / / arxiv.org/abs/2605.30252

    2026 arXiv

  9. [17]

    Chinonso Onah et al.Quantum and classical approaches to the optimization of highway platooning: the two-vehicle matching problem. 2026. arXiv:2603 . 18919 [quant-ph].url:https://arxiv.org/abs/2603.18919. 41

    2026

  10. [18]

    The Complexity of Flow- shop and Jobshop Scheduling

    Michael R. Garey, David S. Johnson, and Ravi Sethi. “The Complexity of Flow- shop and Jobshop Scheduling”. In:Mathematics of Operations Research1.2 (1976), pp. 117–129.doi: 10.1287/moor.1.2.117

    1976 doi

  11. [19]

    Complexity of Machine Scheduling Problems

    Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, and Peter Brucker. “Complexity of Machine Scheduling Problems”. In:Annals of Discrete Mathematics1 (1977), pp. 343–362.doi: 10.1016/S0167-5060(08)70743-X

    1977 doi

  12. [20]

    The Hungarian Method for the Assignment Problem

    Harold W. Kuhn. “The Hungarian Method for the Assignment Problem”. In:Naval Research Logistics Quarterly2.1-2 (1955), pp. 83–97.doi: 10.1002/nav.3800020109

    1955 doi

  13. [21]

    Algorithms for the Assignment and Transportation Problems

    James Munkres. “Algorithms for the Assignment and Transportation Problems”. In: Journal of the Society for Industrial and Applied Mathematics5.1 (1957), pp. 32–38. doi: 10.1137/0105003

    1957 doi

  14. [22]

    Paths, Trees, and Flowers

    Jack Edmonds. “Paths, Trees, and Flowers”. In:Canadian Journal of Mathematics 17 (1965), pp. 449–467.doi: 10.4153/CJM-1965-045-4

    1965 doi

  15. [23]

    Chinonso Onah, Roman Firt, and Kristel Michielsen.Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs. 2026. arXiv:2511 . 14296 [cs.ET].url:https://arxiv.org/abs/2511.14296

    2026

  16. [24]

    Chinonso Onah, Stuart Hadfield, and Kristel Michielsen.Separating Geometry From Interference in Constrained Quantum Optimization. 2026. arXiv:2607.13630 [quant-ph].url:https://arxiv.org/abs/2607.13630

    2026 arXiv

  17. [25]

    Chinonso Onah and Kristel Michielsen.Fundamental Limitations of QAOA on Con- strained Problems and a Route to Exponential Enhancement. 2025. arXiv:2511 . 17259 [quant-ph].url:https://arxiv.org/abs/2511.17259

    2025 arXiv

  18. [26]

    Chinonso Onah and Kristel Michielsen.Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations. 2026. arXiv:2604.04570 [quant-ph].url:htt ps://arxiv.org/abs/2604.04570

    2026 arXiv

  19. [27]

    Low-cost error mitigation by symmetry verification

    Xavier Bonet-Monroig et al. “Low-cost error mitigation by symmetry verification”. In:Physical Review A98.6 (Dec. 2018), p. 062339.doi: 10.1103/PhysRevA.98.062339.url: https://link.aps.org/doi/10.1103/PhysRevA.98.062339

    2018 doi

  20. [28]

    Experimental error mitigation via symmetry verification in a variational quantum eigensolver

    Ramiro Sagastizabal et al. “Experimental error mitigation via symmetry verification in a variational quantum eigensolver”. In:Physical Review A100.1 (July 2019), p. 010302.doi: 10.1103/PhysRevA.100.010302.url:https://link.aps.org/doi/ 10.1103/PhysRevA.100.010302

    2019 doi

  21. [29]

    Error mitigation for short- depth quantum circuits

    Kristan Temme, Sergey Bravyi, and Jay M. Gambetta. “Error mitigation for short- depth quantum circuits”. In:Physical Review Letters119.18 (Nov. 2017), p. 180509. doi: 10.1103/PhysRevLett.119.180509.url:https : / / link . aps . org / doi / 10 . 1103/PhysRevLett.119.180509

    2017 doi

  22. [30]

    Practical Quantum Error Mitiga- tionforNear-FutureApplications

    Suguru Endo, Simon C. Benjamin, and Ying Li. “Practical Quantum Error Mitiga- tionforNear-FutureApplications”.In:Physical Review X8.3(Aug.2018),p.031027. doi: 10.1103/PhysRevX.8.031027.url:https://link.aps.org/doi/10.1103/ PhysRevX.8.031027

    2018 doi

  23. [31]

    Mitigating measurement errors in multiqubit experiments

    Sergey Bravyi et al. “Mitigating measurement errors in multiqubit experiments”. In: Physical Review A103.4(Apr.2021),p.042605.doi:10.1103/PhysRevA.103.042605. url:https://link.aps.org/doi/10.1103/PhysRevA.103.042605. 42

    2021 doi

  24. [32]

    Error mitigation with Clifford quantum-circuit data

    Piotr Czarnik et al. “Error mitigation with Clifford quantum-circuit data”. In:Quan- tum5 (Nov. 2021), p. 592.doi: 10.22331/q-2021-11-26-592.url:https://doi.org/ 10.22331/q-2021-11-26-592

    2021 doi

  25. [33]

    From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz

    Stuart Hadfield et al. “From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz”. In:Algorithms12.2 (2019), p. 34.doi: 10.3390/a12020034

    2019 doi

  26. [34]

    Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm

    Franz G. Fuchs and Ruben Pariente Bassa. “Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm”. In:Algorithms15.6 (2022), p. 202. doi: 10.3390/a15060202

    2022 doi

  27. [35]

    Encodingtrade-offsand design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems

    NicolasPDSawaya,AlbertTSchmitz,andStuartHadfield.“Encodingtrade-offsand design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems”. In:Quantum7 (2023), p. 1111

    2023

  28. [36]

    Symmetries and Dimension Reduction in Quantum Approximate Optimization Algorithm

    B. Tsvelikhovskiy, I. Safro, and Y. Alexeev. “Symmetries and Dimension Reduction in Quantum Approximate Optimization Algorithm”. Version 2. In:arXiv preprint arXiv:2309.13787(2023). arXiv:2309.13787 [quant-ph].url:https://arxiv. org/abs/2309.13787

    2023 arXiv

  29. [37]

    Abhishek Awasthi et al.Constraint Preserving XY-Mixers under Trotterized Adia- batic Evolution. 2026. arXiv:2605.02465 [quant-ph].url:https://arxiv.org/ abs/2605.02465

    2026 arXiv

  30. [38]

    Constrained quantum optimization for extractive summa- rization on a trapped-ion quantum computer

    Pradeep Niroula et al. “Constrained quantum optimization for extractive summa- rization on a trapped-ion quantum computer”. In:Scientific Reports12 (2022), p. 17171.doi: 10.1038/s41598-022-20853-w.url:https : / / doi . org / 10 . 1038 / s41598-022-20853-w

    2022 doi

  31. [39]

    Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping

    Filip B. Maciejewski et al. “Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping”. In:Quantum9 (Nov. 2025), p. 1906.issn: 2521-327X.doi: 10.22331/q-2025-11-06-1906.url:http://dx.doi.org/10.22331/ q-2025-11-06-1906

    2025 doi

  32. [40]

    Maciejewski, and Davide Venturelli.Noise-Directed Adap- tive Remapping for Integer Optimization: from qubits to (encoded) qudits

    Stuart Hadfield, Filip B. Maciejewski, and Davide Venturelli.Noise-Directed Adap- tive Remapping for Integer Optimization: from qubits to (encoded) qudits. 2026. arXiv:2606.28234 [quant-ph].url:https://arxiv.org/abs/2606.28234

    2026 arXiv

  33. [41]

    Quantum Approximate Optimization via Noise-Directed Adaptive Warm-Starting

    Filip Maciejewski et al. “Quantum Approximate Optimization via Noise-Directed Adaptive Warm-Starting”. In:arXiv preprint arXiv:2607.09368(2026)

    2026 arXiv

  34. [42]

    Twisted Hybrid Algorithms for Combinatorial Optimization

    Libor Caha, Alexander Kliesch, and Robert Koenig. “Twisted Hybrid Algorithms for Combinatorial Optimization”. In:Quantum Science and Technology7.4 (2022), p. 045013.doi: 10.1088/2058-9565/ac7f4f.url:https://doi.org/10.1088/2058- 9565/ac7f4f

    2022 doi

  35. [43]

    Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems

    Tatsuhiko Shirai and Nozomu Togawa. “Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems”. In:IEEE Transactions on Quantum Engineering5 (2024). Art. no. 3101114, pp. 1–14.doi: 10.1109/TQE.2024.3376721.url: https://doi.or...

    2024

  36. [44]

    Finding Repeated Elements

    Jayadev Misra and David Gries. “Finding Repeated Elements”. In:Science of Com- puter Programming2.2 (1982), pp. 143–152.doi: 10.1016/0167-6423(82)90012-0. url:https://doi.org/10.1016/0167-6423(82)90012-0. 43

    1982 doi

  37. [45]

    An Improved Data Stream Summary: The Count-Min Sketch and Its Applications

    Graham Cormode and S. Muthukrishnan. “An Improved Data Stream Summary: The Count-Min Sketch and Its Applications”. In:Journal of Algorithms55.1 (2005), pp. 58–75.doi: 10.1016/j.jalgor.2003.12.001.url:https://doi.org/10.1016/j. jalgor.2003.12.001

    2005 doi

  38. [46]

    Polynomial-time approximation schemes for Euclidean Traveling Salesman and other geometric problems

    Sanjeev Arora. “Polynomial-time approximation schemes for Euclidean Traveling Salesman and other geometric problems”. In:Journal of the ACM45.5 (1998), pp. 753–782

    1998

  39. [47]

    Wilde.Quantum Information Theory

    Mark M. Wilde.Quantum Information Theory. 2nd ed. Cambridge University Press, 2017

    2017

  40. [48]

    Algorithm 235: Random Permutation

    Richard Durstenfeld. “Algorithm 235: Random Permutation”. In:Communications of the ACM7.7 (1964). Linear-time in-place implementation of the Fisher–Yates shuffle, p. 420.doi: 10.1145/364520.364540

    1964

  41. [49]

    Ayrton et al.Qiskit: An Open-source Framework for Quantum Computing

    M. Ayrton et al.Qiskit: An Open-source Framework for Quantum Computing. Ver- sion 0.47. 2023.url:https://qiskit.org

    2023

  42. [50]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang.Quantum Computation and Quantum In- formation. Cambridge University Press, 2000. 44

    2000

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.