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

International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia)

Deterministic Quantum Search for Index Retrieval: Algorithm Design and Implementation

Harishankar Mishra, Asvija Balasubramanyam, Gudapati Naresh Raghava

Published Jan 9, 2026• 1 citation
Publisher

Abstract

Searching for index corresponding to a given data in an unsorted database represents a nontrivial unstructured search problem with wide-ranging applications in fields like data mining, cryptography, and bio-informatics. Unlike the reverse query, where the data can be trivially obtained from a known index, retrieving the index from data lacks order preservation, making efficient classical search infeasible without linear traversal. To address this problem, we propose a deterministic quantum search algorithm, which provides a solution for the database having any arbitrary number of entries while always guaranteeing success in a single execution. The algorithm is formulated within the quantum circuit model, employing amplitude manipulation techniques that eliminate probabilistic outcomes and ensure exact retrieval of the location of data. We present a scalable circuit construction adaptable to databases of varying sizes, without constraints such as number of entries equal to power-of-two. Because of its adaptability, the proposed algorithm is directly applicable to real-world datasets without the need for costly pre-processing or ineffective data padding. The proposed work presents a resilient and exact technique for the quantum index retrieval problem by providing a solution offering wide applicability and dependable outputs. Our findings shows a clear way towards quantum primitives that can be easily included into deterministic computing workflows, bridging the gap between theoretical speedup and the real-world requirement for dependable outputs.

DOI
10.1145/3773656.3773688

Related papers

Implementation of Database Search with Quantum Computing: Grover's Algorithm vs Linear Search

Sachin Khurana, Manisha J. Nene

The present study aims to examine the real-world implications of Grover's algorithm, specifically focusing on its quadratic speedup in contrast to classical linear search techniques employed for unsorted databases. The objective is to bridge the gap between theoretical potential and practical application in the field of quantum computing. This study conducts a comprehensive analysis of Grover's Algorithm and traditional linear search across databases of varying sizes, uniquely contributing by empirically validating Grover's Algorithm's superior performance and aligning it with theoretical expectations. Significantly, the study expands its analysis to encompass larger databases, further affirming the algorithm's utility in handling growing database sizes. This study significantly contributes to the progress of quantum computing through the practical implementation of theoretical principles as well as enhancing the scientific community's understanding of quantum search algorithms and their relative efficacy.

International Conference on Ambient Intelligence, Knowledge Informatics and Industrial Electronics (AIKIIE)•Nov 2, 2023•9 citations

Evaluating the Practicality of Grover’s Algorithm for Large-Scale Data Search via Quantum Simulation

Lovish Bhatia, Vinay Shankar Pandey, Ajay K. Sharma

Abstract Quantum computing can solve some classes of problems faster than classical computing. Among the greatest quantum algorithms to showcase this benefit is Grover's search algorithm, which has a quadratic speed-up for unstructured search problems. In this study, we present an implementation of Grover’s algorithm on a large-scale dataset comprising approximately 131,072 (217) names. We contrast its efficiency with the classical linear search based on time complexity, scalability, and the likelihood of success. The experiment was conducted using Qiskit on a quantum simulator, where several query scenarios were implemented to verify the algorithm's efficiency and accuracy. Our findings highlight the theoretical advantage of Grover’s algorithm in situations involving large data sets, while also discussing real-world limitations such as gate noise, qubit number, and circuit depth as we move towards actual quantum hardware. This study serves as a step toward evaluating the real-world relevance of quantum search algorithms and provides information on current challenges and future directions in quantum information retrieval.

•Jul 2, 2025•1 citation

Deterministic Quantum Search via Recursive Oracle Expansion

Burke, John, Ciarán McGoldrick

We introduce a novel deterministic quantum search algorithm that provides a practical alternative to conventional probabilistic search approaches. Our scheme eliminates the inherent uncertainty of quantum search without relying on arbitrary phase rotations, a key limitation of other deterministic methods. The algorithm achieves certainty by recursively expanding the base oracle so that it marks all states prefixed by the same two bits as the target, encompassing exactly one-quarter of the search space. This enables a step-by-step reduction of the superposition until the target state can be measured with certainty. The algorithm achieves deterministic success with a query complexity of $O(N^{\log_2(3)/2}) \approx O(N^{0.7925})$, falling between Grover's $O(\sqrt{N})$ scaling and the classical $O(N)$. Our approach relies exclusively on two-qubit nearest-neighbour diffusion operators, avoiding global diffusion entirely. We show that, despite the increased query complexity, this design reduces the total number of two-qubit gates required for diffusion by more than an order of magnitude for search spaces up to at least 18 qubits, with even greater advantages on hardware with limited qubit connectivity. The scheme's inherent determinism, reliance on simple nearest-neighbour, low-depth operations, and scalable recursive structure make it well-suited for hardware implementation. Additionally, we show that the algorithm naturally supports partial database search, enabling deterministic identification of selected target bits without requiring a full search, further broadening its applicability.

