Pith. Sign in

REVIEW

Quantum approximate stochastic combinatorial optimisation

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Edric Matwiejew, Paulo E. Santos, Jingbo B. Wang, Ugo Varetto

Quantum Physics · Submitted 16 Oct 2026 · 42 references

Pith's verdict: A genuinely new variational quantum-walk ansatz for two-stage stochastic optimization, clearly presented and honestly evaluated on small instances; the main gap (fjoint vs Jmu) is acknowledged but remains load-bearing for generalization.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 19, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 7 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv ID2610.22876 (version 1)
Pith IDVNBPG3NL, Pith's permanent record of this paper and its review
CitationEdric Matwiejew, Jingbo B. Wang, Paulo E. Santos, Ugo Varetto. "Quantum approximate stochastic combinatorial optimisation." arXiv:2610.22876 (2026). https://pith.science/paper/VNBPG3NL
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

QASCO introduces a variational quantum-walk ansatz that coherently incorporates scenario-dependent recourse to search over first-stage decisions without explicitly evaluating expected minimum recourse costs, and demonstrates on…

The reading

This paper introduces Quantum Approximate Stochastic Combinatorial Optimisation (QASCO), a variational quantum-walk ansatz for two-stage stochastic combinatorial optimisation. It avoids the #P-hard task of explicitly computing expected minimum recourse costs by coherently aggregating scenario-weighted recourse phase information into a quantum walk over first-stage decisions. On stochastic MaxCut instances, QASCO concentrates amplitude on the stochastic-optimal first-stage decisions more consistently than a previous two-stage QAOA construction. Under a query-cost model with sample average approximation of recourse costs, QASCO reaches a globally optimal solution in all 2400 test runs and has the lowest expected query cost in all eight tested settings against uniform enumeration, greedy, and tabu search. The ansatz can be calibrated using a depth-independent number of parameters and applied to unseen instances without per-instance optimisation.

What carries the argument

The key machinery is the controlled quantum walk mixer Λ₀(U_W(t)) that applies a continuous-time quantum walk on the first-stage register only when the scenario and recourse registers are in the |0⟩|0⟩ state. This is enabled by the state preparation unitaries S_YS_Ω that create a scenario–recourse reference state |r_x⟩ = Σ_ω √μ(ω)|ω⟩|s_{x,ω}⟩ for each first-stage decision x. The inverse unitaries collapse the joint state into a component in span{|x⟩|0⟩|0⟩}, on which the walk acts. The net effect is a quantum walk on a partite graph where vertices are first-stage decisions and edge weights are modulated by the overlap of the scenario–recourse reference states, thereby incorporating recourse information into the mixing dynamics.

Extended reading notes

Core claim

The core discovery is that a variational quantum walk can serve as an effective ansatz for two-stage stochastic combinatorial optimisation by embedding the scenario distribution and recourse actions into the quantum registers and using a conditional continuous-time quantum walk that only acts on a flagged reference subspace. After phase encoding of both first-stage and recourse costs, the inverse preparation unitaries collapse the scenario-recourse register into a reference state per first-stage decision, condensing the full joint state into a single amplitude per decision. The walk then transfers amplitude between these aggregated amplitudes, effectively searching the first-stage space using recourse-informed dynamics without externally evaluating any expected value. On stochastic MaxCut, this mechanism consistently amplifies the stochastic optimum over the nominal optimum, reversing the preference observed in the two-stage QAOA baseline.

Load-bearing premise

The ansatz minimises the joint expectation f_joint (first-stage cost plus recourse cost averaged over the ansatz distribution), but the true stochastic objective J_μ combines the first-stage cost with the expected minimum recourse cost under the target scenario distribution; the paper acknowledges that minimising f_joint does not guarantee concentration on decisions that minimise J_μ, and the numerical success relies on an empirical correlation that could fail for other problem structures.

Editorial extensions

