Pith. sign in

REVIEW 5 major objections 6 minor 61 references

Zero-shot transfer of equivariant quantum policies from 5- to 10-city TSPs works in exact simulation but is obstructed by finite-shot execution and hardware noise, raising the transfer gap from ~5% to 31.3% and then 45.3%.

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-08-04 09:33 UTC pith:C2XC2HZ6

load-bearing objection The abstract and the supplied full text are two different papers; the body's transfer bound is a real idea but rests on an assumption its own training loop violates. the 5 major comments →

arxiv 2510.14533 v2 pith:C2XC2HZ6 submitted 2025-10-16 quant-ph

Diagnosing Simulation and Hardware Barriers to Cross-Size Transfer in Equivariant Quantum Reinforcement Learning

Monit Sharma , Hoong Chuin Lau This is my paper
classification quant-ph PACS 03.67.-a
keywords equivariant quantum circuitsquantum reinforcement learningzero-shot transfertraveling salesman problemfinite-shot noisehardware noisegeneralization boundcombinatorial 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 asks whether quantum reinforcement-learning policies built from equivariant quantum circuits and trained on small traveling-salesman instances can be reused on larger instances without retraining. In exact simulation, within the validated regime, the answer is yes: zero-shot transfer from five to ten cities beats training directly on the target size in all six evaluations. The central result, however, is that the transfer is systematically obstructed under realistic execution. Finite sampling noise alone widens the performance gap from about 5% to 31.3%, and running on trapped-ion hardware widens it to 45.3%, because the policy's action margins fall below the shot-noise floor and collapse roughly as n^{-2.1}. The paper claims no quantum advantage; it offers a diagnostic standard that future cross-size transfer claims should meet.

Core claim

The paper's central claim is that zero-shot cross-size transfer of equivariant quantum circuit policies works in exact state-vector simulation but fails to survive finite-shot execution and hardware noise. The transfer gap grows from roughly 5% in simulation to 31.3% under sampling noise alone and to 45.3% on hardware, because the action-choice margins of the trained policy lie below the shot-noise floor and decay as n^{-2.1}. A cross-platform campaign across four hardware vendors shows the hardware penalty is set by native two-qubit gate count and error-mitigation overhead, not by shot budget. The paper also derives a theoretical performance bound separating source generalization error from

What carries the argument

The carrying object is the equivariant quantum circuit (EQC), a parameterized circuit whose layers are generated by permutation-averaged operators (for example, sums like (1/k)Σ_j X_j and (2/k(k-1))Σ_{j<k} Z_jZ_k), so the same trained parameters can be plugged into a larger k-qubit circuit without changing the parameter count. The theoretical workhorse is the decomposition P_m(θ*_n) ≥ P̂_n − G_n(δ) − D_{n→m}: G_n is the finite-sample generalization error on the source size, and D_{n→m} bounds the transfer penalty from scaled generators plus structural task shift. The empirical workhorse is the shot-noise floor: actions are chosen from probabilities estimated with finitely many measurements,

Load-bearing premise

The entire bound rests on the assumption that the small-instance training episodes are independent draws from a fixed distribution (or mix quickly enough for statistical generalization bounds to apply); if the agent is trained online on a single instance with an evolving policy, the generalization term G_n(δ) is not the quantity the bound needs it to be.

What would settle it

Run the same transferred EQC checkpoint on TSP sizes n=4..10 under exact state-vector simulation and under finite-shot execution with, say, 10^3 and 10^4 shots each. The paper predicts the action margin (probability gap between the top-two choices) falls below the 1/√K shot-noise floor and scales as n^{-2.1}, and that the transfer gap jumps from ~5% to ~31%. Observing margins well above the shot-noise floor, an exponent clearly different from -2.1, or a transfer gap that shrinks substantially with more shots would overturn the finite-shot barrier and thus the paper's main empirical claim.

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

If this is right

  • Zero-shot transfer of EQC policies across TSP sizes is only trustworthy under exact simulation; with finite measurement shots, a transfer gap floor is set by shot noise, and no amount of additional training on the source size removes it.
  • The n^{-2.1} collapse of action margins means the obstruction worsens as target size grows, so scaling claims need to report margin-versus-shot statistics, not just average tour quality.
  • The hardware penalty tracks native two-qubit gate count and error-mitigation overhead; reducing that penalty means compiling EQC layers to fewer native two-qubit gates rather than increasing the shot budget.
  • The bound P_m(θ*_n) ≥ P̂_n − G_n(δ) − D_{n→m} gives a diagnosis: a transfer failure can be apportioned between source-side generalization error, generator/parameter mismatch, and structural task shift, and each component points to a different remedy (more episodes, smaller size jumps, fine-tuning).
  • If the central claims hold, the paper's measurement protocol becomes the standard by which future claims of cross-size quantum transfer should be judged.

