Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1502.01951 · Quantum Information Processing

Tree search and quantum computation

Luís Tarrataca, Andreas Wichert

Published Nov 20, 2010• 15 citations
arXivHTMLPDF
DOI
10.1007/s11128-010-0212-z

Related papers

Quantum Computing Significance on Multidimensional Data: R-Tree Search Based on Grover's Search Algorithm

T. Hema, Micheal Olaolu Arowolo

Quantum computing is an emerging field of study and gains importance due to the fact that with the introduction of quantum computers, many challenges and changes are presented for the existing algorithms. The main reason for this is the exponential speed of such computers. This study analyzes some of the benefits and implications of quantum computing on geometrical problems such as the multidimensional search for window queries with R-Trees. A review of the window query on R-Trees in classical computing is done to consider its adaptability to quantum computers by applying the Grover's quantum search algorithm from a theoretical point of view. Thereby, the query time complexity in worst-case scenarios could be improved to quadratic search time.

Advances in systems analysis, software engineering, and high performance computing book series•Mar 3, 2023•3 citations

Quantum Search Algorithm and Its Applications

Weng-Long Chang, Athanasios V. Vasilakos

Studies in big data•Dec 21, 2020•0 citations

Quantum search algorithms

Christoph Dürr, xb b b

•Jan 1, 2005•17 citations

Quantum Monte Carlo Tree Search with Fixed Confidence

Mingjie Hu, Jian-Qiang Hu, Enlu Zhou

Recent advances in quantum computing are opening new opportunities for computationally intensive decision problems. This paper studies how quantum computing can improve Monte Carlo tree search (MCTS) in the fixed-confidence setting, where the goal is to identify a near-optimal move in a given game tree with high probability while minimizing query complexity. We first formulate MCTS under a quantum oracle model. We then develop a quantum MCTS algorithm (QMCTS) that combines threshold-based elimination on the search tree with quantum Monte Carlo estimation to reduce the cost of evaluating stochastic leaf values. We establish an instance-dependent lower bound on the query complexity and derive a corresponding upper bound for QMCTS. The lower-bound analysis introduces a new quantum phase-testing result that may also be useful beyond MCTS. We validate the theoretical results through simulation experiments and further demonstrate the feasibility of QMCTS on real quantum hardware.

quant-pharXiv:2609.33132•Sep 29, 2026•0 citations

Quantum Search on Computation Trees

Jevgēnijs Vihrovs

We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of computation. If a vertex \(v\) in the tree of depth \(D\) is computed in \(t_v\) steps from its parent, then we show that detection of a marked vertex requires \(\text O(\sqrt {TD})\) queries to the steps of the computing procedures, where \(T = \sum_v t^2_v\). This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms. The underlying algorithm is simple, explicitly constructed, and has low poly-logarithmic factors in the complexity.

arXiv:2505.22405•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2026•0 citations

Quantum Search Algorithms

Uwe Schöning, Randall J. Pruim

Springer eBooks•Jan 1, 1998•1 citation
Quantum computing is an emerging field of study and gains importance due to the fact that with the introduction of quantum computers, many challenges and changes are presented for the existing algorithms. The main reason for this is the exponential speed of such computers. This study analyzes some of the benefits and implications of quantum computing on geometrical problems such as the multidimensional search for window queries with R-Trees. A review of the window query on R-Trees in classical computing is done to consider its adaptability to quantum computers by applying the Grover's quantum search algorithm from a theoretical point of view. Thereby, the query time complexity in worst-case scenarios could be improved to quadratic search time.
Recent advances in quantum computing are opening new opportunities for computationally intensive decision problems. This paper studies how quantum computing can improve Monte Carlo tree search (MCTS) in the fixed-confidence setting, where the goal is to identify a near-optimal move in a given game tree with high probability while minimizing query complexity. We first formulate MCTS under a quantum oracle model. We then develop a quantum MCTS algorithm (QMCTS) that combines threshold-based elimination on the search tree with quantum Monte Carlo estimation to reduce the cost of evaluating stochastic leaf values. We establish an instance-dependent lower bound on the query complexity and derive a corresponding upper bound for QMCTS. The lower-bound analysis introduces a new quantum phase-testing result that may also be useful beyond MCTS. We validate the theoretical results through simulation experiments and further demonstrate the feasibility of QMCTS on real quantum hardware.
We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of computation. If a vertex vvv in the tree of depth DDD is computed in tvt_vtv​ steps from its parent, then we show that detection of a marked vertex requires O(TD)\text O(\sqrt {TD})O(TD​) queries to the steps of the computing procedures, where T=∑vtv2T = \sum_v t^2_vT=∑v​tv2​. This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms. The underlying algorithm is simple, explicitly constructed, and has low poly-logarithmic factors in the complexity.