If this is right

  • QASCO provides a general framework for stochastic optimisation with recourse that can be combined with existing QAOA or QWOA mixers for constrained first-stage spaces, potentially extending to vehicle routing, energy systems, and other real-world two-stage problems.
  • The linear-ramp parameterisation enables offline calibration of the ansatz on representative instances, so the same schedule can be applied to new instances without per-instance variational optimisation, dramatically reducing classical overhead.
  • By avoiding explicit evaluation of expected minimum recourse costs, QASCO offers a potential quantum speedup for a class of #P-hard stochastic optimisation problems, if the required circuit depths become feasible on future devices.
  • The query-cost model results suggest that even at modest system sizes (6–8 vertices), QASCO’s coherent aggregation strategy provides a tangible advantage over simple classical heuristics that require many SAA evaluations.
  • The authors note that the approach is not guaranteed to work when the joint objective f_joint and the true stochastic objective J_μ diverge, motivating analytical study of the regimes where the correlation holds.

Reading between the lines

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

  • Because QASCO optimises the joint expectation f_joint rather than the true stochastic objective J_μ, its practical success depends on an empirical alignment between these two quantities. Future work could characterise problem classes where this alignment breaks down, for instance when the minimum recourse cost differs sharply from the average recourse cost under the prepared reference state.
  • The circuit depth is dominated by repeated recourse-oracle evaluations, which scale as O(|E|(b+log|E|)) per layer. For dense graphs or high-precision weights, this may exceed NISQ-era resources, but the polynomial scaling is encouraging for fault-tolerant implementations.
  • The ability to transfer calibrated parameters across instances without re-optimisation mirrors classical machine-learning-based heuristics and suggests that QASCO could be trained on problem distributions and then deployed, amortising the quantum resource cost.
  • The comparison with classical methods uses a query-cost model that counts cut evaluations. A more complete resource comparison would include the quantum circuit depth and the overhead of multiple shots, but the demonstrated advantage in queries suggests a plausible regime for early quantum advantage.
Original abstract

Two-stage stochastic combinatorial optimisation concerns discrete decisions made before all relevant information is known. An initial decision is made; once uncertainty is resolved, it can be adapted to the realised scenario, at a cost. The aim is to find the initial decision that minimises the upfront cost plus the expected cost of optimal adaptation. The first-stage decision problem is often NP-hard, and computing the expected minimum recourse cost can be $\#\mathrm{P}$-hard for a single first-stage candidate. We introduce Quantum Approximate Stochastic Combinatorial Optimisation (QASCO), a variational quantum-walk ansatz that coherently incorporates scenario-dependent recourse into its dynamics to search over first-stage decisions without explicitly evaluating expected minimum recourse costs. We demonstrate QASCO for MaxCut with stochastic edge weights, obtain a circuit with polynomial per-layer gate complexity, and study the ansatz via exact state-vector simulation. Across the instances considered, QASCO concentrates amplitude more effectively on stochastic-optimal first-stage decisions than a previously proposed two-stage QAOA construction. We further show that the ansatz can be calibrated using a depth-independent number of parameters and applied to unseen instances without further circuit-parameter optimisation, including joint decision--scenario--recourse spaces spanning more than $2^{32}$ configurations. Under a query-cost model, comparison with the tested classical heuristics using sample-average approximations of the expected minimum recourse cost shows that QASCO more reliably reaches globally optimal first-stage solutions while requiring fewer cut evaluations. These results show how to incorporate scenario-dependent recourse into the ansatz dynamics, providing a general framework for variational quantum walks in two-stage stochastic combinatorial optimisation.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-20: 1 request, 7,745 input tokens.

What the abstract itself states, as probabilities: claims first 0.09 · states limitation 0.15 · human participants 0.02 · controlled comparison 0.90 · randomized assignment 0.01 · states quantitative result 0.77 · compares with prior results 0.98 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