Where Pith is reading between the lines

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

  • Editorial extension: the same shot-noise obstruction should appear in any equivariant quantum policy whose action distribution concentrates with problem size, not just TSP; the n^{-2.1} exponent is a measurable quantity that could be reported alongside approximation-ratio curves for other combinatorial problems.
  • Editorial extension: the margin-collapse diagnostic could be used predictively—measuring action margins at a small source size and extrapolating the transfer gap to a target size and shot budget before running hardware, which would tell a practitioner whether fine-tuning or error mitigation is worth doing.
  • Editorial extension: because the hardware penalty tracks native two-qubit gate count, an architecture search over EQC generator orderings or a compilation pass aimed at minimizing two-qubit gates might restore a large fraction of the lost transfer; the paper stops at diagnosing the obstacle rather than testing that fix.

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

5 major / 6 minor

Summary. The paper proposes a theoretical framework for zero-shot cross-size transfer of equivariant quantum circuits (EQCs) used as reinforcement-learning policies for the Traveling Salesman Problem. It derives a lower bound P_m(θ*_n) ≥ P̂_n(θ*_n) − G_n(δ) − D_{n→m}, where G_n is a source-task generalization term adapted from Schatzki et al. and D_{n→m} is a task-dissimilarity penalty decomposed into a parametric-mismatch term and a structural term based on the Beardwood–Halton–Hammersley theorem. Empirically, the body reports state-vector simulations on 4- to 15-city Euclidean TSPs, comparing a permutation-equivariant circuit against an Efficient SU(2) circuit and claiming that the equivariant architecture transfers better and that fine-tuning improves performance. The arXiv abstract, however, claims additional results: finite-shot execution inflates the transfer gap from ~5% to 31.3% from sampling noise and to 45.3% on hardware, action margins collapse as n^{-2.1}, a four-vendor hardware campaign was performed, and MPS bond-dimension truncation destroys policy quality. None of these abstract-level claims appear in the supplied full text.

Significance. If the abstract's claims were supported, the paper would provide a valuable diagnostic standard for evaluating whether equivariant QRL policies retain cross-size transfer under realistic execution, with quantitative finite-shot and hardware penalties. The theoretical decomposition into a generalization term and a transfer-penalty term is a useful conceptual contribution, and extending permutation-equivariant QML generalization bounds to a cross-size transfer setting is a reasonable research direction. However, the significance as presented is substantially undermined: the quantitative empirical claims in the abstract are not present in the body, and the central theorem relies on assumptions that are not satisfied by the described training protocol and on constants that are fitted to the same data used for validation. The manuscript does not ship code or datasets, so the claimed empirical results are not independently checkable.

major comments (5)
  1. [Abstract vs. §5] The abstract states that finite-shot execution inflates the transfer gap from ~5% to 31.3% (sampling noise) and 45.3% (hardware), that action margins collapse as n^{-2.1}, that a four-vendor hardware campaign confirms the penalty is set by native two-qubit gate count, and that MPS bond-dimension truncation destroys policy quality. Section 5.1 describes only state-vector simulation on graphs with n∈{4,6,8,10,12,15}; no finite-shot execution, no hardware runs, no MPS results, and no shot-count analysis appear anywhere in the supplied full text. These are the central quantitative claims of the abstract, and they are unsupported by the manuscript body.
  2. [Appendix C, Assumption (A2); Theorem 1] Theorem 1's G_n(δ) is inherited from Schatzki et al.'s supervised generalization theorem, but the manuscript does not establish that the QRL training loop satisfies any of the three regimes in (A2). Section 5.1 trains on graphs with epsilon decay and online updates; episodes are not fresh i.i.d. instances from a fixed exploratory policy, and the finite-pool replay option is not described in the experiments. Option (A2-iii) would require an estimate of the mixing time τ_β, and none is provided. Since G_n is the only term separating empirical from true source performance, the lower bound in Theorem 1 has no proven foundation for the actual training procedure.
  3. [Appendix G.1.1, G.1.2; Figure 3; §5.3] The validation of the theoretical bound is circular. The coefficient of the parametric term is consolidated into an empirically measured strength α_n 'for a given source model' (G.1.1), and the structural constant C' is estimated from the experimental normalization constants (G.1.2). Figure 3 then shows data lying above a bound that uses these fitted constants. A bound whose constants are fitted to the data it purports to validate does not provide independent evidence for the bound; this is a load-bearing issue because the empirical validation is the main support for the transfer-penalty decomposition.
  4. [Assumption (A6)/(A7-4); Appendix C, Appendix E] The structural term D_{n→m}^{(struct)} ≤ C'(m−n)/√n is used as a deterministic-looking bound, but the text itself states that the Beardwood–Halton–Hammersley theorem makes no formal statement for finite k and that the non-asymptotic bound is 'conjectured' (Appendix C, A6). The derivation in Appendix E then treats this conjecture as an established inequality. For the small sizes n,m∈{4,...,15} used in the experiments, asymptotic BHH scaling is not a demonstrated guarantee, and the affine rescaling with fixed L_max and L_opt introduces additional finite-size issues. This makes the structural component of D_{n→m} unproven.
  5. [§5.2; Figure 2] The body claims that zero-shot transfer beats target-size training in 'all six evaluations' per the abstract, but the results section does not report quantitative comparisons against the 'Training from Scratch' baseline. It shows equivariant vs. Efficient SU(2) tour costs and mentions a classical baseline, but there is no table or plot of scratch-trained target-size policies. The stated advantage over target-size training is therefore not supported by the reported data.
