Pith. sign in

REVIEW 4 major objections 5 minor 18 references

Benchmarking Quantum Heuristics: Non-Variational QWOA for Weighted Maxcut

T0 review · 4 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 non-variational QWOA reaches a constant average-case measurement probability for global optima of weighted maxcut using quadratically many alternating unitaries.

desk verdict Incremental but honest benchmark of non-variational QWOA on maxcut; the quadratic-depth claim is partly enforced by fitting, but the paper deserves a careful referee. read the letter →

arxiv 2505.24191 v1 pith:B5H36RNV submitted 2025-05-30 quant-ph physics.comp-ph

Tavis Bennett , Aidan Smith , Edric Matwiejew , Jingbo Wang This is my paper
classification quant-phphysics.comp-ph MSC 81P6868Q12
keywords quantumwalkoptimisationalgorithmweightedmaxcutnon-variationalQWOAheuristiccombinatorialaverage-casemeasurementprobabilityadvantagestateamplification
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 benchmarks the non-variational Quantum Walk Optimisation Algorithm (QWOA) on random weighted maxcut instances with up to 31 qubits. It claims that a circuit built from quadratically many alternating phase-separation and mixing unitaries keeps the average-case probability of measuring a globally optimal solution near the 10 percent target across the whole range, with the required iteration count fitting $p(n)=0.019n^2+0.053n-0.092$. This matters because classical local-search heuristics on the same instances show solve probabilities that decay roughly exponentially as $n$ grows. If the quadratic scaling extends beyond the simulated range, the algorithm would offer a polynomial-cost route to constant success probability on an NP-hard problem, which the paper describes as a necessary but not sufficient condition for quantum advantage.

What carries the argument

The central object is the non-variational QWOA ansatz: an alternating sequence of phase-separation unitaries that encode the objective function and mixing unitaries that implement a continuous-time quantum walk on a problem-specific graph, with all layer angles generated from just three continuous parameters $(\gamma,t,\beta)$ through linear schedules. The three parameters are tuned once per instance by a classical optimizer to maximize the expected objective value. The amplifier's interference is biased toward globally optimal solutions, and the paper's quantitative claim rests on the quadratic fit $p(n)=0.019n^2+0.053n-0.092$ obtained from interpolating measured probabilities at the 10 percent target.

What would settle it

Repeat the benchmark for $n=32$ to roughly 50 using the same protocol and several random restarts of the parameter optimizer; if the iteration count needed for a 10 percent average measurement probability departs from the quadratic fit, or if the measurement probability decays with $n$, the central claim collapses.

Watch

Extended reading notes

Core claim

The central claim is that the non-variational QWOA can amplify globally optimal solutions of random weighted maxcut instances to a roughly constant average-case measurement probability using only quadratically many alternating unitaries. Over 1,000 random graphs per problem size, the number of iterations needed to hit the 10 percent target is fit by $p(n)=0.019n^2+0.053n-0.092$ for $10\le n\le 31$. At $n=31$ this corresponds to amplification by a factor over $10^8$ relative to the equal superposition state, versus 1,681 for unstructured quantum search at the same iteration count. The paper positions this as a contrast with classical local-search heuristics, whose solve probability decays approximately exponentially on the same instances, and as supporting evidence for quantum advantage that is not yet conclusive.

Load-bearing premise

The whole quadratic-scaling result depends on the per-instance parameter search actually finding the best three parameters, and on the linear interpolation between measured probabilities giving an unbiased estimate of the iteration count at the 10 percent target.

Editorial extensions

If this is right

  • If the quadratic scaling holds beyond $n=31$, random weighted maxcut instances can be sampled at roughly 10 percent probability with circuit depth $O(n^2)$, so a few thousand measurements would suffice rather than an exponential number.
  • The constant measurement probability corresponds to amplification that grows exponentially with $n$ (over $10^8$ at $n=31$), meaning the algorithm extracts more advantage from instance structure as problems grow.
  • On the same benchmark instances, the two local-search baselines show solve probability decaying roughly exponentially, so the quantum heuristic's constant probability would represent a qualitative separation at polynomial cost.
  • The paper notes that this behavior is a necessary but not sufficient condition for quantum advantage; confirming it at larger sizes or on other problem classes remains open.