Two-stage stochastic combinatorial optimisation concerns discrete decisions made before all relevant information is known. An initial decision is made; once uncertainty is resolved, it can be adapted to the realised scenario, at a cost. The aim is to find the initial decision that minimises the upfront cost plus the expected cost of optimal adaptation. The first-stage decision problem is often NP-hard, and computing the expected minimum recourse cost can be $\#\mathrm{P}$-hard for a single first-stage candidate. We introduce Quantum Approximate Stochastic Combinatorial Optimisation (QASCO), a variational quantum-walk ansatz that coherently incorporates scenario-dependent recourse into its dynamics to search over first-stage decisions without explicitly evaluating expected minimum recourse costs. We demonstrate QASCO for MaxCut with stochastic edge weights, obtain a circuit with polynomial per-layer gate complexity, and study the ansatz via exact state-vector simulation. Across the instances considered, QASCO concentrates amplitude more effectively on stochastic-optimal first-stage decisions than a previously proposed two-stage QAOA construction. We further show that the ansatz can be calibrated using a depth-independent number of parameters and applied to unseen instances without further circuit-parameter optimisation, including joint decision--scenario--recourse spaces spanning more than $2^{32}$ configurations. Under a query-cost model, comparison with the tested classical heuristics using sample-average approximations of the expected minimum recourse cost shows that QASCO more reliably reaches globally optimal first-stage solutions while requiring fewer cut evaluations. These results show how to incorporate scenario-dependent recourse into the ansatz dynamics, providing a general framework for variational quantum walks in two-stage stochastic combinatorial optimisation.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 Two-stage stochastic combinatorial optimisation concerns discrete decisions made before all relevant information is known. background 1.00 0.04 0.02 asserted 0.99
s1 An initial decision is made; once uncertainty is resolved, it can be adapted to the realised scenario, at a cost. background 1.00 0.04 0.02 asserted 0.99
s2 The aim is to find the initial decision that minimises the upfront cost plus the expected cost of optimal adaptation. background 1.00 0.04 0.03 asserted 1.00
s3 The first-stage decision problem is often NP-hard, and computing the expected minimum recourse cost can be $\#\mathrm{P}$-hard for a single first-stage candidate. background 0.93 0.05 0.02 asserted 0.92
s4 We introduce Quantum Approximate Stochastic Combinatorial Optimisation (QASCO), a variational quantum-walk ansatz that coherently incorporates scenario-dependent recourse into its dynamics to search over first-stage decisions without explicitly evaluating expected minimum recourse costs. contribution 0.73 0.94 0.20 asserted 1.00
s5 We demonstrate QASCO for MaxCut with stochastic edge weights, obtain a circuit with polynomial per-layer gate complexity, and study the ansatz via exact state-vector simulation. contribution 0.60 0.97 0.08 asserted 1.00
s6 Across the instances considered, QASCO concentrates amplitude more effectively on stochastic-optimal first-stage decisions than a previously proposed two-stage QAOA construction. result 1.00 0.95 0.20 asserted 1.00
s7 We further show that the ansatz can be calibrated using a depth-independent number of parameters and applied to unseen instances without further circuit-parameter optimisation, including joint decision--scenario--recourse spaces spanning more than $2^{32}$ configurations. result 0.84 0.96 0.15 asserted 1.00
s8 Under a query-cost model, comparison with the tested classical heuristics using sample-average approximations of the expected minimum recourse cost shows that QASCO more reliably reaches globally optimal first-stage solutions while requiring fewer cut evaluations. result 1.00 0.95 0.26 asserted 1.00
s9 These results show how to incorporate scenario-dependent recourse into the ansatz dynamics, providing a general framework for variational quantum walks in two-stage stochastic combinatorial optimisation. interpretation 0.98 0.84 0.77 asserted 1.00

