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

• URL: http://arxiv.org/abs/2606.30415v1
• Date: Mon, 29 Jun 2026 15:01:18 GMT
• Title: Quantum-enhanced Monte Carlo Tree Search framework for combinatorial optimization problems
• Abstract summary: We introduce AtomTreeSearch, a hybrid classical-quantum algorithm that integrates a subroutineable on neutralatom quantum computers within a Monte Carlo Tree Search framework.<n>We find that the quantum subroutine produces more diverse and higher-quality branches compared to classical alternate subroutines.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Quantum optimisation applied to the Quadratic Assignment Problem [4.483208369550461]
  This paper investigates the performance of the emerging non-variational Quantum Walk-based optimisation algorithm (NV-QWOA) for solving small instances of the Quadratic Assignment Problem (QAP)<n>Performance is evaluated using two metrics: the number of objective function evaluations and the number of algorithm iterations required to consistently reach optimal or near optimal solutions across QAP instances with 5 to 10 facilities.<n>Our findings highlight the practical utility of quantum walks for complex quantum problems and establish a foundation for future quantum optimisation algorithms.
  arXiv  Detail & Related papers  (2026-01-03T07:50:03Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Hybrid Sequential Quantum Computing [33.72751145910978]
  We introduce hybrid sequential quantum computing (HSQC)<n>HSQC systematically integrates classical and quantum methods within a structured, stage-wise workflow.<n>Compared to standalone classical solvers, HSQC achieves a speedup of up to 700 times over SA and up to 9 times over runtime.
  arXiv  Detail & Related papers  (2025-10-07T12:15:43Z)
• Combinatorial optimization enhanced by shallow quantum circuits with 104 superconducting qubits [14.569660066740758]
  optimization problems have attracted tremendous attention due to their broad applicability and natural fitness to Ising Hamiltonians.<n>Here we propose a quantum sampling strategy, based on which we design an algorithm for accelerating solving the ground states of Ising model.<n>Using up to 104 superconducting qubits, we demonstrate that this algorithm outputs favorable solutions against even a highly-optimized classical simulated subroutine (SA) algorithm.
  arXiv  Detail & Related papers  (2025-09-15T02:58:38Z)
• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  We develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO.<n>The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs.
  arXiv  Detail & Related papers  (2025-08-04T16:44:53Z)
• Quantum Annealing for Machine Learning: Applications in Feature Selection, Instance Selection, and Clustering [41.94295877935867]
  We implement both quantum and classical solvers to compare their effectiveness.<n>For feature selection, we propose several QUBO configurations that balance feature importance and redundancy.<n>In instance selection, we propose a few novels for instance-level importance measures that extend existing methods.<n>For clustering, we embed a classical-to-quantum pipeline, using classical clustering followed by QUBO-based medoid refinement.
  arXiv  Detail & Related papers  (2025-07-20T17:59:14Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds.<n>We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• Quantum Annealing for Combinatorial Optimization: A Benchmarking Study [39.125366249242646]
  We show that a state-of-the-art quantum solver has higher accuracy (0.013%) and a significantly faster problem-solving time (6,561x) than the best classical solver.<n>Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations.
  arXiv  Detail & Related papers  (2025-04-08T16:43:24Z)
• Qubit-efficient quantum local search for combinatorial optimization [0.0]
  We present a qubit-efficient variational quantum algorithm that implements a quantum version of local search with only $lceil log l rceil$ qubits.<n>This achievement highlights the algorithm's potential for solving large-scale optimization problems on near-term quantum devices.
  arXiv  Detail & Related papers  (2025-02-04T11:44:34Z)
• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  This study systematically benchmarks several non-fault-tolerant quantum computing algorithms across four distinct optimization problems. Our benchmark includes noisy intermediate-scale quantum (NISQ) algorithms, such as the variational quantum eigensolver. Our findings reveal that no single non-FTQC algorithm performs optimally across all problem types, underscoring the need for tailored algorithmic strategies.
  arXiv  Detail & Related papers  (2024-10-30T08:41:29Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• Solving non-native combinatorial optimization problems using hybrid quantum-classical algorithms [0.0]
  Combinatorial optimization is a challenging problem applicable in a wide range of fields from logistics to finance. Quantum computing has been used to attempt to solve these problems using a range of algorithms. This work presents a framework to overcome these challenges by integrating quantum and classical resources with a hybrid approach.
  arXiv  Detail & Related papers  (2024-03-05T17:46:04Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.