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:2310.15303 · IEEE Access

Parallel Quantum Rapidly-Exploring Random Trees

Paul Lathrop, Beth Boardman, Sonia Martı́nez

Published Jan 1, 2024• 5 citations
arXivHTMLPDF

Abstract

In this paper, we present the Parallel Quantum Rapidly-Exploring Random Tree (Pq-RRT) algorithm, a parallel version of the Quantum Rapidly-Exploring Random Trees (q-RRT) algorithm [1]. Parallel Quantum RRT is a parallel quantum algorithm formulation of a sampling-based motion planner that uses Quantum Amplitude Amplification to search databases of reachable states for addition to a tree. In this work we investigate how parallel quantum devices can more efficiently search a database, as the quantum measurement process involves the collapse of the superposition to a base state, erasing probability information and therefore the ability to efficiently find multiple solutions. Pq-RRT uses a manager/parallel-quantum-workers formulation, inspired by traditional parallel motion planning, to perform simultaneous quantum searches of a feasible state database. We present symbolic runtime comparisons between parallel architectures, then results regarding likelihoods of multiple parallel units finding any and all solutions contained with a shared database, with and without reachability errors, allowing efficiency predictions to be made. We offer simulations in dense obstacle environments showing efficiency, density/heatmap, and speed comparisons for Pq-RRT against q-RRT, classical RRT, and classical parallel RRT. We then present Quantum Database Annealing, a database construction strategy that uses a temperature construct to define database creation over time for balancing exploration and exploitation.

DOI
10.1109/access.2024.3383313

Related papers

Quantum Search Approaches to Sampling-Based Motion Planning

Paul Lathrop, Beth Boardman, Sonia Martı́nez

In this paper, we present a novel formulation of traditional sampling-based motion planners as database-oracle structures that can be solved via quantum search algorithms. We consider two complementary scenarios: for simpler sparse environments, we formulate the Quantum Full Path Search Algorithm (q-FPS), which creates a superposition of full random path solutions, manipulates probability amplitudes with Quantum Amplitude Amplification (QAA), and quantum measures a single obstacle free full path solution. For dense unstructured environments, we formulate the Quantum Rapidly Exploring Random Tree algorithm, q-RRT, that creates quantum superpositions of possible parent-child connections, manipulates probability amplitudes with QAA, and quantum measures a single reachable state, which is added to a tree. As performance depends on the number of oracle calls and the probability of measuring good quantum states, we quantify how these errors factor into the probabilistic completeness properties of the algorithm. We then numerically estimate the expected number of database solutions to provide an approximation of the optimal number of oracle calls in the algorithm. We compare the q-RRT algorithm with a classical implementation and verify quadratic run-time speedup in the largest connected component of a 2D dense random lattice. We conclude by evaluating a proposed approach to limit the expected number of database solutions and thus limit the optimal number of oracle calls to a given number.

arXiv:2304.06479•IEEE Access•Jan 1, 2023•12 citations

Fat-Tree QRAM: A High-Bandwidth Shared Quantum Random Access Memory for Parallel Queries

Shifan Xu, Alvin Lu, Yongshan Ding

Quantum Random Access Memory (QRAM) is a crucial architectural component for querying classical or quantum data in superposition, enabling algorithms with wide-ranging applications in quantum arithmetic, quantum chemistry, machine learning, and quantum cryptography. In this work, we introduce Fat-Tree QRAM, a novel query architecture capable of pipelining multiple quantum queries simultaneously while maintaining desirable scalings in query speed and fidelity. Specifically, Fat-Tree QRAM performs $O(\log (N))$ independent queries in $O(\log (N))$ time using $O(N)$ qubits, offering immense parallelism benefits over traditional QRAM architectures. To demonstrate its experimental feasibility, we propose modular and on-chip implementations of Fat-Tree QRAM based on superconducting circuits and analyze their performance and fidelity under realistic parameters. Furthermore, a query scheduling protocol is presented to maximize hardware utilization and access the underlying data at an optimal rate. These results suggest that Fat-Tree QRAM is an attractive architecture in a shared memory system for practical quantum computing.

