pith. sign in

arxiv: 2606.30415 · v1 · pith:VWRTJ2EWnew · submitted 2026-06-29 · 🪐 quant-ph

Quantum-enhanced Monte Carlo Tree Search framework for combinatorial optimization problems

Yohan Finet , Yves B\'erub\'e-Lauzi\`ere , Victor Drouin-Touchette This is my paper

Pith reviewed 2026-06-30 06:18 UTC · model grok-4.3

classification 🪐 quant-ph
keywords hybrid quantum-classical algorithmMonte Carlo Tree Searchtraveling salesman problemneutral-atom quantum computerscombinatorial optimizationmaximal weighted independent set
0
0 comments X

The pith

A hybrid MCTS algorithm with a neutral-atom quantum subroutine for action selection matches or outperforms classical solvers on TSP instances up to 100 cities.

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

The paper introduces AtomTreeSearch, which embeds a quantum subroutine inside Monte Carlo Tree Search to solve combinatorial problems such as the traveling salesman problem. At each expansion step the quantum processor supplies a maximal weighted independent set of candidate actions that are executed together to create child nodes. Benchmarks show the hybrid method generally matches or beats OR-Tools and simulated annealing on random Euclidean instances up to 60 cities and TSPLIB instances up to 100 cities. The quantum subroutine is reported to generate more diverse and higher-quality branches than the classical alternatives tested. The authors conclude that narrowly scoped quantum components inside classical search frameworks can deliver practical value on present hardware.

Core claim

AtomTreeSearch integrates a quantum subroutine natively implementable on neutral-atom quantum computers within a Monte Carlo Tree Search framework. At each expansion step, a maximal weighted independent set of candidate actions provided by the quantum processor is selected, and these collective actions are performed to obtain a child node. On TSP instances of up to 60 cities on random Euclidean instances and up to 100 cities on TSPLIB instances, the hybrid algorithm generally matches or outperforms both OR-Tools and simulated annealing, and the quantum subroutine produces more diverse and higher-quality branches compared to classical alternate subroutines.

What carries the argument

The quantum subroutine that returns a maximal weighted independent set of candidate actions at each MCTS expansion step.

If this is right

  • The hybrid method reaches competitive performance on standard TSPLIB instances with 100 cities.
  • Quantum-selected branches exhibit higher diversity and quality than the classical subroutines examined.
  • Embedding small quantum subroutines inside classical search trees offers a route to near-term utility for combinatorial optimization.
  • The approach avoids full-problem QUBO formulations that exceed current hardware scale.

Where Pith is reading between the lines

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

  • The same quantum MWIS step could be inserted into other tree-search or branch-and-bound solvers without changing the outer framework.
  • If neutral-atom device sizes increase, the fraction of the search tree handled quantum-mechanically could grow while keeping the classical overhead fixed.
  • Diversity gains from the quantum step may reduce the total number of MCTS simulations needed to reach a target solution quality.

Load-bearing premise

The quantum processor can reliably return a maximal weighted independent set of candidate actions that is both implementable on current neutral-atom hardware and superior in diversity and quality to classical selection methods.

What would settle it

A head-to-head run of the identical MCTS framework on the same TSP instances in which a classical MWIS solver or random selection produces branches of equal or greater diversity and quality, and yields equal or better final solution quality.

Figures

Figures reproduced from arXiv: 2606.30415 by Victor Drouin-Touchette, Yohan Finet, Yves B\'erub\'e-Lauzi\`ere.