What kind of paper the classifier reports this is: method or tool 1.00 · evidence from simulation or computation 1.00.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. Two-stage stochastic optimisation with recourse. A first-stage decision
Figure 2. Representative six-vertex stochastic MaxCut instance.
Figure 3. Schematic circuit for QASCO. SX prepares the solution register in a uniform state over all first-stage solutions, and SΩ prepares a probability-weighted superposition over the space of scenarios according to the target distribution µ. The recourse register is prepared conditionally on the solution and scenario registers by SY . UC and UQ phase-encode the first-stage and recourse costs, respectively. The adjoint preparation unitaries S † Y and S † Ω aggregate amplitudes associated with the same first-stage choice in a component flagged by |0⟩Ω |0⟩Y . The controlled mixer Λ0(UW ) acts…
Figure 4. Induced partite-graph structure of the controlled mixer with a transverse-field, or hypercube,
Figure 5. QWOA recourse preconditioner SY for stochastic MaxCut. Each of the pR layers applies the modified recourse-phase oracle UQe , followed by transverse-field mixing on Y . The preconditioner parameters (α, β) are optimised first and then held fixed during optimisation of the main ansatz parameters. For pR = 0, the circuit reduces to H⊗n on the recourse register. For the mixing unitary UW (t), we use the transverse-field mixer on X [10]. This choice performs well for the weighted MaxCut problem and is compatible with the three-parameter schedule in Equation (9) [28]. The mixer requires…
Figure 6. shows that the median optimised joint expectation value fjoint decreases at each simulated depth for both ansätze in all three ensembles, with QASCO consistently achiev￾ing lower values by a small margin. At p = 5, the QASCO medians are −10.961, −11.654, and −11.481 for rg = 1, 2, 3, respectively, compared with −10.008, −11.353, and −10.955 for the two-stage QAOA. In
Figure 7. Median first-stage marginal probability Pp(x) by rank under the stochastic objective Jµ and ansatz depth p, where rank one corresponds to the stochastic optimum. Rows are ordered by increasing rank gap rg, with the problem instances in the first row having one solution between the stochastic optimum X∗ µ and the nominal optimum X∗ C , and the second and third rows having two and three such solutions, respectively. 0.0 0.2 0.4 0.6 rg = 1 QASCO rg = 2 QASCO rg = 3 QASCO 0.0 0.2 0.4 0.6 Pp(X * C ) 0.0 0.2 0.4 0.6 rg = 1 two-stage QAOA 0.0 0.2 0.4 0.6 Pp(X * C ) rg = 2 two-stage QAOA…
Figure 8. compares the stochastic- and nominal-optimum probabilities within each in￾stance at p = 5. QASCO assigns more probability to X∗ µ than to X∗ C in 46/50, 49/50, and 50/50 instances for rg = 1, 2, 3, respectively. The corresponding counts for the two-stage QAOA are 16/50, 12/50, and 21/50. The QASCO counts increase across these ensembles, while the two-stage QAOA counts are nonmonotonic in the rank gap. In Appendix B, we further examine the QASCO state in the reference subspace S and its orthogonal complement, together with their contributions to the change in fjoint. Across the three
Figure 9. Mean QASCO first-stage marginal probability by rank under the stochastic objective
Figure 10. , the classical-to-QASCO ERT ratio increases with the size of the first-stage space, consistent with the increasing advantage reported for deterministic MaxCut over similar simple classical heuristics [28]. Classical hit rates also generally improve across this range; one possible explanation is that, as |E| is held constant, the graph becomes sparser, resulting in a simpler first-stage landscape. This trend should therefore not be assumed to persist for the considered classical solvers in general. Across the tested values of m and |E|, QASCO maintains its hit rate and a comparable…
Figure 11. groups the results by expected minimum recourse cost at the stochastic optimum. QASCO has a hit rate of 1.000 in all four groups. Tabu and greedy search also have hit rate 1.000 in the two lowest-cost groups, while uniform enumeration has hit rates 0.989 and 0.946. In the highest-cost group, Q¯∗ µ > 2, hit rates are 0.707 for tabu, 0.650 for greedy, and 0.432 for uniform enumeration. Normalised ERT increases across the 20
Figure 12. Reference-subspace occupation and objective contributions across the three rank-gap ensembles. Left: squared projection norms PR and P⊥ of the final state. Right: cumulative changes ∆Rp and ∆Ip in the reference and interference contributions, where negative values reduce fjoint. Lines show medians over the 150 instances and bands show interquartile ranges. C Calibrated schedule parameters
Figure 13. shows the calibrated ansatz parameters across p = 1, . . . , 8, holding pR at its selected value for each setting. From p = 2 to p = 8, λ decreases monotonically in every 28
Figure 14. examines recourse evaluation cost and required SAA batch sizes for the calibra￾tion and test ensembles used in the candidate-generator benchmark of Section 6.2. For each test instance, we use the benchmark evaluator of Section 5.4 to count the queries for threshold checks at the stochastic optimum, averaged over the scenarios in its five SAA batches. Each query evaluates a cut and tests whether its realised value meets or exceeds the threshold T. This measures per-scenario recourse evaluation cost before reuse of duplicate scenarios, excluding first-stage evaluation and candidate…

Figures reproduced from arXiv:2610.22876 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.