Reading between the lines

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

  • A testable extension would be to fix the three parameters from one instance and apply them to new instances from the same distribution; if the constant-probability behavior survives without per-instance optimization, the heuristic becomes far more practical.
  • The paper compares circuit iterations to classical function evaluations but does not count the per-instance classical optimizer cost itself, so the end-to-end resource comparison with classical heuristics is not yet complete.
  • The 10 percent target is arbitrary; checking whether the quadratic iteration scaling holds for other target probabilities, such as 1 percent or 50 percent, would show whether the amplification mechanism is fundamentally polynomial or just calibrated to this threshold.
  • Random graphs may not represent the hardest or most structured cases; benchmarking on planted-partition or skewed-weight instances would delineate the regime where the claimed advantage persists.
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

4 major / 5 minor

Summary. The paper benchmarks the non-variational Quantum Walk Optimisation Algorithm (QWOA) on random weighted maxcut instances with n=10--31, using classical statevector simulations. For each instance and iteration count p, three parameters (gamma, t, beta) are tuned by L-BFGS to maximize the expected cut value. The authors estimate, via linear interpolation, the number of iterations needed for the mean measurement probability to reach a 10% target, fit a quadratic p(n) = 0.019n^2 + 0.053n - 0.092 to those estimates, and then evaluate the algorithm at that prescribed p to report constant average-case measurement probability. They compare this against Grover's algorithm and two unnamed local-search heuristics, concluding that the non-variational QWOA may offer a significant scaling advantage.

Significance. If the central scaling claim were established, the result would be important: a non-variational quantum heuristic achieving roughly constant probability of sampling global optima of NP-hard random weighted maxcut instances with only quadratic circuit depth, over n=10--31, would be a notable demonstration and a meaningful step toward assessing quantum advantage. The paper's experimental effort is substantial, including 1,000 random instances per size and GPU-based statevector simulation up to n=31, and the reported error bars suggest care in data collection. However, the current analysis does not independently confirm the central claim: the constant probability is largely built in by using the fitted p(n) to set the evaluation points, and the optimization step on which all estimates rest is not validated. The paper is best read as a promising but preliminary benchmarking study whose headline conclusion needs additional support.

major comments (4)
  1. [§IV, Eq. (1), Figs. 4–6] The central claim that the iteration count required for constant average-case measurement probability scales quadratically is not independently tested. The blue points in Fig. 4 are precisely the interpolated iteration counts at which the mean measurement probability reaches the 10% target; Eq. (1) is fitted to those points; and Figs. 5 and 6 then evaluate the algorithm at p(n) rounded to the nearest integer. The approximately 10% probabilities shown there are therefore a consistency check with the fitted target rather than independent evidence for the scaling. To support the claim, the authors should evaluate the algorithm at p values not used in the fit (for example, held-out instances or extrapolated iteration counts), or report measured probabilities at fixed integer p before any fitting is performed.
  2. [Section III, Algorithm 1] The per-instance L-BFGS optimization over (gamma, t, beta) is a local method applied to a nonconvex objective, the negative expected maxcut value. The manuscript does not report the initial guess x0, any restart strategy, or a success/convergence criterion. If the optimizer returns poorer local maxima as n grows, the estimated required p for large n would be inflated, and the apparent quadratic growth in Eq. (1) could partly describe optimizer degradation rather than a property of QWOA. The authors should justify the optimization reliability, for example by reporting multistart results, comparing against grid or random restarts on a subset of instances, and giving the distribution of final objective values across instances and sizes.
  3. [Section IV, interpolation of iteration counts] The 'estimated exact non-integer number of iterations' is obtained by linear interpolation of the mean measurement probability between adjacent integer p values. This interpolation model is unvalidated; if the mean probability curve is convex or concave with n-dependent curvature, the crossing point will be systematically biased, and that bias propagates directly into the quadratic coefficient in Eq. (1). Additionally, the blue confidence region in Fig. 3 is obtained by linearly interpolating 95% confidence intervals, which does not produce a valid confidence interval for the crossing-time estimate. The authors should validate the interpolation (e.g., fit a nonlinear model and check residuals) and report how the fitted p(n) changes under alternative interpolation assumptions.
  4. [Section IV, Fig. 6] The comparison with classical heuristics is not fully specified. The two local-search heuristics used for Fig. 6 are never named or described, and their stopping rules are not given. Since the quantum iteration count p is chosen to meet a fixed 10% target while the classical heuristics presumably run until local termination, the number-of-evaluations comparison in Fig. 6(left) mixes different success criteria. The authors should specify the heuristics, the neighbourhood structure, the termination condition, and the amount of computation allowed, so that the comparison is reproducible and the claimed advantage is quantified against well-defined baselines.