Figure 1
Figure 1. Figure 1: Illustration of AtomTreeSearch which consists of a MCTS algorithm where the expansion step selects a maximal weighted independent set of actions provided by a quantum processing unit (QPU) and performs these collective actions to obtain a child node. To formulate a CO problem as a MDP, states are defined to represent candidate solutions, while actions correspond to operations that map one solution to anoth… view at source ↗
Figure 2
Figure 2. Figure 2: Example of 2-Opt operation. Edges (a,c) and (b,d) replace edges (a,b) and (c,d). 3.2 Method Our method first requires an initial solution to the TSP. We use one of the constructive heuristics mentioned above to quickly return one. This initial tour is then considered as an MDP state and is given as the root node of our modified MCTS algorithm. Thus, the initial state provided to Alg. 1 is the initial solut… view at source ↗
Figure 3
Figure 3. Figure 3: (a) Conflict graph G of actions with their associated weights. (b) Embedding of G on a triangular lattice. Atoms are shown in shades of green, with the color intensity proportional to their DMM weights. The green circle surrounding each atom represents its Rydberg blockade radius. (c) The solver pulse. Ω(t) ramps linearly from 0 to Ωmax over t ∈ [0, 0.15T], with a global negative detuning held constant. Du… view at source ↗
Figure 4
Figure 4. Figure 4: Performance of AtomTreeSearch for different parameter settings. The solver runs on 30 TSP instances defined on complete random Euclidean graphs for each combination of parameter values (i.e. there are 30 data points in each box of the box plot). Each row corresponds to a partitioning method. Column a) shows example partitions inducing subgraphs G˜ i  V˜ i , E˜ i  with maxi |V˜ i | ≤ M = 6. Planar graphs … view at source ↗
Figure 5
Figure 5. Figure 5: Performance of our tree search algorithm when using the alternative classical samplers. Each row [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Comparison of the structure of trees generated when using different samplers in our tree search [PITH_FULL_IMAGE:figures/full_fig_p015_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Performance of AtomTreeSearch versus OR-Tools and simulated annealing for different TSP sizes and different densities of the graph underlying the TSP instances. The results are obtained using the KL partitioning method and 24 qubits. The integer linear programming sampler generally yields trees whose average branching factor lies be￾tween those obtained with the greedy and simulated annealing samplers. By … view at source ↗
Figure 8
Figure 8. Figure 8: Performance of AtomTreeSearch compared with OR-Tools and simulated annealing on TSPLIB instances with up to 100 cities. Because AtomTreeSearch and simulated annealing are stochastic algorithms, each solver is run 30 times per instance, resulting in a distribution of optimality gaps, which is summarized using box plots. The left panel shows the performance on individual instances, while the right panel pres… view at source ↗
read the original abstract

Over the past decades, the operations research community has developed numerous effective optimization algorithms, yet quantum computing is emerging as a new computational paradigm with the potential to approach optimization problems more efficiently. Grover's algorithm offers a provable speedup for combinatorial optimization, but its circuit depth places it beyond current noisy intermediate-scale quantum (NISQ) devices. A more accessible alternative is to reformulate the optimization problem as a quadratic unconstrained binary optimization (QUBO) problem and apply quantum annealing; however, practical problem instances remain out of reach for existing hardware. We introduce AtomTreeSearch, a hybrid classical-quantum algorithm that integrates a quantum subroutine natively implementable on neutral-atom quantum computers within a Monte Carlo Tree Search framework. At each expansion step, a maximal weighted independent set of candidate actions provided by the quantum processor is selected, and these collective actions are performed to obtain a child node. We benchmark our method on the Traveling Salesman Problem, with instances of up to 60 cities on random Euclidean instances and up to 100 cities on TSPLIB instances. Our hybrid algorithm generally matches or outperforms both OR-Tools and simulated annealing on these instances, and we find that the quantum subroutine produces more diverse and higher-quality branches compared to classical alternate subroutines. These results suggest that carefully scoped quantum subroutines embedded in classical search frameworks represent a promising path toward near-term quantum utility in combinatorial optimization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 1 minor

Summary. The paper introduces AtomTreeSearch, a hybrid classical-quantum Monte Carlo Tree Search (MCTS) algorithm for combinatorial optimization that embeds a quantum maximal weighted independent set (MWIS) subroutine natively implementable on neutral-atom hardware. At each MCTS expansion step, the quantum processor supplies a set of collective actions; the method is benchmarked on TSP instances (random Euclidean up to 60 cities, TSPLIB up to 100 cities) and claims to match or outperform OR-Tools and simulated annealing while producing more diverse and higher-quality branches than classical subroutines.

Significance. If the reported performance advantage and hardware implementability are rigorously validated with statistical controls and device data, the work would illustrate a concrete route to near-term quantum utility by scoping quantum subroutines inside established classical search frameworks rather than attempting end-to-end quantum optimization. The absence of such validation in the current manuscript, however, leaves the practical significance unestablished.

major comments (3)
  1. [Abstract] Abstract: the central empirical claim that the hybrid algorithm 'generally matches or outperforms both OR-Tools and simulated annealing' is stated without error bars, exact instance counts, statistical tests, or any quantitative comparison tables, rendering the performance advantage unverifiable from the given material.
  2. [Abstract] Abstract: the assertion that 'the quantum subroutine produces more diverse and higher-quality branches compared to classical alternate subroutines' rests on the unverified assumption that neutral-atom hardware can reliably return MWIS solutions for the action sets arising in 60–100 city TSP MCTS expansions; no hardware run data, atom-count scaling, coherence limits, or noise-robustness analysis is supplied.
  3. [Method (implied)] The manuscript provides no implementation details (circuit depth, embedding strategy, or simulator vs. hardware distinction) for the MWIS oracle, which is load-bearing for the claim of native implementability on current neutral-atom devices.
minor comments (1)
  1. [Abstract] The abstract refers to 'random Euclidean instances' and 'TSPLIB instances' without specifying the precise instance sets or generation seeds, which would aid reproducibility.

Simulated Author's Rebuttal

3 responses · 1 unresolved

We thank the referee for the constructive comments, which highlight areas where the manuscript can be strengthened for clarity and rigor. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central empirical claim that the hybrid algorithm 'generally matches or outperforms both OR-Tools and simulated annealing' is stated without error bars, exact instance counts, statistical tests, or any quantitative comparison tables, rendering the performance advantage unverifiable from the given material.

    Authors: We agree that the abstract would benefit from greater quantitative precision. In the revised manuscript we will expand the abstract and add a results table reporting mean performance metrics with standard deviations across runs, the exact number of TSP instances evaluated (random Euclidean and TSPLIB), and the outcomes of statistical significance tests against the OR-Tools and simulated-annealing baselines. revision: yes

  2. Referee: [Abstract] Abstract: the assertion that 'the quantum subroutine produces more diverse and higher-quality branches compared to classical alternate subroutines' rests on the unverified assumption that neutral-atom hardware can reliably return MWIS solutions for the action sets arising in 60–100 city TSP MCTS expansions; no hardware run data, atom-count scaling, coherence limits, or noise-robustness analysis is supplied.

    Authors: The diversity and quality comparisons are obtained from the MWIS solutions generated inside our simulation of the subroutine. We will revise the abstract to make this simulation basis explicit. The claim of native implementability is grounded in the MWIS problem’s known compatibility with Rydberg-atom arrays, but we acknowledge the lack of device-specific validation. A new discussion paragraph will be added outlining hardware considerations, scaling limits, and the distinction between the algorithmic contribution and future experimental work. revision: partial

  3. Referee: [Method (implied)] The manuscript provides no implementation details (circuit depth, embedding strategy, or simulator vs. hardware distinction) for the MWIS oracle, which is load-bearing for the claim of native implementability on current neutral-atom devices.

    Authors: We accept that these details are required. The revised methods section will contain a dedicated subsection describing the MWIS-to-neutral-atom embedding, the pulse-sequence considerations, the classical simulator used to generate the reported benchmark results, and explicit statements that all numerical experiments were performed in simulation rather than on hardware. revision: yes

standing simulated objections not resolved
  • Provision of actual neutral-atom hardware execution data, atom-count scaling curves, coherence-time analysis, or noise-robustness benchmarks for the 60–100 city TSP action sets, as the original study evaluated the framework exclusively through classical simulation of the MWIS oracle.

Circularity Check

0 steps flagged

No circularity; claims rest on external benchmarks against OR-Tools and SA

full rationale

The paper introduces AtomTreeSearch as a hybrid MCTS framework embedding a quantum MWIS subroutine and reports performance via direct comparisons to OR-Tools and simulated annealing on TSP instances up to 100 cities. No equations, derivations, or parameter fittings are described that reduce by construction to the method's own inputs. No self-citation chains, uniqueness theorems, or ansatzes imported from prior author work are invoked to justify core claims. The quantum subroutine's reported diversity/quality gains are presented as empirical observations from the benchmarks rather than tautological redefinitions. This is the standard non-circular case of an algorithmic proposal validated externally.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract supplies no explicit free parameters or invented physical entities. The method rests on the domain assumption that a useful MWIS solution can be obtained from the neutral-atom device at each search step.

axioms (1)
  • domain assumption A maximal weighted independent set of candidate actions can be obtained from the neutral-atom quantum processor and used directly to generate child nodes in MCTS.
    The algorithm description states that this quantum output is selected and performed at each expansion step.

pith-pipeline@v0.9.1-grok · 5791 in / 1308 out tokens · 33649 ms · 2026-06-30T06:18:17.022639+00:00 · methodology

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

122 extracted references · 92 canonical work pages · 5 internal anchors

  1. [1]

    Journal of Statistical Physics 50(1):187--206, ISSN 1572-9613, ://dx.doi.org/10.1007/BF01022991

    Aarts EHL, Korst JHM, van Laarhoven PJM (1988) A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem. Journal of Statistical Physics 50(1):187--206, ISSN 1572-9613, ://dx.doi.org/10.1007/BF01022991

    work page doi:10.1007/bf01022991 1988

  2. [2]

    Nature Reviews Physics 6(12):718--735, ISSN 2522-5820, ://dx.doi.org/10.1038/s42254-024-00770-9

    Abbas A, Ambainis A, Augustino B, B \"a rtschi A, Buhrman H, Coffrin C, Cortiana G, Dunjko V, Egger DJ, Elmegreen BG, Franco N, Fratini F, Fuller B, Gacon J, Gonciulea C, Gribling S, Gupta S, Hadfield S, Heese R, Kircher G, Kleinert T, Koch T, Korpas G, Lenk S, Marecek J, Markov V, Mazzola G, Mensa S, Mohseni N, Nannicini G, O'Meara C, Tapia EP, Pokutta S...

    work page doi:10.1038/s42254-024-00770-9 2024

  3. [3]

    Parallel Computing 10(3):335--338, ISSN 0167-8191, ://dx.doi.org/https://doi.org/10.1016/0167-8191(89)90106-3

    Allwright JR, Carpenter D (1989) A distributed implementation of simulated annealing for the travelling salesman problem. Parallel Computing 10(3):335--338, ISSN 0167-8191, ://dx.doi.org/https://doi.org/10.1016/0167-8191(89)90106-3

    work page doi:10.1016/0167-8191(89)90106-3 1989

  4. [4]

    http://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm, last accessed: 2025-08-13

    Applegate D, Bixby R, Chv \'a tal V, Cook W (2003) Concorde TSP solver, version 03.12.19. http://www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm, last accessed: 2025-08-13

    2003

  5. [5]

    Machine Learning 47(2):235--256, ISSN 1573-0565, ://dx.doi.org/10.1023/A:1013689704352

    Auer P, Cesa-Bianchi N, Fischer P (2002) Finite-time Analysis of the Multiarmed Bandit Problem . Machine Learning 47(2):235--256, ISSN 1573-0565, ://dx.doi.org/10.1023/A:1013689704352

    work page doi:10.1023/a:1013689704352 2002

  6. [6]

    International Journal of Systems Science: Operations & Logistics 10(1):2102265, ://dx.doi.org/10.1080/23302674.2022.2102265

    Barletta C, Garn W, Turner C, Fallah S (2023) Hybrid fleet capacitated vehicle routing problem with flexible Monte–Carlo Tree search . International Journal of Systems Science: Operations & Logistics 10(1):2102265, ://dx.doi.org/10.1080/23302674.2022.2102265

    work page doi:10.1080/23302674.2022.2102265 2023

  7. [7]

    Neural Combinatorial Optimization with Reinforcement Learning

    Bello I, Pham H, Le QV, Norouzi M, Bengio S (2017) Neural Combinatorial Optimization with Reinforcement Learning . ://arxiv.org/abs/1611.09940

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  8. [8]

    ://arxiv.org/abs/1811.06128

    Bengio Y, Lodi A, Prouvost A (2020) Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon . ://arxiv.org/abs/1811.06128

    work page arXiv 2020

  9. [9]

    ORSA Journal on Computing 4(4):387--411, ://dx.doi.org/10.1287/ijoc.4.4.387

    Bentley JJ (1992) Fast Algorithms for Geometric Traveling Salesman Problems . ORSA Journal on Computing 4(4):387--411, ://dx.doi.org/10.1287/ijoc.4.4.387

    work page doi:10.1287/ijoc.4.4.387 1992

  10. [10]

    ://arxiv.org/abs/2510.09813

    Bidzhiev K, Grava S, le Henaff P, Mendizabal M, Merhej E, Quelle A (2025) Efficient Emulation of Neutral Atom Quantum Hardware . ://arxiv.org/abs/2510.09813

    work page arXiv 2025

  11. [11]

    IEEE Transactions on Computational Intelligence and AI in Games 1(1):4--15, ://dx.doi.org/10.1109/TCIAIG.2009.2018702

    Bjornsson Y, Finnsson H (2009) CadiaPlayer: A Simulation-Based General Game Player . IEEE Transactions on Computational Intelligence and AI in Games 1(1):4--15, ://dx.doi.org/10.1109/TCIAIG.2009.2018702

    work page doi:10.1109/tciaig.2009.2018702 2009

  12. [12]

    Zeitschrift f \"u r Physik 51(3):165--180, ISSN 0044-3328, ://dx.doi.org/10.1007/BF01343193

    Born M, Fock V (1928) Beweis des Adiabatensatzes . Zeitschrift f \"u r Physik 51(3):165--180, ISSN 0044-3328, ://dx.doi.org/10.1007/BF01343193

    work page doi:10.1007/bf01343193 1928

  13. [13]

    ://arxiv.org/abs/2311.03294

    Bourreau E, Fleury G, Lacomme P (2023) Indirect Quantum Approximate Optimization Algorithms: application to the TSP . ://arxiv.org/abs/2311.03294

    work page arXiv 2023

  14. [14]

    Nature 317(6040):804--806

    Brady RM (1985) Optimization strategies gleaned from biological evolution. Nature 317(6040):804--806

    1985

  15. [15]

    Brassard, P

    Brassard G, Høyer P, Mosca M, Tapp A (2002) Quantum amplitude amplification and estimation. ://dx.doi.org/10.1090/conm/305/05215

    work page doi:10.1090/conm/305/05215 2002

  16. [16]

    Computational Geometry 9(1):3--24, ISSN 0925-7721, ://dx.doi.org/https://doi.org/10.1016/S0925-7721(97)00014-X, special Issue on Geometric Representations of Graphs

    Breu H, Kirkpatrick DG (1998) Unit disk graph recognition is NP-hard . Computational Geometry 9(1):3--24, ISSN 0925-7721, ://dx.doi.org/https://doi.org/10.1016/S0925-7721(97)00014-X, special Issue on Geometric Representations of Graphs

    work page doi:10.1016/s0925-7721(97)00014-x 1998

  17. [17]

    IEEE Transactions on Computational Intelligence and AI in Games 4(1):1--43, ://dx.doi.org/10.1109/TCIAIG.2012.2186810

    Browne CB, Powley E, Whitehouse D, Lucas SM, Cowling PI, Rohlfshagen P, Tavener S, Perez D, Samothrakis S, Colton S (2012) A Survey of Monte Carlo Tree Search Methods . IEEE Transactions on Computational Intelligence and AI in Games 4(1):1--43, ://dx.doi.org/10.1109/TCIAIG.2012.2186810

    work page doi:10.1109/tciaig.2012.2186810 2012

  18. [18]

    2020 IEEE International Conference on Quantum Computing and Engineering (QCE), 72--82 (Los Alamitos, CA, USA: IEEE Computer Society), ://dx.doi.org/10.1109/QCE49297.2020.00020

    Bärtschi A, Eidenbenz S (2020) Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation . 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), 72--82 (Los Alamitos, CA, USA: IEEE Computer Society), ://dx.doi.org/10.1109/QCE49297.2020.00020

    work page doi:10.1109/qce49297.2020.00020 2020

  19. [19]

    Caneva T, Calarco T, Montangero S (2011) Chopped random-basis quantum optimization. Phys. Rev. A 84:022326, ://dx.doi.org/10.1103/PhysRevA.84.022326

    work page doi:10.1103/physreva.84.022326 2011

  20. [20]

    ://arxiv.org/abs/2412.14783

    Cazalis J, Shah T, Chai Y, Jansen K, Kühn S (2024) Gaussian boson sampling for binary optimization. ://arxiv.org/abs/2412.14783

    work page arXiv 2024

  21. [21]

    ://arxiv.org/abs/2502.04291

    Cazals P, François A, Henriet L, Leclerc L, Marin M, Naghmouchi Y, da Silva Coelho W, Sikora F, Vitale V, Watrigant R, Garzillo MW, Dalyac C (2025 a ) Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors. ://arxiv.org/abs/2502.04291

    work page arXiv 2025

  22. [22]

    Physical Review A 112(6), ISSN 2469-9934, ://dx.doi.org/10.1103/3sjz-gfmr

    Cazals P, Sorondo A, Onofre V, Dalyac C, Coelho W, Vitale V (2025 b ) Quantum optimization on Rydberg-atom arrays with arbitrary connectivity: Gadget limitations and a heuristic approach . Physical Review A 112(6), ISSN 2469-9934, ://dx.doi.org/10.1103/3sjz-gfmr

    work page doi:10.1103/3sjz-gfmr 2025

  23. [23]

    Chao J, Rodriguez R, Crowe S (2023) Quantum Enhancements for AlphaZero . Proceedings of the Companion Conference on Genetic and Evolutionary Computation, 2179–2186, GECCO '23 Companion (New York, NY, USA: Association for Computing Machinery), ISBN 9798400701207, ://dx.doi.org/10.1145/3583133.3596302

    work page doi:10.1145/3583133.3596302 2023

  24. [24]

    Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA

    Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA

    1976

  25. [25]

    Operations Research 12(4):568--581, ://dx.doi.org/10.1287/opre.12.4.568

    Clarke G, Wright JW (1964) Scheduling of Vehicles from a Central Depot to a Number of Delivery Points . Operations Research 12(4):568--581, ://dx.doi.org/10.1287/opre.12.4.568

    work page doi:10.1287/opre.12.4.568 1964

  26. [26]

    (2024) Combinatorial Optimization and Applications

    Crainic TG, Gendreau M, Frangioni A, eds. (2024) Combinatorial Optimization and Applications. International Series in Operations Research & Management Science (Springer Cham), ://dx.doi.org/10.1007/978-3-031-57603-4

    work page doi:10.1007/978-3-031-57603-4 2024

  27. [27]

    Operations Research 6(6):791--812, ://dx.doi.org/10.1287/opre.6.6.791

    Croes GA (1958) A Method for Solving Traveling-Salesman Problems . Operations Research 6(6):791--812, ://dx.doi.org/10.1287/opre.6.6.791

    work page doi:10.1287/opre.6.6.791 1958

  28. [28]

    da Costa PRdO, Rhuggenaath J, Zhang Y, Akcay A (2020) Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning . Pan SJ, Sugiyama M, eds., Proceedings of The 12th Asian Conference on Machine Learning, volume 129 of Proceedings of Machine Learning Research, 465--480 (PMLR), ://proceedings.mlr.press/v129/costa20a.html

    2020

  29. [29]

    ://arxiv.org/abs/2207.13030

    da Silva Coelho W, D'Arcangelo M, Henry LP (2022) Efficient protocol for solving combinatorial graph problems on neutral-atom quantum processors. ://arxiv.org/abs/2207.13030

    work page arXiv 2022

  30. [30]

    Proceedings of the 31st International Conference on Neural Information Processing Systems, 6351–6361, NIPS'17 (Red Hook, NY, USA: Curran Associates Inc.), ISBN 9781510860964

    Dai H, Khalil EB, Zhang Y, Dilkina B, Song L (2017) Learning combinatorial optimization algorithms over graphs. Proceedings of the 31st International Conference on Neural Information Processing Systems, 6351–6361, NIPS'17 (Red Hook, NY, USA: Curran Associates Inc.), ISBN 9781510860964

    2017

  31. [31]

    Theses, Sorbonne Universit \'e , ://theses.hal.science/tel-04265956

    Dalyac C (2023) Quantum many-body dynamics for combinatorial optimisation and machine learning . Theses, Sorbonne Universit \'e , ://theses.hal.science/tel-04265956

    2023

  32. [32]

    Les Cahiers du GERAD G-2024-36, Groupe d’études et de recherche en analyse des décisions, GERAD, Montréal QC H3T 2A7, Canada, ://www.gerad.ca/fr/papers/G-2024-36

    Desrosiers J, Lübbecke M, Desaulniers G, Gauthier JB (2024) Branch-and-Price . Les Cahiers du GERAD G-2024-36, Groupe d’études et de recherche en analyse des décisions, GERAD, Montréal QC H3T 2A7, Canada, ://www.gerad.ca/fr/papers/G-2024-36

    2024

  33. [33]

    Biosystems 43(2):73--81, ISSN 0303-2647, ://dx.doi.org/https://doi.org/10.1016/S0303-2647(97)01708-5

    Dorigo M, Gambardella LM (1997) Ant colonies for the travelling salesman problem. Biosystems 43(2):73--81, ISSN 0303-2647, ://dx.doi.org/https://doi.org/10.1016/S0303-2647(97)01708-5

    work page doi:10.1016/s0303-2647(97)01708-5 1997

  34. [34]

    Quantum optimization of maximum inde- pendent set using rydberg atom arrays

    Ebadi S, Keesling A, Cain M, Wang TT, Levine H, Bluvstein D, Semeghini G, Omran A, Liu JG, Samajdar R, Luo XZ, Nash B, Gao X, Barak B, Farhi E, Sachdev S, Gemelke N, Zhou L, Choi S, Pichler H, Wang ST, Greiner M, Vuletić V, Lukin MD (2022) Quantum optimization of maximum independent set using Rydberg atom arrays . Science 376(6598):1209--1215, ://dx.doi.o...

    work page doi:10.1126/science.abo6587 2022

  35. [35]

    A Quantum Approximate Optimization Algorithm

    Farhi E, Goldstone J, Gutmann S (2014) A Quantum Approximate Optimization Algorithm . ://arxiv.org/abs/1411.4028

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  36. [36]

    Farhi E, Gutmann S (1998) Quantum computation and decision trees. Phys. Rev. A 58:915--928, ://dx.doi.org/10.1103/PhysRevA.58.915

    work page doi:10.1103/physreva.58.915 1998

  37. [37]

    Operations Research 4(1):61--75, ://dx.doi.org/10.1287/opre.4.1.61

    Flood MM (1956) The Traveling-Salesman Problem . Operations Research 4(1):61--75, ://dx.doi.org/10.1287/opre.4.1.61

    work page doi:10.1287/opre.4.1.61 1956

  38. [38]

    Frazier PI (2018) Bayesian Optimization, chapter 11, 255--278 ( Informs ), ://dx.doi.org/10.1287/educ.2018.0188

    work page doi:10.1287/educ.2018.0188 2018

  39. [39]

    Proceedings of the AAAI Conference on Artificial Intelligence 35(8):7474--7482, ://dx.doi.org/10.1609/aaai.v35i8.16916

    Fu ZH, Qiu KB, Zha H (2021) Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances . Proceedings of the AAAI Conference on Artificial Intelligence 35(8):7474--7482, ://dx.doi.org/10.1609/aaai.v35i8.16916

    work page doi:10.1609/aaai.v35i8.16916 2021

  40. [40]

    Applied Soft Computing 11(4):3680--3689, ISSN 1568-4946, ://dx.doi.org/https://doi.org/10.1016/j.asoc.2011.01.039

    Geng X, Chen Z, Yang W, Shi D, Zhao K (2011) Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Applied Soft Computing 11(4):3680--3689, ISSN 1568-4946, ://dx.doi.org/https://doi.org/10.1016/j.asoc.2011.01.039

    work page doi:10.1016/j.asoc.2011.01.039 2011

  41. [41]

    arXiv preprint arXiv:2506.19298

    Gibson J, Drouin-Touchette V, Kourtis S (2025) Quantum Counting in the Rydberg Blockade . arXiv preprint arXiv:2506.19298

    work page arXiv 2025

  42. [42]

    Computers & Operations Research 13(5):533--549, ISSN 0305-0548, ://dx.doi.org/https://doi.org/10.1016/0305-0548(86)90048-1, applications of Integer Programming

    Glover F (1986) Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13(5):533--549, ISSN 0305-0548, ://dx.doi.org/https://doi.org/10.1016/0305-0548(86)90048-1, applications of Integer Programming

    work page doi:10.1016/0305-0548(86)90048-1 1986

  43. [43]

    Grover LK (1996) A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 212–219, STOC '96 (New York, NY, USA: Association for Computing Machinery), ISBN 0897917855, ://dx.doi.org/10.1145/237814.237866

    work page doi:10.1145/237814.237866 1996

  44. [44]

    ://www.gurobi.com

    Gurobi Optimization, LLC (2024) Gurobi Optimizer Reference Manual . ://www.gurobi.com

    2024

  45. [45]

    Varoquaux G, Vaught T, Millman J, eds., Proceedings of the 7th Python in Science Conference, 11 -- 15 (Pasadena, CA USA)

    Hagberg AA, Schult DA, Swart PJ (2008) Exploring Network Structure, Dynamics, and Function using NetworkX . Varoquaux G, Vaught T, Millman J, eds., Proceedings of the 7th Python in Science Conference, 11 -- 15 (Pasadena, CA USA)

    2008

  46. [46]

    Designing Adiabatic Quantum Optimization: A Case Study for the Traveling Salesman Problem

    Heim B, Brown EW, Wecker D, Troyer M (2017) Designing Adiabatic Quantum Optimization: A Case Study for the Traveling Salesman Problem . ://arxiv.org/abs/1702.06248

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  47. [47]

    Journal of the Society for Industrial and Applied Mathematics 10(1):196--210, ://dx.doi.org/10.1137/0110015

    Held M, Karp RM (1962) A Dynamic Programming Approach to Sequencing Problems . Journal of the Society for Industrial and Applied Mathematics 10(1):196--210, ://dx.doi.org/10.1137/0110015

    work page doi:10.1137/0110015 1962

  48. [48]

    Quantum 4:327, ISSN 2521-327X, ://dx.doi.org/10.22331/q-2020-09-21-327

    Henriet L, Beguin L, Signoles A, Lahaye T, Browaeys A, Reymond GO, Jurczak C (2020) Quantum computing with neutral atoms. Quantum 4:327, ISSN 2521-327X, ://dx.doi.org/10.22331/q-2020-09-21-327

    work page doi:10.22331/q-2020-09-21-327 2020

  49. [49]

    Parallel Computing 17(2):221--228, ISSN 0167-8191, ://dx.doi.org/https://doi.org/10.1016/S0167-8191(05)80107-3

    Jeong CS, Kim MH (1991) Fast parallel simulated annealing for traveling salesman problem on SIMD machines with linear interconnections . Parallel Computing 17(2):221--228, ISSN 0167-8191, ://dx.doi.org/https://doi.org/10.1016/S0167-8191(05)80107-3

    work page doi:10.1016/s0167-8191(05)80107-3 1991

  50. [50]

    Computer Physics Communications 183(8):1760--1772, ISSN 0010-4655, ://dx.doi.org/https://doi.org/10.1016/j.cpc.2012.02.021

    Johansson J, Nation P, Nori F (2012) QuTiP: An open-source Python framework for the dynamics of open quantum systems . Computer Physics Communications 183(8):1760--1772, ISSN 0010-4655, ://dx.doi.org/https://doi.org/10.1016/j.cpc.2012.02.021

    work page doi:10.1016/j.cpc.2012.02.021 2012

  51. [51]

    Computer Physics Communications 184(4):1234--1240, ISSN 0010-4655, ://dx.doi.org/https://doi.org/10.1016/j.cpc.2012.11.019

    Johansson J, Nation P, Nori F (2013) QuTiP 2: A Python framework for the dynamics of open quantum systems . Computer Physics Communications 184(4):1234--1240, ISSN 0010-4655, ://dx.doi.org/https://doi.org/10.1016/j.cpc.2012.11.019

    work page doi:10.1016/j.cpc.2012.11.019 2013

  52. [52]

    Gutin G, Punnen AP, eds., The Traveling Salesman Problem and Its Variations, 369--443 (Kluwer Academic Publishers)

    Johnson DS, McGeoch LA (2002) Experimental Analysis of Heuristics for the STSP . Gutin G, Punnen AP, eds., The Traveling Salesman Problem and Its Variations, 369--443 (Kluwer Academic Publishers)

    2002

  53. [53]

    ://arxiv.org/abs/2408.08292

    Jordan SP, Shutty N, Wootters M, Zalcman A, Schmidhuber A, King R, Isakov SV, Khattar T, Babbush R (2025) Optimization by Decoded Quantum Interferometry . ://arxiv.org/abs/2408.08292

    work page arXiv 2025

  54. [54]

    Quantum annealing in the transverse Ising model,

    Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse Ising model . Physical Review E 58(5):5355–5363, ISSN 1095-3787, ://dx.doi.org/10.1103/physreve.58.5355

    work page doi:10.1103/physreve.58.5355 1998

  55. [55]

    Operations Research Letters 32(6):499--509, ISSN 0167-6377, ://dx.doi.org/https://doi.org/10.1016/j.orl.2004.04.001

    Kahng AB, Reda S (2004) Match twice and stitch: a new TSP tour construction heuristic . Operations Research Letters 32(6):499--509, ISSN 0167-6377, ://dx.doi.org/https://doi.org/10.1016/j.orl.2004.04.001

    work page doi:10.1016/j.orl.2004.04.001 2004

  56. [56]

    Optimal control of coupled spin dynamics: Design of nmr pulse sequences by gradient ascent algorithms,

    Khaneja N, Reiss T, Kehlet C, Schulte-Herbrüggen T, Glaser SJ (2005) Optimal control of coupled spin dynamics: design of NMR pulse sequences by gradient ascent algorithms . Journal of Magnetic Resonance 172(2):296--305, ISSN 1090-7807, ://dx.doi.org/https://doi.org/10.1016/j.jmr.2004.11.004

    work page doi:10.1016/j.jmr.2004.11.004 2005

  57. [57]

    Neural Computing and Applications 37(2):611--626, ISSN 1433-3058, ://dx.doi.org/10.1007/s00521-022-07438-4

    Khumalo MT, Chieza HA, Prag K, Woolway M (2025) An investigation of IBM quantum computing device performance on combinatorial optimisation problems . Neural Computing and Applications 37(2):611--626, ISSN 1433-3058, ://dx.doi.org/10.1007/s00521-022-07438-4

    work page doi:10.1007/s00521-022-07438-4 2025

  58. [58]

    Quantum Information Processing 18(3), ISSN 1573-1332, ://dx.doi.org/10.1007/s11128-019-2206-9

    Kieu TD (2019) The travelling salesman problem and adiabatic quantum computation: an algorithm. Quantum Information Processing 18(3), ISSN 1573-1332, ://dx.doi.org/10.1007/s11128-019-2206-9

    work page doi:10.1007/s11128-019-2206-9 2019

  59. [59]

    Opti- mization by Simulated Annealing,

    Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by Simulated Annealing . Science 220(4598):671--680, ://dx.doi.org/10.1126/science.220.4598.671

    work page doi:10.1126/science.220.4598.671 1983

  60. [60]

    F \"u rnkranz J, Scheffer T, Spiliopoulou M, eds., Machine Learning: ECML 2006, 282--293 (Berlin, Heidelberg: Springer Berlin Heidelberg), ISBN 978-3-540-46056-5

    Kocsis L, Szepesv \'a ri C (2006) Bandit Based Monte-Carlo Planning . F \"u rnkranz J, Scheffer T, Spiliopoulou M, eds., Machine Learning: ECML 2006, 282--293 (Berlin, Heidelberg: Springer Berlin Heidelberg), ISBN 978-3-540-46056-5

    2006

  61. [61]

    Technical report, University of Tartu

    Kocsis L, Szepesv \'a ri C, Willemson J (2006) Improved Monte-Carlo Search . Technical report, University of Tartu

    2006

  62. [62]

    Kool W, van Hoof H, Welling M (2019) Attention, Learn to Solve Routing Problems! International Conference on Learning Representations, ://openreview.net/forum?id=ByxBFsRqYm

    2019

  63. [63]

    Krotov VF (1993) Global Methods in Optimal Control Theory, 74--121 (Boston, MA: Birkh \"a user Boston), ISBN 978-1-4612-0349-0, ://dx.doi.org/10.1007/978-1-4612-0349-0_3

    work page doi:10.1007/978-1-4612-0349-0_3 1993

  64. [64]

    Salvagnin D, Lombardi M, eds., Integration of AI and OR Techniques in Constraint Programming, 202--210 (Cham: Springer International Publishing), ISBN 978-3-319-59776-8

    Kruber M, L \"u bbecke ME, Parmentier A (2017) Learning When to Use a Decomposition . Salvagnin D, Lombardi M, eds., Integration of AI and OR Techniques in Constraint Programming, 202--210 (Cham: Springer International Publishing), ISBN 978-3-319-59776-8

    2017

  65. [65]

    Physics Reports 1153:1--62, ISSN 0370-1573, ://dx.doi.org/10.1016/j.physrep.2025.10.001

    Lambert N, Gigu \`e re E, Menczel P, Li B, Hopf P, Su \'a rez G, Gali M, Lishman J, Gadhvi R, Agarwal R, Galicia A, Shammah N, Nation P, Johansson JR, Ahmed S, Cross S, Pitchford A, Nori F (2026) QuTiP 5: The Quantum Toolbox in Python . Physics Reports 1153:1--62, ISSN 0370-1573, ://dx.doi.org/10.1016/j.physrep.2025.10.001

    work page doi:10.1016/j.physrep.2025.10.001 2026

  66. [66]

    Nature 619(7969):282--287, ISSN 1476-4687, ://dx.doi.org/10.1038/s41586-023-06095-4

    Layden D, Mazzola G, Mishmash RV, Motta M, Wocjan P, Kim JS, Sheldon S (2023) Quantum-enhanced Markov chain Monte Carlo . Nature 619(7969):282--287, ISSN 1476-4687, ://dx.doi.org/10.1038/s41586-023-06095-4

    work page doi:10.1038/s41586-023-06095-4 2023

  67. [67]

    Theses, Universit \'e Paris-Saclay , ://pastel.hal.science/tel-04745992

    Leclerc L (2024) Quantum computing with Rydberg atoms : control and modelling for quantum simulation and practical algorithms . Theses, Universit \'e Paris-Saclay , ://pastel.hal.science/tel-04745992

    2024

  68. [68]

    Physical Review A 111(3), ISSN 2469-9934, ://dx.doi.org/10.1103/physreva.111.032611

    Leclerc L, Dalyac C, Bendotti P, Griset R, Mikael J, Henriet L (2025) Implementing transferable annealing protocols for combinatorial optimization on neutral-atom quantum processors: A case study on smart charging of electric vehicles. Physical Review A 111(3), ISSN 2469-9934, ://dx.doi.org/10.1103/physreva.111.032611

    work page doi:10.1103/physreva.111.032611 2025

  69. [69]

    The Bell System Technical Journal 44(10):2245--2269, ://dx.doi.org/10.1002/j.1538-7305.1965.tb04146.x

    Lin S (1965) Computer solutions of the traveling salesman problem. The Bell System Technical Journal 44(10):2245--2269, ://dx.doi.org/10.1002/j.1538-7305.1965.tb04146.x

    work page doi:10.1002/j.1538-7305.1965.tb04146.x 1965

  70. [70]

    Operations Research 21(2):498--516, ://dx.doi.org/10.1287/opre.21.2.498

    Lin S, Kernighan BW (1973) An Effective Heuristic Algorithm for the Traveling-Salesman Problem . Operations Research 21(2):498--516, ://dx.doi.org/10.1287/opre.21.2.498

    work page doi:10.1287/opre.21.2.498 1973

  71. [71]

    ://arxiv.org/abs/2407.13616

    Liu CY, Matsuyama H, hao Huang W, Yamashiro Y (2024) Quantum Local Search for Traveling Salesman Problem with Path-Slicing Strategy . ://arxiv.org/abs/2407.13616

    work page arXiv 2024

  72. [72]

    TOP 25(2):207--236, ISSN 1863-8279, ://dx.doi.org/10.1007/s11750-017-0451-6

    Lodi A, Zarpellon G (2017) On learning and branching: a survey. TOP 25(2):207--236, ISSN 1863-8279, ://dx.doi.org/10.1007/s11750-017-0451-6

    work page doi:10.1007/s11750-017-0451-6 2017

  73. [73]

    Ising formulations of many NP problems

    Lucas A (2014) Ising formulations of many NP problems . Frontiers in Physics 2, ISSN 2296-424X, ://dx.doi.org/10.3389/fphy.2014.00005

    work page doi:10.3389/fphy.2014.00005 2014

  74. [74]

    Ma \' n dziuk J, Nejman C (2015) UCT-Based Approach to Capacitated Vehicle Routing Problem . Rutkowski L, Korytkowski M, Scherer R, Tadeusiewicz R, Zadeh LA, Zurada JM, eds., Artificial Intelligence and Soft Computing, 679--690 (Cham: Springer International Publishing), ISBN 978-3-319-19369-4

    2015

  75. [75]

    Marto n n \'ak R, Santoro GE, Tosatti E (2004) Quantum annealing of the traveling-salesman problem. Phys. Rev. E 70:057701, ://dx.doi.org/10.1103/PhysRevE.70.057701

    work page doi:10.1103/physreve.70.057701 2004

  76. [76]

    Mason L, Baxter J, Bartlett P, Frean M (1999) Boosting Algorithms as Gradient Descent . Solla S, Leen T, M\" u ller K, eds., Advances in Neural Information Processing Systems, volume 12 (MIT Press), ://proceedings.neurips.cc/paper_files/paper/1999/file/96a93ba89a5b5c6c226e49b88973f46e-Paper.pdf

    1999

  77. [77]

    ://arxiv.org/abs/2003.03600

    Mazyavkina N, Sviridov S, Ivanov S, Burnaev E (2020) Reinforcement Learning for Combinatorial Optimization: A Survey . ://arxiv.org/abs/2003.03600

    work page arXiv 2020

  78. [78]

    Information Sciences 406-407:42--56, ISSN 0020-0255, ://dx.doi.org/https://doi.org/10.1016/j.ins.2017.04.020

    Mańdziuk J, Świechowski M (2017) UCT in Capacitated Vehicle Routing Problem with traffic jams . Information Sciences 406-407:42--56, ISSN 0020-0255, ://dx.doi.org/https://doi.org/10.1016/j.ins.2017.04.020

    work page doi:10.1016/j.ins.2017.04.020 2017

  79. [79]

    ://arxiv.org/abs/2211.03464

    Meyer N, Ufrecht C, Periyasamy M, Scherer DD, Plinge A, Mutschler C (2024) A Survey on Quantum Reinforcement Learning . ://arxiv.org/abs/2211.03464

    work page arXiv 2024

  80. [80]

    Quantum Machine Intelligence 6(1), ISSN 2524-4914, ://dx.doi.org/10.1007/s42484-024-00161-4

    Mohanty N, Behera BK, Ferrie C (2024) Solving the vehicle routing problem via quantum support vector machines. Quantum Machine Intelligence 6(1), ISSN 2524-4914, ://dx.doi.org/10.1007/s42484-024-00161-4

    work page doi:10.1007/s42484-024-00161-4 2024

Showing first 80 references.