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

Progress of Theoretical and Experimental Physics

Implementing a deterministic search algorithm with a single qubit

Chen-Hui Peng, Liang Bin, Xin He, Yong-Nan Sun, Qi-Ping Su, Chui‐Ping Yang

Published Mar 1, 2023• 1 citation
Publisher

Abstract

Abstract Quantum search algorithms have important applications in quantum information, which have been experimentally demonstrated in several quantum systems with database sizes up to 16. We first propose an efficient quantum search scheme based on an optimized Grover’s algorithm and a novel encoding method. With this scheme, a target element can be deterministically searched in a large database using only a single qubit. Then we implement this search scheme in linear optics with database sizes up to 40. Experimental results fit well with the theoretical results, with all fidelities greater than 99.7%. The limitation of the number of elements encoded in a single qubit is also investigated in the experiment. The experimental results indicate that a target state can be successfully searched from a database of size 36 using a single qubit in our laboratory. Since only one qubit and one-qubit gates are required, this search scheme is quite efficient and general, and can be adopted to implement the same task in most quantum systems.

DOI
10.1093/ptep/ptad032

Related papers

Implementing a quantum search algorithm with nonorthogonal states

Shi-Chao Wang, Yan Chi, Li Zhi Yu +3 more

The search algorithm is one of the most widely studied quantum algorithms, while its complete implementation in experiments is difficult and only a few experimental works have been reported. Based on Grover's algorithm, we propose a scheme of quantum search using nonorthogonal states and experimentally implement the entire scheme in a linear optical system. With this scheme, a large-sized search space can be encoded using only one qubit and the search probability of the target state is $100%$ in theory. The experimental setup and the operations for implementing this scheme are extremely simple. In our linear optical experiment, different target states are successfully found from a database of nine elements with all fidelities $>0.99$, the state evolution from the initial state to a target state is studied, and the medium states and the final state are shown in a Bloch sphere. The scheme is general and can be easily realized in a wide range of quantum systems. This work may pave an avenue to implement quantum algorithms with nonorthogonal states.

Physical Review A•Mar 15, 2021•7 citations

Implementation of Grover’s Iterator for Quantum Searching With an Arbitrary Number of Qubits

Sihyung Lee, Seung Yeob Nam

Grover’s algorithm harnesses the power of quantum computing to swiftly locate specific elements in an unstructured database, outperforming classical computers in tasks like database searching. This algorithm capitalizes on the unique ability of qubits to be in both 0 and 1 states simultaneously (superposition), allowing it to scan the entire search space at once. It then boosts the probability of the target element, making it more prominent. While the foundational concepts of Grover’s algorithm are well-documented, practical implementation using quantum operators, especially for large search spaces, remains less explored beyond basic examples with a small number of qubits. Existing general synthesis techniques often involve numerous operators or are time-consuming. Our proposed methods specifically address the amplitude-amplification component of Grover’s algorithm for any size of search space. These methods detail the required types and quantities of qubits and operators, emphasizing minimal usage and efficient assembly. Developed and evaluated in Python, our methods consistently identified target elements with over 95% accuracy and achieved configurations comparably compact as those in the existing literature but at a faster pace. We anticipate that these methods facilitate practical implementations of Grover’s algorithm across various domains.

IEEE Access•Jan 1, 2024•7 citations

Experimental demonstration of deterministic quantum search for multiple marked states without adjusting the oracle

Xin He, Wentao Zhao, Wang-Chu Lv +5 more

Grover's search algorithm is a well-known quantum algorithm that has been extensively studied and improved to increase its success rate and enhance its flexibility. However, most improved search algorithms require an adjustment of the oracle, which may not be feasible in practical problem-solving scenarios. In this work, we report an experimental demonstration of a deterministic quantum search for multiple marked states without adjusting the oracle. A linear optical setup is designed to search for two marked states, one in a 16-state database with an initial equal-superposition state and the other in an 8-state database with different initial nonequal-superposition states. The evolution of the probability of finding each state in the database is also measured and displayed. Our experimental results agree well with the theoretical predictions, thereby proving the feasibility of the search protocol and the implementation scheme. This work is a pioneering experimental demonstration of deterministic quantum search for multiple marked states without adjusting the oracle.

Optics Letters•Aug 1, 2023•4 citations

Grover's search algorithm for nnn qubits with optimal number of iterations

Simanraj Sadana

The success probability of a search of $M$ targets from a database of size $N$, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as $\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of the optimal number of iterations when $\sqrt{M/N}$ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of $n$-qubit Grover's search algorithm with $1 \leq M \leq N$ target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given $N$ and $M$, there is an upper-bound on the success probability of the algorithm.

arXiv:2011.04051•Nov 8, 2020•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•0 citations

Complete 3-Qubit Grover search on a programmable quantum computer

Caroline Figgatt, Dmitri A Maslov, K. A. Landsman +3 more

