Pith. sign in

REVIEW 3 major objections 4 minor 47 references

A continuous-time quantum walk on feasible vertex covers can rank vertices well enough to guide greedy reductions that beat degree-based classical greedy on tested random graphs.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-07-31 23:05 UTC pith:JS5OCNYU

load-bearing objection Clean construction, honest benchmarks, one calibration-robustness soft spot that should not block peer review. the 3 major comments →

arxiv 2607.27915 v1 pith:JS5OCNYU submitted 2026-07-30 quant-ph

Iterative quantum algorithms for the minimum vertex cover problem based on continuous-time quantum walks

Ruben Pariente Bassa , Finley A. Quinton , Franz G. Fuchs , Pascal Halffmann This is my paper
classification quant-ph
keywords minimum vertex covercontinuous-time quantum walkconstraint-preserving mixersgreedy reductionmaximum independent setfeasible-state graphTrotterisationquantum optimization
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper tries to establish that the hard constraints of minimum vertex cover can be baked into a continuous-time quantum walk rather than enforced by penalty terms. The walk lives entirely on the subspace of feasible covers, and its Hamiltonian is exactly the adjacency matrix of the graph of feasible covers connected by single-vertex flips. The resulting quantum state yields per-vertex scores — marginal inclusion probability or expected cover size after fixing a vertex — that the authors feed into a recursive greedy algorithm. On 3-regular, 4-regular, and connected Erdős–Rényi instances, they report that these quantum-informed rules give lower mean approximation ratios and solve a larger fraction of instances optimally than the corresponding degree-based greedy baselines, with the conditioned-energy score most stable under Trotterisation. The framework extends to maximum independent set by bitwise complementation and needs no variational training.

Core claim

Restricted to the feasible subspace, the projected Pauli-X Hamiltonian H_MVC = Σ_i Π_{N(i)} X_i coincides with the adjacency matrix of the induced feasible-state graph G_VC(G), whose vertices are feasible covers and whose edges are feasibility-preserving single-bit flips. Since every feasible cover is reachable from the all-in cover, a continuous-time quantum walk starting there explores all covers without ever leaving feasibility. The paper shows numerically that direct sampling of a minimum cover is exponentially suppressed in system size, but the walk's per-vertex marginals and conditioned energies encode global structural information through a light-cone of nested commutators. Using thos

What carries the argument

The central object is H_MVC = Σ_i Π_{N(i)} X_i, where the projector Π_{N(i)} requires all neighbours of i to already be in the cover, so flipping i can never uncover an edge. Restricted to the feasible subspace, H_MVC equals the adjacency matrix of the induced feasible-state graph G_VC(G). This identification turns the unitary e^{itH_MVC} into a continuous-time quantum walk on the layered graph of feasible covers, and the walk state provides vertex scores — marginal probabilities P_v or conditioned expected costs E_v — that drive a recursive greedy reduction. The connectivity theorem ensures every feasible cover is reachable from the all-in cover by allowed flips.

Load-bearing premise

The benchmark conclusions depend on a single walk duration calibrated on 100 small graphs per family and then reused at every graph size, every circuit depth, and every recursive step, even though the residual graph shrinks as vertices are fixed.

What would settle it

Take held-out 3-regular graphs at n=20. Run QEG-LDF with the n=18-calibrated walk time; run it again with t chosen by grid search on n=20; and run a classical degree-based greedy that is allowed the same kind of per-family tuning. If the fixed-time quantum variant is not better than the tuned classical baseline, the reported advantage is an artifact of calibration transfer.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • MIS is handled with the same machinery: bitwise complementation turns vertex covers into independent sets, so the constraint-preserving walk and greedy reduction transfer without new penalty terms.
  • For bounded-degree graphs, each Trotter layer of the walk has circuit depth independent of system size, and depth p=4 already tracks the exact evolution closely for QEG; shallow circuits suffice on the tested families.
  • The limiting resource is measurement: QEG requires one conditioned circuit per candidate vertex per recursive step, so the practical trade-off is score stability versus circuit-evaluation count.
  • Direct single-shot extraction of an optimal cover from the walk is not the right operating point; the useful quantum output is a ranking of vertices, not a solution state.
  • The p=1 Monte Carlo surrogate extends the same scores to graphs of hundreds of vertices, so the framework can be probed beyond exact-state sizes.