arXiv:2507.15797•Jul 21, 2025•2 citations

Quantum mechanics can find a needle in a haystack every time

F. Mohit, Joshua J. Guanzon, Jaden McKinlay +5 more

Grover's algorithm is one of the pioneering demonstrations of the advantages of quantum computing over its classical counterpart, providing - at most - a quadratic speed-up over the classical solution for unstructured database search. The original formulation of Grover's algorithm is non-deterministic, finding the answer with a probability that varies with the size of the search space and the number of marked elements. A recent reformulation introduced a deterministic form of Grover's algorithm that - in principle - finds the answer with certainty. Here we realise the deterministic Grover's algorithm on a programmable photonic integrated circuit, finding that it not only outperforms the original Grover's algorithm as predicted, but is also markedly more robust against technological imperfections. We explore databases of 4 to 10 elements, with every choice of a single marked element, achieving an average success probability of $99.77 \pm 0.05\%$.

arXiv:2506.06435•Jun 6, 2025•2 citations

An Oracle Design for Grover’s Quantum Search Algorithm for Solving the Exact String Matching Problem

Jeffrey A. Aborot

Grover’s quantum search algorithm is a template for doing quantum search in unstructured search spaces. The details of the oracle in Grover’s algorithm is abstracted for the purpose of analyzing the bound on the number of queries the algorithm must make in order to find the target element of the search space. In order for Grover’s quantum search algorithm to be usable in a specific unstructured search problem, one must provide details on the inner workings of the oracle. Specifically, we present a high-level and basic design of the oracle using the quantum computing model specific to the exact string matching problem. We describe our design using the quantum circuit model of computing and show that the gate complexity of the circuit is linear with respect to the product of the length of the pattern and the size of the alphabet. We have suggested a quantum memory structure for storage and retrieval of the input text. The quantum circuit we presented requires scratch qubits linear to the product of the length of the pattern and the size of the alphabet to reduce the size of the scratch register without exponential increase in the count of elementary gates required for the computation.

Workshop on Computation: Theory and Practice (WCTP)•Dec 1, 2018•3 citations

Hardware Efficient Quantum Search Algorithm

Ji Liu, Huiyang Zhou

Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.