arXiv:2502.06767•International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)•Mar 27, 2025•2 citations

Quantum-Enhanced Monte Carlo Tree Search

Jincheng Zhang

This paper investigates the potential of quantum computing to significantly enhance the efficiency of Monte Carlo Tree Search (MCTS) algorithms. MCTS, a cornerstone of modern artificial intelligence, particularly in game playing, relies heavily on computationally intensive simulations to evaluate game states and guide the search process. We propose a hybrid quantum-classical algorithm that leverages quantum superposition and entanglement to achieve a parallel exploration of the vast search space inherent in MCTS. The core mechanism involves utilizing quantum computers for specific tasks within the MCTS workflow, primarily the evaluation of game states. We formulate the problem as a quantum optimization task, mapping the state evaluation to a quantum objective function. The algorithm employs a classical controller to manage the quantum computation, orchestrating the simulations and extracting information. Preliminary theoretical analysis suggests a potential exponential speedup in state evaluation compared to classical simulations, contingent on the quality of the quantum hardware and the effectiveness of the hybrid approach. This research contributes to the broader field of quantum-accelerated AI and provides a framework for future investigations into the practical application of quantum computing within complex decision-making algorithms.

•Sep 5, 2026•0 citations

Quantum State Superposition-Based Database Query Optimization

Jincheng Zhang

This paper investigates the potential of leveraging quantum state superposition to optimize database queries. Traditional database queries often face bottlenecks due to sequential processing and limitations in parallelization. We propose a novel approach that translates database queries into quantum state superposition problems, enabling parallel exploration of multiple query branches simultaneously. The core mechanism involves constructing a quantum circuit designed to exploit superposition and implementing algorithms for efficient result merging. We present a theoretical framework and a conceptual algorithm demonstrating the feasibility of this approach, highlighting the potential for significant speedups in query execution. The focus is on the conceptual design and theoretical considerations, without requiring experimental validation. The key innovation lies in directly mapping database query operations onto quantum superposition and leveraging quantum parallelism. This work represents a foundational step toward exploring quantum computing's role in database optimization.

•Sep 5, 2026•0 citations

Quantum-Enhanced Monte Carlo Tree Search for Complex Optimization Problems

Jincheng Zhang

This paper explores the potential of quantum computing to revolutionize Monte Carlo Tree Search (MCTS) algorithms, a cornerstone technique in reinforcement learning and game AI. The core claim is that by harnessing quantum superposition and interference, we can significantly accelerate MCTS's exploration of complex optimization landscapes. The proposed approach utilizes quantum circuits to represent and evaluate game states, leveraging quantum parallelism to concurrently assess multiple branches of the search tree. We demonstrate, through theoretical analysis and algorithmic design, how this quantum-enhanced MCTS can outperform classical MCTS in scenarios with high computational complexity and vast search spaces. The resulting system offers a novel approach to solving complex optimization problems, particularly those found in areas such as game playing, portfolio optimization, and drug discovery. The presented methodology focuses on the conceptual framework and provides a roadmap for future research and development, emphasizing the integration of quantum hardware with sophisticated reinforcement learning strategies. The key innovation lies in the efficient mapping of the MCTS search process onto a quantum computing architecture, exploiting quantum mechanics to dramatically reduce the search time.

•Aug 29, 2026•0 citations

Multi-Dimensional Spatial Information Retrieval via Quantum Algorithms: Optimization

Jincheng Zhang