Where Pith is reading between the lines

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

  • An extension the authors leave implicit is adaptive walk-time selection: because the walk time is fixed from a calibration ensemble and not rescaled as the residual graph shrinks, recalibrating t at each recursion level is a natural next test and may change the size of the reported advantage.
  • At p=1 the quantum circuit reduces to a classical sequential removal process with removal probability determined by cos²(t); a classical probabilistic greedy with the same per-vertex tie-breaking would isolate how much of the gain comes from coherent multi-qubit interference rather than from the sequential pruning rule.
  • The layered-transport analysis suggests that cumulative probability in the bottom few layers saturates quickly, implying that per-vertex rankings stay informative at sizes where full quantum simulation is impossible; this could be tested by running the Monte Carlo surrogate at n beyond 300 and watching whether the gap to classical baselines widens or narrows.
  • The O(V^2) conditioned-circuit count of QEG motivates adaptive shot allocation, since scores are evaluated as exact expectation values in the paper; finite-shot estimation of small score gaps is likely the dominant hardware cost.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper proposes a penalty-free hybrid quantum-classical greedy framework for minimum vertex cover. The key construction is a projected-Pauli-X Hamiltonian whose restriction to the feasible subspace is the adjacency matrix of the induced graph of feasible covers; the authors prove that this graph is connected from the all-in cover and that a continuous-time quantum walk on it can be used to define vertex scores. Two score families are developed: QPG (marginal occupation probabilities) and QEG (conditioned expected cover size), each combined with LDF-like and SDF-like recursive reduction rules. Numerical benchmarks on 3-regular, 4-regular, and Erdős–Rényi graphs (n=8..20) compare the LDF variants against classical greedy baselines and FastVC, with walk times calibrated on independent n=18 ensembles. The paper also contains Trotter-depth analysis, a p=1 Monte Carlo surrogate up to n=300, and a Lean 4 formalization of support bookkeeping.

Significance. If the empirical claims hold, the paper gives a clean and conceptually appealing way to convert constrained continuous-time quantum walks into local greedy signals, without penalty terms or variational training. The structural results—Theorem 1, Corollary 1, Eq. (3), Proposition 1, and the parity selection rule—are mathematically sound and are partly machine-checked. The paper is honest about its calibration protocol, releases code and data, and explicitly separates the mathematical core from the heuristic benchmark contribution. However, the central empirical advantage is asserted for the LDF variants only, and the fixed calibrated walk time is transferred across sizes, Trotter depths, and recursion levels without a robustness analysis; this makes the headline claim less secure than the abstract suggests.

major comments (3)
  1. [Section VI.C, Eq. (10), Figures 7 and 9] The benchmark conclusion relies on a single calibrated walk time t* per (family, score, rule), selected on 100 n=18 instances and then used for every n in {8,...,20}, every finite Trotter depth, and every recursion level. This is a non-trivial transfer because the induced-graph depth D(G)=n-τ(G) changes with system size and shrinks during recursion, and Figures 4 and 7 indicate that the optimal contrast time depends on the layer structure. The paper discloses this and lists adaptive walk-time selection as future work, but it does not test whether the reported advantage is robust to the fixed choice. Please add a sensitivity analysis—for example, success-rate-vs-t curves for several sizes, per-size calibration, or rescaling t by D(G)—or explicitly restrict the claim to the tested fixed-time protocol. Without such an analysis, the empirical conclusion is contingent on an unexamined hyperpa
  2. [Section VI.B, Figure 11, abstract] The abstract claims that 'the quantum-informed algorithms achieve lower mean approximation ratios and solve a larger fraction of instances optimally than their corresponding classical greedy baselines.' Figure 11, however, compares only QPG-LDF and QEG-LDF against Greedy LDF, Greedy SDF, and FastVC; the SDF-like variants (QPG-SDF and QEG-SDF) are not shown against Greedy SDF in that figure. Figures 7, 9, and 10 present the SDF variants only among themselves. Thus the plural claim is not directly supported for the SDF rules. Either add the SDF-vs-Greedy-SDF comparison or qualify the abstract and conclusion to state that the demonstrated advantage is for the LDF variants.
  3. [Section VI.B, Fig. 11 caption] The figure caption states 'for n=18' while the horizontal axis runs over n=8,10,...,20. This is not merely a typo: it obscures whether the panel is aggregated over all sizes or only at n=18. If the panels are aggregated over sizes, the caption should say so; if they are per-size, the x-axis is redundant. Please clarify.