minor comments (5)
  1. [Section III, text near Algorithm 1] The sentence 'As detailed in ??1' contains a broken cross-reference; please replace it with the appropriate section or reference.
  2. [Section IV, Figs. 3–5] The text states that simulation results are shown for n=10 to n=30 in Fig. 3 and Fig. 4, while Fig. 5 includes n=31; please clarify why n=31 is excluded from the interpolation and fitting procedure and how the p value for n=31 is set.
  3. [Eq. (1)] The quadratic fit is reported without fit quality metrics or uncertainties on the coefficients; please report residuals, R^2, and parameter uncertainties so the reader can judge how closely the blue points agree with the fit.
  4. [Section IV, Fig. 6] The text says the quantum measurement probability is based on 'four shots', but the simulations are statevector-based; it would be clearer to state whether the reported probability is the exact probability from the statevector or a sampled estimate from four projective measurements, and if the latter, to report the associated sampling uncertainty.
  5. [Algorithm 1, lines 6–7] The schedule formulas involve division by (p-1); since the starting value is p=2 this is numerically fine, but for completeness the reader should be told whether p=1 is excluded.

Circularity Check

2 steps flagged · score 6.0 of 10

Partial circularity: the 'constant probability' result is a self-imposed 10% target used to fit Eq. (1), and the later panels using Eq. (1) only re-check that fit; the quadratic scaling itself is independent empirical content.

  1. self definitional [Section IV, Eq. (1) and Fig. 5 description]
    "The estimated number of iterations required to produce a mean measurement probability equal to the target 10%, shown in blue in Fig. 3, are compiled in a single plot in Fig. 4. Importantly, a quadratic fit, p(n)=0.019n2+0.053n−0.092,(1) is shown in blue which agrees very closely with the estimated values."

    Eq. (1) is fitted to the blue points in Fig. 4, and those points are defined as the interpolated iteration counts at which the mean measurement probability equals the authors' chosen target of 10%. Using Eq. (1) to set p for Fig. 5 and then reporting probabilities 'around the target 10%' is therefore a consistency check on the same data used for the fit, not an independent confirmation that QWOA achieves constant probability. The constant-probability claim is a target imposed by construction; the only genuinely empirical content is the quadratic growth of the required p, which is a fitted trend rather than a derived prediction.

  2. self citation load bearing [Section V, Discussion and Outlook]
    "While extrapolation beyond the simulated range introduces uncertainty, the interference effect at the core of the non-variational QWOA, as described in [10], relies on statistical assumptions that are increasingly valid for larger problem sizes. This supports the plausibility of the observed scaling persisting for larger problem sizes."

    The only cited basis for expecting the fitted quadratic to persist beyond n=31 is the authors' own prior work [10] (Bennett, Noakes, Wang), i.e., a self-citation. Because [10] is not independently machine-checked or otherwise externally verified here, it cannot carry the extrapolation weight by itself; however, this is presented as 'plausibility' and is not the main benchmark claim, so it is a minor circular-support issue.

full rationale