This paper presents a novel quantum algorithm for optimizing multi-dimensional spatial information retrieval. Traditional information retrieval methods struggle with the exponential growth of complexity in high-dimensional spaces. We propose a quantum approach leveraging superposition and interference to drastically improve search efficiency. The core concept involves mapping the retrieval space into a quantum state space, utilizing quantum entanglement for parallel search across multiple dimensions, and employing quantum measurement to rapidly pinpoint the target information. The algorithm's performance is theoretically analyzed, demonstrating a potential speedup compared to classical algorithms. Specifically, we outline a framework for constructing a quantum index and detailing the steps involved in the search process. The key elements of the algorithm are the quantum state preparation, entanglement generation, and the final measurement stage. We provide a mathematical formulation of the core operations, focusing on the quantum circuit design and the probability amplitudes involved. The optimization strategy relies on minimizing the number of quantum gates required while maintaining the algorithm's effectiveness. The ultimate goal is to provide a robust and scalable quantum solution for spatial information retrieval, addressing the limitations of current classical methods.

•Sep 2, 2026•0 citations
In this paper, we present the Parallel Quantum Rapidly-Exploring Random Tree (Pq-RRT) algorithm, a parallel version of the Quantum Rapidly-Exploring Random Trees (q-RRT) algorithm [1]. Parallel Quantum RRT is a parallel quantum algorithm formulation of a sampling-based motion planner that uses Quantum Amplitude Amplification to search databases of reachable states for addition to a tree. In this work we investigate how parallel quantum devices can more efficiently search a database, as the quantum measurement process involves the collapse of the superposition to a base state, erasing probability information and therefore the ability to efficiently find multiple solutions. Pq-RRT uses a manager/parallel-quantum-workers formulation, inspired by traditional parallel motion planning, to perform simultaneous quantum searches of a feasible state database. We present symbolic runtime comparisons between parallel architectures, then results regarding likelihoods of multiple parallel units finding any and all solutions contained with a shared database, with and without reachability errors, allowing efficiency predictions to be made. We offer simulations in dense obstacle environments showing efficiency, density/heatmap, and speed comparisons for Pq-RRT against q-RRT, classical RRT, and classical parallel RRT. We then present Quantum Database Annealing, a database construction strategy that uses a temperature construct to define database creation over time for balancing exploration and exploitation.
In this paper, we present a novel formulation of traditional sampling-based motion planners as database-oracle structures that can be solved via quantum search algorithms. We consider two complementary scenarios: for simpler sparse environments, we formulate the Quantum Full Path Search Algorithm (q-FPS), which creates a superposition of full random path solutions, manipulates probability amplitudes with Quantum Amplitude Amplification (QAA), and quantum measures a single obstacle free full path solution. For dense unstructured environments, we formulate the Quantum Rapidly Exploring Random Tree algorithm, q-RRT, that creates quantum superpositions of possible parent-child connections, manipulates probability amplitudes with QAA, and quantum measures a single reachable state, which is added to a tree. As performance depends on the number of oracle calls and the probability of measuring good quantum states, we quantify how these errors factor into the probabilistic completeness properties of the algorithm. We then numerically estimate the expected number of database solutions to provide an approximation of the optimal number of oracle calls in the algorithm. We compare the q-RRT algorithm with a classical implementation and verify quadratic run-time speedup in the largest connected component of a 2D dense random lattice. We conclude by evaluating a proposed approach to limit the expected number of database solutions and thus limit the optimal number of oracle calls to a given number.
Quantum Random Access Memory (QRAM) is a crucial architectural component for querying classical or quantum data in superposition, enabling algorithms with wide-ranging applications in quantum arithmetic, quantum chemistry, machine learning, and quantum cryptography. In this work, we introduce Fat-Tree QRAM, a novel query architecture capable of pipelining multiple quantum queries simultaneously while maintaining desirable scalings in query speed and fidelity. Specifically, Fat-Tree QRAM performs O(log⁡(N))O(\log (N))O(log(N)) independent queries in O(log⁡(N))O(\log (N))O(log(N)) time using O(N)O(N)O(N) qubits, offering immense parallelism benefits over traditional QRAM architectures. To demonstrate its experimental feasibility, we propose modular and on-chip implementations of Fat-Tree QRAM based on superconducting circuits and analyze their performance and fidelity under realistic parameters. Furthermore, a query scheduling protocol is presented to maximize hardware utilization and access the underlying data at an optimal rate. These results suggest that Fat-Tree QRAM is an attractive architecture in a shared memory system for practical quantum computing.
This paper investigates the potential of quantum computing to significantly enhance the efficiency of Monte Carlo Tree Search (MCTS) algorithms. MCTS, a cornerstone of modern artificial intelligence, particularly in game playing, relies heavily on computationally intensive simulations to evaluate game states and guide the search process. We propose a hybrid quantum-classical algorithm that leverages quantum superposition and entanglement to achieve a parallel exploration of the vast search space inherent in MCTS. The core mechanism involves utilizing quantum computers for specific tasks within the MCTS workflow, primarily the evaluation of game states. We formulate the problem as a quantum optimization task, mapping the state evaluation to a quantum objective function. The algorithm employs a classical controller to manage the quantum computation, orchestrating the simulations and extracting information. Preliminary theoretical analysis suggests a potential exponential speedup in state evaluation compared to classical simulations, contingent on the quality of the quantum hardware and the effectiveness of the hybrid approach. This research contributes to the broader field of quantum-accelerated AI and provides a framework for future investigations into the practical application of quantum computing within complex decision-making algorithms.
This paper investigates the potential of leveraging quantum state superposition to optimize database queries. Traditional database queries often face bottlenecks due to sequential processing and limitations in parallelization. We propose a novel approach that translates database queries into quantum state superposition problems, enabling parallel exploration of multiple query branches simultaneously. The core mechanism involves constructing a quantum circuit designed to exploit superposition and implementing algorithms for efficient result merging. We present a theoretical framework and a conceptual algorithm demonstrating the feasibility of this approach, highlighting the potential for significant speedups in query execution. The focus is on the conceptual design and theoretical considerations, without requiring experimental validation. The key innovation lies in directly mapping database query operations onto quantum superposition and leveraging quantum parallelism. This work represents a foundational step toward exploring quantum computing's role in database optimization.
This paper explores the potential of quantum computing to revolutionize Monte Carlo Tree Search (MCTS) algorithms, a cornerstone technique in reinforcement learning and game AI. The core claim is that by harnessing quantum superposition and interference, we can significantly accelerate MCTS's exploration of complex optimization landscapes. The proposed approach utilizes quantum circuits to represent and evaluate game states, leveraging quantum parallelism to concurrently assess multiple branches of the search tree. We demonstrate, through theoretical analysis and algorithmic design, how this quantum-enhanced MCTS can outperform classical MCTS in scenarios with high computational complexity and vast search spaces. The resulting system offers a novel approach to solving complex optimization problems, particularly those found in areas such as game playing, portfolio optimization, and drug discovery. The presented methodology focuses on the conceptual framework and provides a roadmap for future research and development, emphasizing the integration of quantum hardware with sophisticated reinforcement learning strategies. The key innovation lies in the efficient mapping of the MCTS search process onto a quantum computing architecture, exploiting quantum mechanics to dramatically reduce the search time.
This paper presents a novel quantum algorithm for optimizing multi-dimensional spatial information retrieval. Traditional information retrieval methods struggle with the exponential growth of complexity in high-dimensional spaces. We propose a quantum approach leveraging superposition and interference to drastically improve search efficiency. The core concept involves mapping the retrieval space into a quantum state space, utilizing quantum entanglement for parallel search across multiple dimensions, and employing quantum measurement to rapidly pinpoint the target information. The algorithm's performance is theoretically analyzed, demonstrating a potential speedup compared to classical algorithms. Specifically, we outline a framework for constructing a quantum index and detailing the steps involved in the search process. The key elements of the algorithm are the quantum state preparation, entanglement generation, and the final measurement stage. We provide a mathematical formulation of the core operations, focusing on the quantum circuit design and the probability amplitudes involved. The optimization strategy relies on minimizing the number of quantum gates required while maintaining the algorithm's effectiveness. The ultimate goal is to provide a robust and scalable quantum solution for spatial information retrieval, addressing the limitations of current classical methods.