minor comments (4)
  1. [Section V.A vs Section VI.A] Section V.A says that for QPG the gap between p=4 and p=∞ is substantial, while Section VI.A says that already at p=4 the LDF performance is close to the exact evolution. The apparent tension should be reconciled, e.g., by distinguishing score fidelity from final success rate.
  2. [Eq. (10)] The notation bPopt is used before its full definition is given. Please introduce it explicitly as the empirical success rate on the calibration ensemble.
  3. [Section VI, first paragraph] The sentence about measurement shots appears parenthetically. Since the benchmarks use exact expectation values, it would be clearer to state explicitly in the results section that shot noise is not included in any figure, and to mention the resulting uncertainty in the conclusion.
  4. [Appendix D, Fig. 18] The p=1 Monte Carlo results are a useful extension, but the caption and text should more strongly emphasize that these are classical simulations of a quantum-inspired rule and do not constitute evidence of a quantum speedup. The current wording already says this, but the placement in a figure-heavy appendix may allow readers to over-interpret.

Circularity Check

0 steps flagged

No significant circularity: the central derivation is self-contained; the only calibrated quantity (walk time t*) is selected on disjoint calibration ensembles and then applied to held-out benchmarks.

full rationale

The paper's mathematical core — the reachability theorem, the induced feasible-state graph, and the identification of the projected-Pauli Hamiltonian with the adjacency matrix of that graph — is derived from the definitions of the vertex-cover feasibility projector and the neighbourhood-controlled operators, not from the target result. Equation (3), H_MVC restricted to H_VC equals A(G_VC(G)), is an exact algebraic reformulation by construction, not a fitted or predicted output. The QPG and QEG scores are explicit expectation values: P_v(t) is the marginal occupation of the CTQW state and E_v(t) is the conditioned expected cost; neither is defined in terms of the benchmark outcome or the optimal cover. The only fitted quantity is the walk time t*, selected in Eq. (10) by maximizing the empirical success rate on independent calibration ensembles of 100 n=18 instances. The paper explicitly states that these calibration ensembles are disjoint from every benchmark ensemble used in figure 11, and that all benchmark points are evaluated on held-out ensembles. Using a hyperparameter tuned on a separate calibration set to evaluate held-out instances is standard hyperparameter calibration, not circular reasoning: the benchmark success rates are not equal by construction to the calibration objective. The paper also discloses the limitation that t* is not rescaled as the residual graph shrinks and lists adaptive walk-time selection as an open question; this is a robustness/transfer concern about the empirical comparison, not a circularity. Self-citations such as [12] and [17] are not load-bearing for the central claim: the projected Pauli mixers are attributed to the external reference [14], and the connectivity result is proved in the paper itself, with the support bookkeeping additionally machine-verified in Lean 4. No step in the paper's derivation chain reduces to its own input, and no fitted parameter is renamed as a prediction. The reported quantum advantage is an empirical benchmark result conditional on calibrated hyperparameters, not a conclusion forced by definition or by a self-citation chain.

Axiom & Free-Parameter Ledger

2 free parameters · 6 axioms · 0 invented entities

The mathematical construction rests on standard quantum-walk and Lie-algebra facts plus the definition of the projected mixers from ref. [14]. The empirical claims rely on one fitted hyperparameter (walk time) and on procedural assumptions about calibration/benchmark separation. No new physical entities are postulated; the induced feasible-state graph is an analytic object derived from the problem constraints.

free parameters (2)
  • Walk time t*_{s,R,f} = not stated numerically; chosen from grid {0, π/16, ..., π} via Eq. (10)
    One walk-time hyperparameter per score function, reduction rule, and graph family, chosen by maximizing empirical success on an independent 100-graph calibration ensemble at n=18; then held fixed for all benchmark sizes and recursion levels.
  • Trotter depth p=4 for headline benchmarks = 4
    Headline results in Fig. 11 use p=4; the paper also scans p=1..4. This is a design choice, not fitted to the benchmark, but it is part of the reported operating point.