minor comments (6)
  1. [§3.4] The definition of G_n(δ) uses the notation T_en+1 without redefining it; it is earlier defined in Appendix A as T_en+1 = \binom{n+3}{3}. Also the displayed formula has a formatting artifact ('s' before the square-root terms) that should be corrected.
  2. [Appendix A.3] The subsection title 'Prook Sketch' is a typo for 'Proof Sketch.'
  3. [§5.2, Figure 2] Figure 2 is described as comparing transfer performance, but the caption lacks axis labels, units, and error-bar definitions; the classical baseline is referred to as 'e.g., a greedy or MST-based solver' without specifying which one.
  4. [§1, Contributions] The contribution list says 'zero-shot five-to-ten-city transfer beats target-size training in all six evaluations,' but this claim is not in the body's experimental section and should be either stated with data or removed.
  5. [§6.1] The limitation paragraph correctly admits that the constants in D_{n→m} 'remain abstract,' but this conflicts with the stronger validation language in §5.3; the authors should reconcile these statements.
  6. [References] Reference [9] is a preprint by the same authors on capacitated vehicle routing that is not cited in the text; please check whether it is needed.

Circularity Check

1 steps flagged

The Figure 3 'theoretical' lower bound is operationalized with an empirically fitted α_n, so the claimed validation reduces to the fit; the separate A2 i.i.d. mapping issue is a validity risk, not the circularity driving this score.

specific steps
  1. fitted input called prediction [Appendix G.1.1 (Estimating the Unitary Lipschitz Constant L_U) and Section 5.3 / Figure 3]
    "Rather than relying on potentially loose worst-case estimates for these individual constants, we consolidate them into a single, effective scaling factor, αn, for each source model size n. This allows us to construct a tight and illustrative bound that retains the theoretically-derived structure, while pragmatically accounting for the difficulty in calculating the precise value of the overall coefficient. This αn is therefore best understood as the empirically measured strength of the parametric penalty for a given source model."

    Theorem 1's displayed bound is P_m(θ*_n) ≥ P̂_n − G_n(δ) − D_{n→m}, where D_{n→m} = L_U ∥θ*_n∥_1 e^{θmax∥A∥_op} 2∥A∥_op (m−n)/m + C′(m−n)/√n. Rather than computing L_U, ∥A∥_op, θmax, and C′ from first principles, G.1.1 folds them into α_n, described as the 'empirically measured strength of the parametric penalty for a given source model.' Section 5.3 then uses that curve to announce that the zero-shot points 'never enter the theoretically excluded region' and calls this 'strong evidence for the correctness of the derived bound.' Once the excluded-region boundary is set by an empirical coefficient estimated for the same source model, the inequality is satisfied by construction; the 'prediction' is a fit to the measurements it is used to validate.

full rationale

The central defect is confined to the validation claim for the transfer bound. The symbolic derivation of D_{n→m} (Appendix E) is not circular: it bounds generator mismatch via Lipschitz/unitary inequalities and structural shift via BHH asymptotics. However, the empirical confirmation in Figure 3 is circular in the mild sense of a fitted input called a prediction: the paper's own G.1.1 consolidates the unknown constants into a per-source-size α_n that is 'empirically measured,' and the bound is then overlaid on the same zero-shot data. A lower envelope with a fitted coefficient is not a falsifiable prediction; the paper itself concedes in Section 6.1 that 'the precise functional form and magnitude of the constants within the transfer penalty term Dn→m remain abstract.' Separately, the mapping of Schatzki et al.'s i.i.d. supervised generalization theorem to the QRL loop via assumption (A2-i)/(A2-ii) is not established for the online, epsilon-decay training described in Section 5.1, and option (A2-iii) invokes an unestimated mixing time τβ. That is a correctness or validity risk, not an input-output circularity, so I do not weight it into the circularity score. There is no load-bearing self-citation: reference [9] is tangential, and the main external basis, Schatzki et al. [18], is independent of the authors. Overall, the paper has substantial non-circular empirical content (zero-shot transfer results against baselines), but its advertised theoretical validation of the bound reduces by construction, giving a partial-circularity score of 6 rather than 0.