The Grover quantum search algorithm is a hallmark application of a quantum computer with a well-known speedup over classical searches of an unsorted database. Here, we report results for a complete three-qubit Grover search algorithm using the scalable quantum computing technology of trapped atomic ions, with better-than-classical performance. Two methods of state marking are used for the oracles: a phase-flip method employed by other experimental demonstrations, and a Boolean method requiring an ancilla qubit that is directly equivalent to the state marking scheme required to perform a classical search. We also report the deterministic implementation of a Toffoli-4 gate, which is used along with Toffoli-3 gates to construct the algorithms; these gates have process fidelities of 70.5% and 89.6%, respectively.

arXiv:1703.10535•Nature Communications•Nov 28, 2017•235 citations
Abstract Quantum search algorithms have important applications in quantum information, which have been experimentally demonstrated in several quantum systems with database sizes up to 16. We first propose an efficient quantum search scheme based on an optimized Grover’s algorithm and a novel encoding method. With this scheme, a target element can be deterministically searched in a large database using only a single qubit. Then we implement this search scheme in linear optics with database sizes up to 40. Experimental results fit well with the theoretical results, with all fidelities greater than 99.7%. The limitation of the number of elements encoded in a single qubit is also investigated in the experiment. The experimental results indicate that a target state can be successfully searched from a database of size 36 using a single qubit in our laboratory. Since only one qubit and one-qubit gates are required, this search scheme is quite efficient and general, and can be adopted to implement the same task in most quantum systems.
The search algorithm is one of the most widely studied quantum algorithms, while its complete implementation in experiments is difficult and only a few experimental works have been reported. Based on Grover's algorithm, we propose a scheme of quantum search using nonorthogonal states and experimentally implement the entire scheme in a linear optical system. With this scheme, a large-sized search space can be encoded using only one qubit and the search probability of the target state is 100100%100 in theory. The experimental setup and the operations for implementing this scheme are extremely simple. In our linear optical experiment, different target states are successfully found from a database of nine elements with all fidelities >0.99>0.99>0.99, the state evolution from the initial state to a target state is studied, and the medium states and the final state are shown in a Bloch sphere. The scheme is general and can be easily realized in a wide range of quantum systems. This work may pave an avenue to implement quantum algorithms with nonorthogonal states.
Grover’s algorithm harnesses the power of quantum computing to swiftly locate specific elements in an unstructured database, outperforming classical computers in tasks like database searching. This algorithm capitalizes on the unique ability of qubits to be in both 0 and 1 states simultaneously (superposition), allowing it to scan the entire search space at once. It then boosts the probability of the target element, making it more prominent. While the foundational concepts of Grover’s algorithm are well-documented, practical implementation using quantum operators, especially for large search spaces, remains less explored beyond basic examples with a small number of qubits. Existing general synthesis techniques often involve numerous operators or are time-consuming. Our proposed methods specifically address the amplitude-amplification component of Grover’s algorithm for any size of search space. These methods detail the required types and quantities of qubits and operators, emphasizing minimal usage and efficient assembly. Developed and evaluated in Python, our methods consistently identified target elements with over 95% accuracy and achieved configurations comparably compact as those in the existing literature but at a faster pace. We anticipate that these methods facilitate practical implementations of Grover’s algorithm across various domains.
Grover's search algorithm is a well-known quantum algorithm that has been extensively studied and improved to increase its success rate and enhance its flexibility. However, most improved search algorithms require an adjustment of the oracle, which may not be feasible in practical problem-solving scenarios. In this work, we report an experimental demonstration of a deterministic quantum search for multiple marked states without adjusting the oracle. A linear optical setup is designed to search for two marked states, one in a 16-state database with an initial equal-superposition state and the other in an 8-state database with different initial nonequal-superposition states. The evolution of the probability of finding each state in the database is also measured and displayed. Our experimental results agree well with the theoretical predictions, thereby proving the feasibility of the search protocol and the implementation scheme. This work is a pioneering experimental demonstration of deterministic quantum search for multiple marked states without adjusting the oracle.
The success probability of a search of MMM targets from a database of size NNN, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as O(N)\mathcal{O}(\sqrt{N})O(N​) for large NNN, the asymptote is not a good indicator of the optimal number of iterations when M/N\sqrt{M/N}M/N​ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of nnn-qubit Grover's search algorithm with 1≤M≤N1 \leq M \leq N1≤M≤N target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given NNN and MMM, there is an upper-bound on the success probability of the algorithm.
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.
The Grover quantum search algorithm is a hallmark application of a quantum computer with a well-known speedup over classical searches of an unsorted database. Here, we report results for a complete three-qubit Grover search algorithm using the scalable quantum computing technology of trapped atomic ions, with better-than-classical performance. Two methods of state marking are used for the oracles: a phase-flip method employed by other experimental demonstrations, and a Boolean method requiring an ancilla qubit that is directly equivalent to the state marking scheme required to perform a classical search. We also report the deterministic implementation of a Toffoli-4 gate, which is used along with Toffoli-3 gates to construct the algorithms; these gates have process fidelities of 70.5% and 89.6%, respectively.