arXiv:2103.14196•Mar 26, 2021•15 citations
Searching for index corresponding to a given data in an unsorted database represents a nontrivial unstructured search problem with wide-ranging applications in fields like data mining, cryptography, and bio-informatics. Unlike the reverse query, where the data can be trivially obtained from a known index, retrieving the index from data lacks order preservation, making efficient classical search infeasible without linear traversal. To address this problem, we propose a deterministic quantum search algorithm, which provides a solution for the database having any arbitrary number of entries while always guaranteeing success in a single execution. The algorithm is formulated within the quantum circuit model, employing amplitude manipulation techniques that eliminate probabilistic outcomes and ensure exact retrieval of the location of data. We present a scalable circuit construction adaptable to databases of varying sizes, without constraints such as number of entries equal to power-of-two. Because of its adaptability, the proposed algorithm is directly applicable to real-world datasets without the need for costly pre-processing or ineffective data padding. The proposed work presents a resilient and exact technique for the quantum index retrieval problem by providing a solution offering wide applicability and dependable outputs. Our findings shows a clear way towards quantum primitives that can be easily included into deterministic computing workflows, bridging the gap between theoretical speedup and the real-world requirement for dependable outputs.
The present study aims to examine the real-world implications of Grover's algorithm, specifically focusing on its quadratic speedup in contrast to classical linear search techniques employed for unsorted databases. The objective is to bridge the gap between theoretical potential and practical application in the field of quantum computing. This study conducts a comprehensive analysis of Grover's Algorithm and traditional linear search across databases of varying sizes, uniquely contributing by empirically validating Grover's Algorithm's superior performance and aligning it with theoretical expectations. Significantly, the study expands its analysis to encompass larger databases, further affirming the algorithm's utility in handling growing database sizes. This study significantly contributes to the progress of quantum computing through the practical implementation of theoretical principles as well as enhancing the scientific community's understanding of quantum search algorithms and their relative efficacy.
Abstract Quantum computing can solve some classes of problems faster than classical computing. Among the greatest quantum algorithms to showcase this benefit is Grover's search algorithm, which has a quadratic speed-up for unstructured search problems. In this study, we present an implementation of Grover’s algorithm on a large-scale dataset comprising approximately 131,072 (217) names. We contrast its efficiency with the classical linear search based on time complexity, scalability, and the likelihood of success. The experiment was conducted using Qiskit on a quantum simulator, where several query scenarios were implemented to verify the algorithm's efficiency and accuracy. Our findings highlight the theoretical advantage of Grover’s algorithm in situations involving large data sets, while also discussing real-world limitations such as gate noise, qubit number, and circuit depth as we move towards actual quantum hardware. This study serves as a step toward evaluating the real-world relevance of quantum search algorithms and provides information on current challenges and future directions in quantum information retrieval.
We introduce a novel deterministic quantum search algorithm that provides a practical alternative to conventional probabilistic search approaches. Our scheme eliminates the inherent uncertainty of quantum search without relying on arbitrary phase rotations, a key limitation of other deterministic methods. The algorithm achieves certainty by recursively expanding the base oracle so that it marks all states prefixed by the same two bits as the target, encompassing exactly one-quarter of the search space. This enables a step-by-step reduction of the superposition until the target state can be measured with certainty. The algorithm achieves deterministic success with a query complexity of O(Nlog⁡2(3)/2)≈O(N0.7925)O(N^{\log_2(3)/2}) \approx O(N^{0.7925})O(Nlog2​(3)/2)≈O(N0.7925), falling between Grover's O(N)O(\sqrt{N})O(N​) scaling and the classical O(N)O(N)O(N). Our approach relies exclusively on two-qubit nearest-neighbour diffusion operators, avoiding global diffusion entirely. We show that, despite the increased query complexity, this design reduces the total number of two-qubit gates required for diffusion by more than an order of magnitude for search spaces up to at least 18 qubits, with even greater advantages on hardware with limited qubit connectivity. The scheme's inherent determinism, reliance on simple nearest-neighbour, low-depth operations, and scalable recursive structure make it well-suited for hardware implementation. Additionally, we show that the algorithm naturally supports partial database search, enabling deterministic identification of selected target bits without requiring a full search, further broadening its applicability.
Grover's algorithm is one of the pioneering demonstrations of the advantages of quantum computing over its classical counterpart, providing - at most - a quadratic speed-up over the classical solution for unstructured database search. The original formulation of Grover's algorithm is non-deterministic, finding the answer with a probability that varies with the size of the search space and the number of marked elements. A recent reformulation introduced a deterministic form of Grover's algorithm that - in principle - finds the answer with certainty. Here we realise the deterministic Grover's algorithm on a programmable photonic integrated circuit, finding that it not only outperforms the original Grover's algorithm as predicted, but is also markedly more robust against technological imperfections. We explore databases of 4 to 10 elements, with every choice of a single marked element, achieving an average success probability of 99.77±0.05%99.77 \pm 0.05\%99.77±0.05%.
Grover’s quantum search algorithm is a template for doing quantum search in unstructured search spaces. The details of the oracle in Grover’s algorithm is abstracted for the purpose of analyzing the bound on the number of queries the algorithm must make in order to find the target element of the search space. In order for Grover’s quantum search algorithm to be usable in a specific unstructured search problem, one must provide details on the inner workings of the oracle. Specifically, we present a high-level and basic design of the oracle using the quantum computing model specific to the exact string matching problem. We describe our design using the quantum circuit model of computing and show that the gate complexity of the circuit is linear with respect to the product of the length of the pattern and the size of the alphabet. We have suggested a quantum memory structure for storage and retrieval of the input text. The quantum circuit we presented requires scratch qubits linear to the product of the length of the pattern and the size of the alphabet to reduce the size of the scratch register without exponential increase in the count of elementary gates required for the computation.
Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.