The defensible circularity is in the presentation of the 'constant measurement probability' result. The blue points in Fig. 4 are defined as iteration counts at which the interpolated mean probability hits the authors' chosen 10% target; Eq. (1) is a quadratic fit to those points. When Fig. 5 is then drawn with p given by Eq. (1) and the paper reports probabilities 'around the target 10%,' that is a self-consistency check, not an independent prediction: the outcome is fixed by the construction of Eq. (1). However, the underlying claim that the required p grows approximately quadratically is genuine empirical content extracted from the simulations, not a tautology. The L-BFGS optimization and linear-interpolation reliability are correctness risks rather than circularity. The extrapolation beyond n=31 leans on the authors' own [10] for plausibility, but it is explicitly hedged and does not drive the central benchmark. Score reflects partial, not total, circularity.

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

The paper contributes benchmarking data on a previously introduced algorithm. The central claims rest on simulation fidelity, representative random instances, successful per-instance parameter optimization, and the validity of the interference theory from the group's own earlier work. No new physical entities are introduced.

free parameters (5)
  • gamma (phase-separation strength) = per instance, not reported
    L-BFGS optimizes gamma along with t and beta to maximize the expected objective (Algorithm 1).
  • t (mixing time) = per instance, not reported
    L-BFGS optimizes t to maximize the expected objective (Algorithm 1).
  • beta (schedule interpolation parameter) = per instance, not reported
    L-BFGS optimizes beta to control the schedule of gamma_k and t_k (Algorithm 1).
  • target measurement probability = 10%
    The 10% threshold is chosen by the authors and defines the entire p(n) curve; all claims of constant probability are relative to this arbitrary target.
  • p(n) quadratic coefficients = a=0.019, b=0.053, c=-0.092
    Eq. (1) is a quadratic fit to the interpolated iteration counts required to reach the 10% target, and is then used to set circuit depth in Figs 5 and 6.
assumptions (6)
  • domain assumption Qiskit Aer noiseless statevector simulation faithfully represents the ideal quantum algorithm.
    All performance numbers come from classical simulation with no noise model; hardware effects are not considered.
  • domain assumption Erdős-Rényi-Gilbert random graphs are representative of average-case weighted maxcut instances.
    The benchmark library is generated from this model, but the edge probability and weight distribution are not specified, so representativeness is assumed.
  • domain assumption L-BFGS with box constraints finds sufficiently optimal parameters for every instance.
    The optimization is heuristic; if it stalls in poor local optima, the estimated required iteration counts p(n) would be biased upward or downward.
  • domain assumption Linear interpolation of mean measurement probabilities accurately estimates the iteration count needed to hit the 10% target.
    The paper uses linear interpolation to define p(n); curvature between sampled p values could change the fitted quadratic.
  • domain assumption Each QWOA iteration has time complexity equivalent to one classical objective function evaluation.
    This equivalence is used to compare 4p quantum function evaluations to local-search evaluations, but it excludes the classical parameter optimization cost.
  • domain assumption The interference mechanism from Bennett et al. [10], which biases amplification toward global optima, remains valid at larger n.
    The paper cites [10] for this mechanism and assumes the observed scaling would persist beyond the simulated range.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Benchmarking Quantum Heuristics: Non-Variational QWOA for Weighted Maxcut." pith.science (2026). https://pith.science/paper/B5H36RNV

@misc{pith2026250524191,
  author       = {Pith},
  title        = {Pith review of: Benchmarking Quantum Heuristics: Non-Variational QWOA for Weighted Maxcut},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/B5H36RNV}},
  note         = {Machine review of arXiv:2505.24191}
}
abstract

We present benchmarking results for the non-variational Quantum Walk Optimisation Algorithm (non-variational QWOA) applied to the weighted maxcut problem, using classical simulations for problem sizes up to $n = 31$. The amplified quantum state, prepared using a quadratic number of alternating unitaries, achieves a constant average-case measurement probability for globally optimal solutions across these problem sizes. This behaviour contrasts with that of classical heuristics, which, for NP-hard optimisation problems, typically exhibit solve probabilities that decay as problem size increases. Performance comparisons with two local-search heuristics on the same benchmark instances suggest that the non-variational QWOA may offer a meaningful advantage by scaling more favourably with problem size. These results provide supporting evidence for the potential of this quantum heuristic to achieve quantum advantage, though further work is needed to assess whether the observed performance scaling persists at larger problem sizes, and to confirm whether similar performance trends are observed for the other problem classes to which the non-variational QWOA is designed to generalise.