Axiom & Free-Parameter Ledger

2 free parameters · 4 axioms · 0 invented entities

No new physical entities are introduced. D_{n→m} is a mathematical construct combining parametric and structural penalties, not an entity with independent evidence requirements.

free parameters (2)
  • α_n (effective parametric penalty coefficient) = not reported (fitted per source size n)
    Appendix G.1.1 consolidates L_U, ∥A∥_op, ∥θ*_n∥_1, and θ_max-dependent factors into a single per-source-size factor α_n and calls it 'empirically measured strength'; it is used to draw the theoretical lower bound in Figure 3.
  • C′ (structural dissimilarity constant) = ≈ β2 / (2(L_max − L_opt)), β2≈0.712
    Appendix G.1.2 estimates C′ from the BHH constant and from empirical normalization constants L_max, L_opt; the non-asymptotic form |P_opt_n − P_opt_m| ≤ C′(m−n)/√n is conjectured in Appendix C (A6).
axioms (4)
  • domain assumption Theorem 4 of Schatzki et al. (2024): Sn-equivariant QNN generalization bound with G_n = O(√((T_{n+1}+1)/M) + √(log(1/δ)/M)).
    The transfer bound inherits this result; Appendix A states it as given. If the source-task training is not i.i.d. or the QNN is not Sn-equivariant, the bound may not apply.
  • domain assumption A2: episodic returns (or per-instance averages) are i.i.d., or β-mixing with known mixing time τβ.
    Appendix C (A2-i/ii/iii) maps supervised generalization to QRL; online Q-learning with policy updates violates the i.i.d. condition and leaves τβ unestimated.
  • domain assumption A5: reusing θ*_n with scaled generators (1/m)∑O_j preserves S_m-equivariance and makes the target circuit compatible with the source parameters.
    Appendix C (A5) is described as playing a 'particularly critical role'; if the generator scaling does not preserve the symmetry or alignment, D_{n→m} is not an upper bound on transfer loss.
  • ad hoc to paper A6 / A7-4: |P_opt_n − P_opt_m| ≤ C′(m−n)/√n for finite n,m (non-asymptotic smoothness conjectured from BHH).
    Appendix C calls this a conjecture based on a 'heuristic first-order approximation' of the BHH asymptotic; it is then used as a rigorous bound in Theorem 1 and D_{n→m}.

pith-pipeline@v1.3.0-alltime-deepseek · 24758 in / 15601 out tokens · 117612 ms · 2026-08-04T09:33:44.992453+00:00 · methodology

0 comments
read the original abstract

Equivariant quantum circuits (EQCs) parameterise reinforcement-learning policies for combinatorial optimisation with a size-independent parameter count, suggesting policies trained on small instances may transfer to larger ones. Whether such transfer survives realistic execution has not been measured end-to-end. We train EQC policies on Euclidean Travelling Salesman instances and evaluate identical checkpoints across statevector simulation, matrix-product-state simulation, noisy simulation, a protocol-matched noiseless emulator, and trapped-ion hardware. Within the validated regime, zero-shot five-to-ten-city transfer beats target-size training in all six evaluations. Beyond it, three barriers emerge: bond-dimension truncation destroys policy quality even without transfer; larger size jumps degrade performance consistently with a conditional diagnostic bound; and finite-shot execution inflates the transfer gap from ${\sim}5\%$ to $31.3\%$ (sampling noise alone) to $45.3\%$ hardware), because action margins lie below the shot-noise floor and collapse as $n^{-2.1}$. A cross-platform campaign across four hardware vendors confirms the penalty is set by native two-qubit gate count and error mitigation, not shot budget. A shot-complexity bound formalises the obstruction. We claim no quantum advantage; we provide the diagnostic standard such claims should meet.

Figures

Figures reproduced from arXiv: 2510.14533 by Hoong Chuin LAU, Monit Sharma.