axioms (6)
  • standard math The projected Pauli-X operators \hat X_i = Π_{N(i)} X_i preserve the feasible vertex-cover subspace, and the restricted Hamiltonian H_MVC equals the adjacency matrix of the induced feasible-state graph.
    Proven in Sections II and IV, Eq. (3); relies on the standard definition of the vertex-cover projector.
  • standard math The reference state |Ω> = |1>^⊗n is a feasible cover, and every feasible cover is reachable from it by constraint-preserving single flips.
    Theorem 1/Corollary 1; proof is self-contained.
  • standard math First-order Suzuki–Trotter error is O(|E|t^2/p) and supports the low-depth approximations used in benchmarks.
    Standard product-formula bound; Appendix C.2.
  • domain assumption For bounded-degree graphs, each Trotter layer can be implemented in constant depth using ancilla-free multi-controlled SU(2) decompositions.
    Uses chromatic number of the squared graph and decomposition bounds from refs. [31,32]; these are cited external results, not re-derived.
  • domain assumption Calibration ensembles are independent of benchmark ensembles and representative of the three graph families.
    Procedural assumption in Section VI C; the paper explicitly constructs disjoint ensembles, but representativeness is assumed.
  • ad hoc to paper The walk-time grid {0, π/16, ..., π} contains a good operating point for each family.
    The grid and the success-rate objective in Eq. (10) are chosen by the authors; there is no theoretical guarantee that the calibrated time transfers to all sizes and recursion levels.

pith-pipeline@v1.3.0-daily-deepseek · 31713 in / 17671 out tokens · 158640 ms · 2026-07-31T23:05:12.108361+00:00 · methodology

0 comments
read the original abstract

We introduce a constraint-preserving hybrid quantum-classical greedy framework for the minimum vertex cover problem, which extends directly to maximum independent set by bitwise complementation. The framework uses projected Pauli-X terms whose sum preserves the feasible subspace and acts within it exactly as the adjacency matrix of a layered graph of feasible covers. This graph is connected, so every feasible cover is linked to the configuration containing all vertices by a sequence of allowed single-vertex flips. Starting from this configuration, the corresponding continuous-time quantum walk propagates amplitude into layers containing progressively smaller covers. We rank vertices using either their marginal cover probabilities or the expected cover size obtained after fixing each candidate vertex in the cover, and use these rankings to guide recursive greedy reductions. Across several random-graph families, with walk times fixed using independent calibration ensembles, the quantum-informed algorithms achieve lower mean approximation ratios and solve a larger fraction of instances optimally than their corresponding classical greedy baselines. The conditioned-energy strategy performs best on the tested instances and retains algorithmic performance close to the exact continuous-time limit under low-depth Trotterisation. For bounded-degree graphs, each Trotter layer has circuit depth independent of system size, and the framework requires neither penalty terms nor variational training.

Figures

Figures reproduced from arXiv: 2607.27915 by Finley A. Quinton, Franz G. Fuchs, Pascal Halffmann, Ruben Pariente Bassa.