Figures

Figures reproduced from arXiv: 2505.24191 by the authors.

Figure 1
Figure 1. FIG. 1. Distributions of the number of local optima for each problem size of the weighted maxcut bench [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. Quantum circuits for (left) the mixing unitary with mixing time [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. The mean measurement probability is shown with black error bars indicating 95% confi [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (4 more)
Figure 3
Figure 3. Figure 3: FIG. 3. Simulation results, indicating typical performance for weighted maxcut problem instances of size [PITH_FULL_IMAGE:figures/full_fig_p008_3.png]
Figure 4
Figure 4. Figure 4: FIG. 4. Estimated number of iterations [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5. Typical performance of the non-variational QWOA applied to weighted maxcut on random graphs. [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6. A performance comparison between the local-search heuristics and the non-variational QWOA. (left) [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

18 extracted references · 15 canonical work pages

  1. [1]

    Abbas, A

    A. Abbas, A. Ambainis, B. Augustino, A. B¨ artschi, H. Buhrman, C. Coffrin, G. Cortiana, V. Dunjko, D. J. Egger, B. G. Elmegreen,et al., Nature Reviews Physics6, 718 (2024)

    work page 2024

  2. [2]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint arXiv:1411.4028 (2014)

    arXiv 2014

  3. [3]

    Marsh and J

    S. Marsh and J. B. Wang, Quantum Information Processing18, 61 (2019)

    work page 2019

  4. [4]

    Hadfield, Z

    S. Hadfield, Z. Wang, B. O’gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, Algorithms12, 34 (2019)

    2019

  5. [5]

    Marsh and J

    S. Marsh and J. B. Wang, Physical Review Research2, 023302 (2020)

    work page 2020

  6. [6]

    Slate, E

    N. Slate, E. Matwiejew, S. Marsh, and J. B. Wang, Quantum5, 513 (2021). 14

    work page 2021

  7. [7]

    Bennett, E

    T. Bennett, E. Matwiejew, S. Marsh, and J. B. Wang, Frontiers in Physics9, 730856 (2021)

    work page 2021

  8. [8]

    Manouchehri and J

    K. Manouchehri and J. B. Wang,Physical implementation of quantum walks(Springer, 2014)

    work page 2014

Show all 18 references
  1. [9]

    Bennett, L

    T. Bennett, L. Noakes, and J. Wang, inarXiv:2404.03167 and 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 1 (IEEE, 2024) pp. 31–41

    2024 arXiv

  2. [10]

    Bennett, L

    T. Bennett, L. Noakes, and J. B. Wang, arXiv preprint arXiv:2408.06368 (2024)

    2024 arXiv

  3. [11]

    Bittel and M

    L. Bittel and M. Kliesch, Physical Review Letters127, 120502 (2021)

    2021

  4. [12]

    Larocca, S

    M. Larocca, S. Thanasilp, S. Wang, K. Sharma, J. Biamonte, P. J. Coles, L. Cincio, J. R. McClean, Z. Holmes, and M. Cerezo, arXiv preprint arXiv:2405.00781 (2024)

    2024 arXiv

  5. [13]

    H. R. Louren¸ co, O. C. Martin, and T. St¨ utzle, inHandbook of Metaheuristics(Springer, 2003) pp. 320–353

    2003

  6. [14]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi, science220, 671 (1983)

    1983

  7. [15]

    Glover and M

    F. Glover and M. Laguna,Tabu search(Springer, 1998)

    1998

  8. [16]

    Beheshti and S

    Z. Beheshti and S. M. H. Shamsuddin, Int. J. Adv. Soft Comput. Appl5, 1 (2013)

    2013

  9. [17]

    Pawsey Supercomputing Research Centre, Setonix supercomputer,https://doi.org/10.48569/ 18sb-8s43(2023), perth, Western Australia

    2023

  10. [18]

    Benlic and J.-K

    U. Benlic and J.-K. Hao, Engineering Applications of Artificial Intelligence26, 1162 (2013)

    2013

Pith tools

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