Figure 1
Figure 1. Figure 1: Comparison of circuit architectures used in this study. (a) EQC uses globally entangling [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of transfer performance: Permutation Equivariant (left column) vs. Efficient SU(2) (right column) 10 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Empirical Validation of the Theoretical Transfer Performance Bound. Each panel shows the performance [PITH_FULL_IMAGE:figures/full_fig_p012_3.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

61 extracted references · 2 canonical work pages

  1. [1]

    The traveling-salesman problem.Operations research, 4(1):61–75, 1956

    Merrill M Flood. The traveling-salesman problem.Operations research, 4(1):61–75, 1956. 1

    1956

  2. [2]

    Princeton university press, 2006

    David L Applegate.The traveling salesman problem: a computational study, volume 17. Princeton university press, 2006. 1

    2006

  3. [3]

    Princeton university press, 2015

    William J Cook.In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton university press, 2015. 1

    2015

  4. [4]

    Computers and intractability: a guide to the theory of np-completeness (michael r

    Juris Hartmanis. Computers and intractability: a guide to the theory of np-completeness (michael r. garey and david s. johnson).Siam Review, 24(1):90, 1982. 1

    1982

  5. [5]

    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. InProceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS), pages 2–11,

  6. [6]

    Reinforcement learning for combinatorial optimization: A survey.Computers & Operations Research, 134:105400, 2021

    Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey.Computers & Operations Research, 134:105400, 2021. 1

    2021

  7. [7]

    Ant-q: A reinforcement learning approach to the traveling salesman problem

    Luca M Gambardella and Marco Dorigo. Ant-q: A reinforcement learning approach to the traveling salesman problem. InMachine learning proceedings 1995, pages 252–260. Elsevier, 1995. 1

    1995

  8. [8]

    Combining reinforcement learning with lin-kernighan-helsgaun algorithm for the traveling salesman problem

    Jiongzhi Zheng, Kun He, Jianrong Zhou, Yan Jin, and Chu-Min Li. Combining reinforcement learning with lin-kernighan-helsgaun algorithm for the traveling salesman problem. InProceedings of the AAAI conference on artificial intelligence, volume 35, pages 12445–12452, 2021. 1

    2021

  9. [9]

    Hybrid learning and optimization methods for solving capacitated vehicle routing problem.arXiv preprint arXiv:2509.15262, 2025

    Monit Sharma and Hoong Chuin Lau. Hybrid learning and optimization methods for solving capacitated vehicle routing problem.arXiv preprint arXiv:2509.15262, 2025

    arXiv 2025

  10. [10]

    Vedran Dunjko and Hans J. Briegel. Machine learning & artificial intelligence in the quantum domain: a review of recent progress.Reports on Progress in Physics, 81(7):074001, 2018. URL https://arxiv.org/abs/1709. 02779. 1

    2018

  11. [11]

    Robustness of quantum reinforcement learning under hardware errors.EPJ Quantum Technology, 10(1):1–43, 2023

    Andrea Skolik, Stefano Mangini, Thomas Bäck, Chiara Macchiavello, and Vedran Dunjko. Robustness of quantum reinforcement learning under hardware errors.EPJ Quantum Technology, 10(1):1–43, 2023. 1, 2, 3

    2023

  12. [12]

    Equivariant quantum circuits for learning on weighted graphs.npj Quantum Information, 9(1):47, 2023

    Andrea Skolik, Michele Cattelan, Sheir Yarkoni, Thomas Bäck, and Vedran Dunjko. Equivariant quantum circuits for learning on weighted graphs.npj Quantum Information, 9(1):47, 2023. 1, 2, 3

    2023

  13. [13]

    Improving generalization of deep reinforcement learning-based tsp solvers via equivariance and local search

    Wenbin Ouyang, Yisen Wang, Shuai Han, Zhi Jin, and Peng Wei Weng. Improving generalization of deep reinforcement learning-based tsp solvers via equivariance and local search. InIEEE Symposium Series on Computational Intelligence (SSCI), pages 01–08, 2021. URLhttps://arxiv.org/abs/2110.02843. 2

    Pith/arXiv arXiv 2021

  14. [14]

    Generalize a small pre-trained model to arbitrarily large tsp instances, 2021

    Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances, 2021. URLhttps://arxiv.org/abs/2012.10658. 2, 3

    Pith/arXiv arXiv 2021

  15. [16]

    Lotshaw, Jeffrey Larson, James Ostrowski, and Travis S

    Ruslan Shaydulin, Phillip C. Lotshaw, Jeffrey Larson, James Ostrowski, and Travis S. Humble. Parameter transfer for quantum approximate optimization of weighted maxcut.ACM Transactions on Quantum Computing, 4(3): 1–15, April 2023. ISSN 2643-6817. doi: 10.1145/3584706. URL http://dx.doi.org/10.1145/3584706. 2, 4

    doi:10.1145/3584706 2023

  16. [17]

    Caro, Hsin-Yuan Huang, Marco Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick J

    Matthias C. Caro, Hsin-Yuan Huang, Marco Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick J. Coles. Generalization in quantum machine learning from few training data.Nature Communications, 13 (1):4919, 2022. URLhttps://www.nature.com/articles/s41467-022-32550-3. 2

    2022

  17. [18]

    Theoretical guarantees for permutation-equivariant quantum neural networks.npj Quantum Information, 10(1):12, 2024

    Louis Schatzki, Martín Larocca, Quynh T Nguyen, Frédéric Sauvage, and M Cerezo. Theoretical guarantees for permutation-equivariant quantum neural networks.npj Quantum Information, 10(1):12, 2024. doi: 10.1038/ s41534-024-00804-1. 2, 3, 4, 5, 6, 17, 18, 19, 21, 25 14

    2024

  18. [19]

    Generalization in quantum machine learning: A quantum information standpoint.PRX Quantum, 2(4):040321, 2021

    Leonardo Banchi, Jason Pereira, and Stefano Pirandola. Generalization in quantum machine learning: A quantum information standpoint.PRX Quantum, 2(4):040321, 2021

    2021

  19. [20]

    Understanding quantum machine learning also requires rethinking generalization.Nature Communications, 15(1):2277, 2024

    Elies Gil-Fuster, Jens Eisert, and Carlos Bravo-Prieto. Understanding quantum machine learning also requires rethinking generalization.Nature Communications, 15(1):2277, 2024. 2

    2024

  20. [21]

    Generalization in deep rl for tsp problems via equivariance and local search.SN Computer Science, 5(4):369, 2024

    Wenbin Ouyang, Yisen Wang, Paul Weng, and Shaochen Han. Generalization in deep rl for tsp problems via equivariance and local search.SN Computer Science, 5(4):369, 2024. ISSN 2661-8907. doi: 10.1007/ s42979-024-02689-5. URLhttps://doi.org/10.1007/s42979-024-02689-5. 3

    work page doi:10.1007/s42979-024-02689-5 2024

  21. [22]

    The traveling salesman problem: a case study.Local search in combinatorial optimization, pages 215–310, 1997

    David S Johnson and Lyle A McGeoch. The traveling salesman problem: a case study.Local search in combinatorial optimization, pages 215–310, 1997. 3

    1997

  22. [23]

    Worst-case analysis of a new heuristic for the travelling salesman problem

    Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. InOperations Research Forum, volume 3, page 20. Springer, 2022. 3

    2022

  23. [24]

    A generalized insertion heuristic for the traveling salesman problem with time windows.Operations Research, 46(3):330–335, 1998

    Michel Gendreau, Alain Hertz, Gilbert Laporte, and Mihnea Stan. A generalized insertion heuristic for the traveling salesman problem with time windows.Operations Research, 46(3):330–335, 1998. 3

    1998

  24. [25]

    An effective heuristic algorithm for the traveling-salesman problem.Operations research, 21(2):498–516, 1973

    Shen Lin and Brian W Kernighan. An effective heuristic algorithm for the traveling-salesman problem.Operations research, 21(2):498–516, 1973. 3

    1973

  25. [26]

    Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent

    Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning tsp requires rethinking generalization. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi: 10.4230/LIPICS.CP. 2021.33. URLhttps://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.33. 3

    work page doi:10.4230/lipics.cp 2021

  26. [27]

    Learning-based tsp-solvers tend to be overly greedy, 2025

    Xiayang Li and Shihua Zhang. Learning-based tsp-solvers tend to be overly greedy, 2025. URL https: //arxiv.org/abs/2502.00767. 3

    Pith/arXiv arXiv 2025

  27. [28]

    The shortest path through many points

    Jillian Beardwood, John H Halton, and John Michael Hammersley. The shortest path through many points. InMathematical proceedings of the Cambridge philosophical society, volume 55, pages 299–327. Cambridge University Press, 1959. 3, 19, 20, 23, 26

    1959

  28. [29]

    Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems.Journal of the ACM (JACM), 45(5):753–782, 1998

    Sanjeev Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems.Journal of the ACM (JACM), 45(5):753–782, 1998. 3

    1998

  29. [30]

    Barren plateaus in quantum neural network training landscapes.Nature communications, 9(1):4812, 2018

    Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes.Nature communications, 9(1):4812, 2018. 3

    2018

  30. [31]

    Effect of barren plateaus on gradient-free optimization.Quantum, 5:558, 2021

    Andrew Arrasmith, Marco Cerezo, Piotr Czarnik, Lukasz Cincio, and Patrick J Coles. Effect of barren plateaus on gradient-free optimization.Quantum, 5:558, 2021. 3

    2021

  31. [32]

    Generalization despite overfitting in quantum machine learning models.Quantum, 7:1210, 2023

    Evan Peters and Maria Schuld. Generalization despite overfitting in quantum machine learning models.Quantum, 7:1210, 2023. 3

    2023

  32. [33]

    The power of quantum neural networks.Nature Computational Science, 1(6):403–409, 2021

    Amira Abbas, David Sutter, Christa Zoufal, Aurélien Lucchi, Alessio Figalli, and Stefan Woerner. The power of quantum neural networks.Nature Computational Science, 1(6):403–409, 2021. 3

    2021

  33. [34]

    Equivariant quantum graph circuits, 2022

    Péter Mernyei, Konstantinos Meichanetzidis, and ˙Ismail ˙Ilkan Ceylan. Equivariant quantum graph circuits, 2022. URLhttps://arxiv.org/abs/2112.05261. 3

    Pith/arXiv arXiv 2022

  34. [35]

    Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances, 2018. URLhttps://arxiv.org/abs/1812.04170. 4

    Pith/arXiv arXiv 2018

  35. [36]

    Atia, Sihong He, and Yue Wang

    Chi Zhang, Ziying Jia, George K. Atia, Sihong He, and Yue Wang. Pessimism principle can be effective: Towards a framework for zero-shot transfer reinforcement learning, 2025. URL https://arxiv.org/abs/2505.18447. 4, 21

    Pith/arXiv arXiv 2025

  36. [37]

    On the theory of transfer learning: The importance of task diversity.Advances in neural information processing systems, 33:7852–7862, 2020

    Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity.Advances in neural information processing systems, 33:7852–7862, 2020. 4, 21

    2020

  37. [38]

    Stability bounds for stationary φ-mixing and β-mixing processes

    Mehryar Mohri and Afshin Rostamizadeh. Stability bounds for stationary φ-mixing and β-mixing processes. Journal of Machine Learning Research, 11(2), 2010. 19 15

    2010

  38. [39]

    Generalization bounds for mixing processes via delayed online-to-pac conversions.arXiv preprint arXiv:2406.12600, 2024

    Baptiste Abeles, Eugenio Clerico, and Gergely Neu. Generalization bounds for mixing processes via delayed online-to-pac conversions.arXiv preprint arXiv:2406.12600, 2024. URL https://arxiv.org/abs/2406. 12600. 19

    Pith/arXiv arXiv 2024

  39. [40]

    Cost function dependent barren plateaus in shallow parametrized quantum circuits.Nature communications, 12(1):1791, 2021

    Marco Cerezo, Akira Sone, Tyler V olkoff, Lukasz Cincio, and Patrick J Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits.Nature communications, 12(1):1791, 2021. 19

    2021

  40. [41]

    Connecting ansatz expressibility to gradient magnitudes and barren plateaus.PRX quantum, 3(1):010313, 2022

    Zoë Holmes, Kunal Sharma, Marco Cerezo, and Patrick J Coles. Connecting ansatz expressibility to gradient magnitudes and barren plateaus.PRX quantum, 3(1):010313, 2022. 19

    2022

  41. [42]

    SIAM, 1997

    J Michael Steele.Probability theory and combinatorial optimization. SIAM, 1997. 20

    1997

  42. [43]

    Subadditive euclidean functionals and nonlinear growth in geometric probability.The Annals of Probability, pages 365–376, 1981

    J Michael Steele. Subadditive euclidean functionals and nonlinear growth in geometric probability.The Annals of Probability, pages 365–376, 1981. 20

    1981

  43. [44]

    Concentration of measure and isoperimetric inequalities in product spaces.Publications Mathématiques de l’Institut des Hautes Etudes Scientifiques, 81:73–205, 1995

    Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces.Publications Mathématiques de l’Institut des Hautes Etudes Scientifiques, 81:73–205, 1995. 20

    1995

  44. [45]

    Gradients and frequency profiles of quantum re-uploading models

    Alice Barthe and Adrián Pérez-Salinas. Gradients and frequency profiles of quantum re-uploading models. Quantum, 8:1523, 2024. 20

    2024

  45. [46]

    Robustness and generalization in quantum reinforcement learning via lipschitz regularization.arXiv preprint arXiv:2410.21117, 2024

    Nico Meyer, Julian Berberich, Christopher Mutschler, and Daniel D Scherer. Robustness and generalization in quantum reinforcement learning via lipschitz regularization.arXiv preprint arXiv:2410.21117, 2024. URL https://arxiv.org/abs/2410.21117. 20

    Pith/arXiv arXiv 2024

  46. [47]

    Lipschitz continuity in model-based reinforcement learning

    Kavosh Asadi, Dipendra Misra, and Michael Littman. Lipschitz continuity in model-based reinforcement learning. InInternational Conference on Machine Learning, pages 264–273. PMLR, 2018. 20

    2018

  47. [48]

    Cambridge university press, 2018

    John Watrous.The theory of quantum information. Cambridge university press, 2018. 22

    2018

  48. [49]

    Resource frugal optimizer for quantum machine learning.Quantum Science and Technology, 8(4):045019, 2023

    Charles Moussa, Max Hunter Gordon, Michal Baczyk, Marco Cerezo, Lukasz Cincio, and Patrick J Coles. Resource frugal optimizer for quantum machine learning.Quantum Science and Technology, 8(4):045019, 2023. 26

    2023

  49. [50]

    Training robust and generalizable quantum models.Physical Review Research, 6(4):043326, 2024

    Julian Berberich, Daniel Fink, Daniel Pranji ´c, Christian Tutschku, and Christian Holm. Training robust and generalizable quantum models.Physical Review Research, 6(4):043326, 2024

    2024

  50. [51]

    Learning quantum many-body systems from a few copies.Quantum, 8: 1319, 2024

    Cambyse Rouzé and Daniel Stilck França. Learning quantum many-body systems from a few copies.Quantum, 8: 1319, 2024. 26

    2024

  51. [52]

    New bounds for the traveling salesman constant.Advances in Applied Probability, 47(1): 27–36, 2015

    Stefan Steinerberger. New bounds for the traveling salesman constant.Advances in Applied Probability, 47(1): 27–36, 2015. 26, 27 16 A Context and Foundations Theorem 4 in Schatzki et al. (2024) [ 18] provides a significant theoretical guarantee regarding the generalization capabilities of Sn-equivariant Quantum Neural Networks. Understanding this theorem ...

    2015

  52. [54]

    An Sn- equivariant unitaryU(θ)can be decomposed into a block-diagonal form U(θ) ∼= M λ Imλ ⊗U λ(θ)

    Block-Diagonal Structure:A cornerstone of the argument is the representation theory of Sn. An Sn- equivariant unitaryU(θ)can be decomposed into a block-diagonal form U(θ) ∼= M λ Imλ ⊗U λ(θ). Here, λ labels the irreducible representations (irreps) of Sn that appear in the decomposition of the n-qubit Hilbert space, Imλ is an identity matrix of dimension mλ...

  53. [55]

    The sum P λ d2 λ is precisely the Tetrahedral number Ten+1

    Covering Number Bound:The ϵ-covering number of the set Vn of n-qubit unitary Sn-equivariant QNNs with respect to the operator norm∥ · ∥is bounded as: N(V n,∥ · ∥, ϵ)≤ 6 ϵ 2 P λ d2 λ . The sum P λ d2 λ is precisely the Tetrahedral number Ten+1. This step is crucial: it shows that the “size” of the function class implementable byS n-equivariant QNNs scales ...

  54. [56]

    dissimilarity

    Generalization Bound from Covering Numbers:This polynomial bound on the covering number is then leveraged within standard machine learning theory frameworks that relate covering numbers to generalization error (e.g., based on Rademacher complexity or VC dimension, though directly applied via a result from their reference which uses covering numbers). Smal...

  55. [57]

    This fundamentally alters the problem: • The search space of possible tours grows factorially (from(n−1)!/2to(m−1)!/2)

    Change in Problem Scale and Structure:The most obvious difference is the increase in the number of cities fromntom. This fundamentally alters the problem: • The search space of possible tours grows factorially (from(n−1)!/2to(m−1)!/2). • The geometric or combinatorial structure of optimal (or near-optimal) solutions can change. Features or patterns releva...

  56. [58]

    Parameter Mismatch due to Generator Adaptation:As per Assumption 5 (A5), the parameters θ∗ n were optimized for QNN layers involving n-scaled generators (e.g., H (n) l ). When the same θ∗ n are used with m-scaled generators (e.g.,H (m) l ) for them-city problem, the resulting unitary evolution Um(θ∗ n) = Y l e−iθn,lH (m) l will generally be different from...

  57. [59]

    Sim-to-Real Gap

    Representational Capacity Mismatch:The Sn-equivariant QNN used for the source task has an effective complexity related to Ten+1 ∼n 3. An optimal QRL agent for the m-city TSP might ideally require an Sm-equivariant QNN with complexity related to Tem+1 ∼m 3. Since m > n, Tem+1 > Ten+1. The model trained on n cities, even if its parameters θ∗ n are used with...

  58. [60]

    A maximum allowable bond dimensionχ max is set to control the accuracy–efficiency trade-off

    State Initialization.The initial product state (e.g., |0⟩⊗m) is prepared as an MPS with bond dimension χ= 1 . A maximum allowable bond dimensionχ max is set to control the accuracy–efficiency trade-off

  59. [61]

    MPO Construction.For each EQC layer with unitary Ul =e −iθlHl, the generator Hl is represented as an MPO of constant bond dimension. 3.Gate Application.The unitaryU l is applied to the MPS using one of several standard approaches: • Trotter–Suzuki decomposition:approximate e−iθ P j Oj ≈ Q j e−iθOj , applying local exponentials sequentially with temporary ...

  60. [62]

    The state is truncated back to χmax using Singular Value Decomposition (SVD), discarding small singular values and introducing a controlled approximation error

    Bond-Dimension Truncation.After each gate, the MPS bond dimension increases. The state is truncated back to χmax using Singular Value Decomposition (SVD), discarding small singular values and introducing a controlled approximation error. 5.Iteration.Repeat steps 2–4 for all circuit layers. 6.Measurement.Observables, also represented as MPOs, are computed ...

  61. [1996]

    URLhttps://dl.acm.org/doi/10.1145/290179.290180. 1

    arXiv