Figure 1
Figure 1. Figure 1: Schematic of the iterative quantum algorithm. The input graph [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a) Graph illustrating a vertex q6 (red) and its neighbourhood N (6) (blue). The neighbours may have additional edges among themselves or to other vertices not shown. (b) Circuit representation of the constraint preserving unitary U6(α) = e iαXˆ6 . A single-qubit rotation is applied to vertex 6, conditioned on all neighbouring qubits being in the state |1⟩, thereby restricting the dynamics to the vertex-co… view at source ↗
Figure 3
Figure 3. Figure 3: Example of the implicitly induced feasible-state graph underlying the constrained continuous-time [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: Cumulative bottom-ℓ peak probability P ⋆ ≤ℓ (n) ≡ maxt P j≤ℓ PD(G)−j (t) as a function of n at fixed offset ℓ from the minimum-cover layer. Markers show numerical data; lines show exponential fits Aℓe −αℓn. For ℓ ≥ 5, the fitted decay rate αℓ is statistically indistinguishable from zero over the simulated range. Error bars show the corresponding standard deviation. in the system size. Hitting the minimum-c… view at source ↗
Figure 6
Figure 6. Figure 6: Vertex occupation probabilities Pv(t) as a function of the continuous quantum walk time t for the depicted small example graph. As t increases, higher-order terms in the commutator expansion become relevant and the quantum walk propagates in the layered graph, leading to a progressive separation of probability profiles and encoding increasingly nonlocal structural information, revealing how the quantum sta… view at source ↗
Figure 7
Figure 7. Figure 7: Walk-time selection for QPG on 100 random [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Vertex Energy Ev(t) as a function of the continuous quantum walk time t for the depicted small example graph. Similarly as for the probability case, as t increases, higher-order terms in the commutator expansion become relevant, the quantum walk spread in the layered graph, leading to a progressive separation of energies profiles encoding increasingly nonlocal structural information. changes the graph-wide… view at source ↗
Figure 10
Figure 10. Figure 10: QPG and QEG performances as a function of the number of Trotter layers [PITH_FULL_IMAGE:figures/full_fig_p013_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Empirical exact-recovery rate (bottom row) and mean approximation ratio (top row) at circuit depth [PITH_FULL_IMAGE:figures/full_fig_p014_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Exact echo-fidelity scores Fv,∞(t, t) for the vertices of the depicted small example graph, shown as functions of the common echo time t = ta = tb. The curve colours correspond to the vertex colours in the inset, and the separation of the scores produces the vertex ranking used by QFG. Appendix A: Quantum Fidelity Greedy algorithm The main greedy strategies presented in the paper select vertices based on … view at source ↗
Figure 13
Figure 13. Figure 13: Echo-time selection for QFG on 100 random 3-regular graph instances with [PITH_FULL_IMAGE:figures/full_fig_p019_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: (a) Graphical representation of two adjacent vertices, [PITH_FULL_IMAGE:figures/full_fig_p022_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Trotter error analysis for the constrained continuous-time quantum walk. Left: Norm-2 distance between [PITH_FULL_IMAGE:figures/full_fig_p027_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Mean von Neumann block entropy Sblocks averaged over 40 connected subgraphs. Left: Sblocks as a function of walk time t for connected blocks of size k = n/2. Right: Scaling of the maximum block entropy S max blocks with total system size n at t = π/4. Appendix D: Monte Carlo simulation for p = 1 Although the constrained quantum-walk state can exhibit substantial entanglement, a simplification occurs in th… view at source ↗
Figure 17
Figure 17. Figure 17: Quantum-state-tree representation for a four-vertex example. The unbalanced tree is shown on the left, [PITH_FULL_IMAGE:figures/full_fig_p028_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Mean approximation ratio obtained using the [PITH_FULL_IMAGE:figures/full_fig_p031_18.png] view at source ↗

discussion (0)

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

Reference graph

Works this paper leans on

47 extracted references · 2 canonical work pages

  1. [1]

    R. M. Karp, Reducibility among combinatorial problems, in50 Years of Integer Programming 1958-2008: from the Early Years to the State-of-the-Art(Springer, 2009) pp. 219–241

    1958

  2. [2]

    V. V. Vazirani,Approximation algorithms, Vol. 1 (Springer, 2001)

    2001

  3. [3]

    Khot, On the power of unique 2-prover 1-round games, inProceedings of the thiry-fourth annual ACM sympo- sium on Theory of computing(2002) pp

    S. Khot, On the power of unique 2-prover 1-round games, inProceedings of the thiry-fourth annual ACM sympo- sium on Theory of computing(2002) pp. 767–775

    2002

  4. [4]

    Halld´ orsson and J

    M. Halld´ orsson and J. Radhakrishnan, Greed is good: Approximating independent sets in sparse and bounded- degree graphs, Algorithmica (New York)18, 145 (1997)

    1997

  5. [5]

    Krysta, M

    P. Krysta, M. Mari, and N. Zhi, Ultimate greedy approxi- mation of independent sets in subcubic graphs, Algorith- mica86, 3518 (2024)

    2024

  6. [6]

    T. A. Feo and M. G. C. Resende, Greedy randomized adaptive search procedures, Journal of Global Optimiza- tion6, 109 (1995)

    1995

  7. [7]

    Bang-Jensen, G

    J. Bang-Jensen, G. Gutin, and A. Yeo, When the greedy algorithm fails, Discrete Optimization1, 121 (2004)

    2004

  8. [8]

    Lucas, Ising formulations of many np problems, Fron- tiers in Physics2, 5 (2014)

    A. Lucas, Ising formulations of many np problems, Fron- tiers in Physics2, 5 (2014)

    2014

  9. [9]

    Pelofske, G

    E. Pelofske, G. Hahn, and H. Djidjev, Solving large min- imum vertex cover problems on a quantum annealer, arXiv:1904.00051 (2019)

    Pith/arXiv arXiv 1904

  10. [10]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm, arXiv (2014), arXiv:1411.4028 [quant-ph]

    Pith/arXiv arXiv 2014

  11. [11]

    Peruzzo, J

    A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien, A variational eigenvalue solver on a photonic quantum processor, Nature communications5, 4213 (2014)

    2014

  12. [12]

    F. G. Fuchs, K. O. Lye, H. Møll Nilsen, A. J. Stasik, and G. Sartor, Constraint preserving mixers for the quantum approximate optimization algorithm, Algorithms15, 202 (2022)

    2022

  13. [13]

    Herman, R

    D. Herman, R. Shaydulin, Y. Sun, S. Chakrabarti, S. Hu, P. Minssen, A. Rattew, R. Yalovetzky, and M. Pistoia, Constrained optimization via quantum zeno dynamics, Communications Physics6, 219 (2023)

    2023

  14. [14]

    Hadfield, Z

    S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, From the quantum ap- proximate optimization algorithm to a quantum alternat- ing operator ansatz, Algorithms12, 10.3390/a12020034 (2019)

    doi:10.3390/a12020034 2019

  15. [15]

    Z. Wang, N. C. Rubin, J. M. Dominy, and E. G. Rief- fel, XY mixers: Analytical and numerical results for the quantum alternating operator ansatz, Phys. Rev. A101, 012320 (2020). 17

    2020

  16. [16]

    B¨ artschi and S

    A. B¨ artschi and S. Eidenbenz, Grover mixers for qaoa: Shifting complexity from mixer design to state prepara- tion, arXiv:2006.00354 (2020)

    Pith/arXiv arXiv 2006

  17. [17]

    F. G. Fuchs and R. P. Bassa, Lx-mixers for qaoa: Op- timal mixers restricted to subspaces and the stabilizer formalism, Quantum8, 1535 (2024)

    2024

  18. [18]

    Z. H. Saleem, Max-independent set and the quantum al- ternating operator ansatz, International Journal of Quan- tum Information18, 2050011 (2020)

    2020

  19. [19]

    Bucher, J

    D. Bucher, J. Stein, S. Feld, and C. Linnhoff-Popien, Penalty-free approach to accelerating constrained quan- tum optimization, Physical Review A112, 062605 (2025)

    2025

  20. [20]

    Montanaro, Quantum speedup of branch-and-bound algorithms, Physical Review Research2, 013056 (2020)

    A. Montanaro, Quantum speedup of branch-and-bound algorithms, Physical Review Research2, 013056 (2020)

    2020

  21. [21]

    Chakrabarti, P

    S. Chakrabarti, P. Minssen, R. Yalovetzky, and M. Pistoia, Universal quantum speedup for branch- and-bound, branch-and-cut, and tree-search algorithms, arXiv preprint arXiv:2210.03210 (2022)

    Pith/arXiv arXiv 2022

  22. [22]

    Wilkening, A.-I

    S. Wilkening, A.-I. Lefterovici, L. Binkowski, M. Perk, S. P. Fekete, and T. J. Osborne, A quantum algorithm for solving 0-1 knapsack problems, npj Quantum Infor- mation11, 10.1038/s41534-025-01097-8 (2025)

    work page doi:10.1038/s41534-025-01097-8 2025

  23. [23]

    D. J. Egger, J. Mareˇ cek, and S. Woerner, Warm-starting quantum optimization, Quantum5, 479 (2021)

    2021

  24. [24]

    Bravyi, A

    S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Hybrid quantum-classical algorithms for approximate graph col- oring, Quantum6, 678 (2022)

    2022

  25. [25]

    J. R. Finˇ zgar, A. Kerschbaumer, M. J. Schuetz, C. B. Mendl, and H. G. Katzgraber, Quantum-informed recur- sive optimization algorithms, PRX Quantum5, 020327 (2024)

    2024

  26. [26]

    F. Luiz, A. Iwakami, D. Moraes, and M. de Oliveira, Scalable quantum walk-based heuristics for the minimum vertex cover problem, arXiv preprint arXiv:2512.02940 (2025)

    Pith/arXiv arXiv 2025

  27. [27]

    L. T. Brady and S. Hadfield, Iterative quantum algo- rithms for maximum independent set, Phys. Rev. A110, 052435 (2024)

    2024

  28. [28]

    Dupont, B

    M. Dupont, B. Evert, M. J. Hodson, B. Sundar, S. Jef- frey, Y. Yamaguchi, D. Feng, F. B. Maciejewski, S. Had- field, M. S. Alam, Z. Wang, S. Grabbe, P. A. Lott, E. G. Rieffel, D. Venturelli, and M. J. Reagor, Quantum- enhanced greedy combinatorial optimization solver, Sci- ence Advances9, 10.1126/sciadv.adi0487 (2023)

    work page doi:10.1126/sciadv.adi0487 2023

  29. [29]

    A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by a quantum walk, inProceedings of the thirty-fifth an- nual ACM symposium on Theory of computing, STOC03 (ACM, 2003) pp. 59–68

    2003

  30. [30]

    S. Cai, Balance between complexity and quality: Lo- cal search for minimum vertex cover in massive graphs, inProceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI)(2015) pp. 747–753

    2015

  31. [31]

    Barenco, C

    A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, Elementary gates for quantum computa- tion, Phys. Rev. A52, 3457 (1995)

    1995

  32. [32]

    R. Vale, T. M. D. Azevedo, I. C. S. Ara´ ujo, I. F. Araujo, and A. J. da Silva, Circuit decomposition of multicontrolled special unitary single-qubit gates, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 10.1109/TCAD.2023.3327102 (2024), arXiv:2302.06377

    arXiv 2023

  33. [33]

    A. J. da Silva and D. K. Park, Linear-depth quantum cir- cuits for multiqubit controlled gates, Phys. Rev. A106, 042602 (2022)

    2022

  34. [34]

    Claudon, J

    B. Claudon, J. Zylberman, C. Feniou, F. Debbasch, A. Peruzzo, and J.-P. Piquemal, Polylogarithmic-depth controlled-not gates without ancilla qubits, Nature Com- munications15, 5886 (2024)

    2024

  35. [35]

    N. J. Ross and P. Selinger, Optimal ancilla-free clifford+t approximation of z-rotations, Quantum Inf. Comput.16, 901 (2016)

    2016

  36. [36]

    P. J. Christiansen, L. Binkowski, D. Ramacciotti, and S. Wilkening, Quantum tree generator improves qaoa state-of-the-art for the knapsack problem, in2025 IEEE International Conference on Quantum Computing and Engineering (QCE)(IEEE, 2025) p. 1–10

    2025

  37. [37]

    Wilkening, Constraint-oriented biased quantum search for general constrained combinatorial optimization prob- lems (2025), arXiv:2512.08384 [quant-ph]

    S. Wilkening, Constraint-oriented biased quantum search for general constrained combinatorial optimization prob- lems (2025), arXiv:2512.08384 [quant-ph]. 18 0 π/4 π/2 3π/4 π0 0.2 0.4 0.6 0.8 1 1 2 3 4 5 6 7 Timet Fv(t) Figure 12: Exact echo-fidelity scoresF v,∞(t, t) for the vertices of the depicted small example graph, shown as functions of the common e...

    arXiv 2025

  38. [38]

    Constraint-preserving operators We begin by reviewing the projection formalism that ensures all operators respect the vertex-cover constraint. The projector onto the valid vertex-cover subspace is ΠVC = X C∈VC |C⟩⟨C|= Y (i,j)∈E I− |00⟩⟨00|ij , where the product form explicitly enforces the edge constraintC i +C j ≥1 for every edge (i, j)∈E. To implement P...

  39. [39]

    Nested commutators The QPG selection probabilityP v(t) in equation (7) is governed by nested commutators ofHMVC withZ v. The QEG energy estimateE v(t) in equation (8) instead involves nested commutators of the candidate-conditioned Hamiltonian H (v) MVC with the Pauli-Zterms in the cost HamiltonianH C = |V| 2 I− 1 2 P i∈V Zi. For QFG, the echo expansion i...

  40. [40]

    A transpose-symmetry argument eliminates all odd-order contributions

    Parity selection rules The QPG and QEG observables contain expectation values of nested commutators in the real reference state |Ω⟩=|1⟩ ⊗|V| . A transpose-symmetry argument eliminates all odd-order contributions. Lemma 2(Parity selection).LetAandC 0 be real symmetric operators in the computational basis, and define Cr = [A, Cr−1] forr≥1. ThenC T r = (−1)r...

  41. [41]

    A single Trotter step of the walk unitary is Ustep(τ) = Y i∈V eiτΠ N(i) Xi = Y i∈V CN(i) RXi (τ), τ= t p .(C1) The full state-preparation circuit is Up(t) =U step(τ) p

    Gate count and circuit depth We quantify the cost of preparing the trotterised continuous-time quantum walk (CTQW) state. A single Trotter step of the walk unitary is Ustep(τ) = Y i∈V eiτΠ N(i) Xi = Y i∈V CN(i) RXi (τ), τ= t p .(C1) The full state-preparation circuit is Up(t) =U step(τ) p. Throughout, we writen=|V|,m=|E|,d i =|N(i)|, and ∆ = max i di. a. ...

  42. [42]

    The exact continuous-time evolution is U(t) =e itHMVC

    T rotter error analysis We now analyse the error introduced by the trotterisation of the continuous-time quantum walk evolution. The exact continuous-time evolution is U(t) =e itHMVC. Since the local terms ˆXi do not generally commute, the exact evolution is approximated through a first-order Suzuki–Trotter decomposition: Up(t) = Y i∈V ei t p ˆXi !p , whe...

  43. [43]

    Over the tested system sizes, the approximately linear growth of the maximum block entropy withnis consistent with volume-law entanglement

    Entanglement analysis Figure 16 shows the time dependence of the mean von Neumann entropyS blocks for connected blocks of sizek=n/2 and the scaling of its maximum with system size. Over the tested system sizes, the approximately linear growth of the maximum block entropy withnis consistent with volume-law entanglement. The circuit structure provides a mec...

  44. [44]

    The final quantum state can be written as |ψ(t)⟩= Y i∈V CN(i) RXi(t)|Ω⟩, where the ordering of vertices induces a sequential structure in the circuit

    Quantum tree representation of the feasible subspace Forp= 1, the evolved quantum state admits a natural interpretation as a weighted superposition over feasible vertex covers. The final quantum state can be written as |ψ(t)⟩= Y i∈V CN(i) RXi(t)|Ω⟩, where the ordering of vertices induces a sequential structure in the circuit. a. Quantum tree construction....

  45. [45]

    Introducing the change of variablesx:= cos 2(t), x∈[0,1], the expectation value can be expressed as a relaxed pseudo-Boolean function

    Cost function as pseudo-Boolean function The expectation value of the cost HamiltonianH C = |V| 2 − 1 2 P i∈V Zi with respect to the quantum state|ψ(t)⟩can be expressed as ⟨ψ(t)|H C |ψ(t)⟩= X C∈VC(G) cost(C) Y j∈RγC sin2(t) Y k∈LγC cos2(t), whereR γC ,L γC correspond to the sets of qubits that can be flipped along the pathγ C in the quantum tree. Introduc...

  46. [46]

    Sequential Monte Carlo sampler Equations (D1) and (D2) show that both QEG and QPG scores atp= 1 are expectations under the path measure wγ(x). Becausew γ factorises over the tree, a path can be drawn by a single top-down traversal that visits vertices in the fixed order and respects feasibility, with no global summation over the exponentially many covers....

  47. [47]

    Numerical results up ton= 300 Figure 18 reports the mean approximation ratio of thep= 1 surrogate for QPG and QEG, in both LDF and SDF variants, on 20 instances per size for 3-regular, 4-regular, and Erd˝ os–R´ enyi (ρ= 0.3) graphs, with sizes up ton= 300. Each score is estimated fromN= 10 4 Monte Carlo samples drawn using algorithm 2, with the vertices v...