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

Optics Letters

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

Xin He, Wentao Zhao, Wang-Chu Lv, Chen-Hui Peng, Zhe Sun, Yong-Nan Sun, Qi-Ping Su, Chui‐Ping Yang

Published Aug 1, 2023• 4 citations
Publisher

Abstract

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.

DOI
10.1364/ol.497599

Related papers

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•0 citations

Implementing a deterministic search algorithm with a single qubit

Chen-Hui Peng, Liang Bin, Xin He +3 more

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.

Progress of Theoretical and Experimental Physics•Mar 1, 2023•1 citation

A Non-Oracle Quantum Search Algorithm and Its Experimental Implementation

Nanyang Xu, Zhu Jin, Xinhua Peng +2 more

Grover's algorithm has achieved great success. But quantum search algorithms still are not complete algorithms because of Grover's Oracle. We concerned on this problem and present a new quantum search algorithm in adiabatic model without Oracle. We analyze the general difficulties in quantum search algorithms and show how to solve them in the present algorithm. As well this algorithm could deal with both single-solution and multi-solution searches without modification. We also implement this algorithm on NMR quantum computer. It is the first experiment which perform a real quantum database search rather than a marked-state search.

arXiv:0809.0664•Sep 3, 2008•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

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

Near‐Deterministic Quantum Search Algorithm Without Phase Design

Zhen Wang, Kun Zhang, V. E. Korepin

Abstract Grover's algorithm solves the unstructured search problem. Grover's algorithm can find the target state with certainty only if searching one out of four. Designing the deterministic search algorithm can avoid any repetition of the algorithm, especially when Grover's algorithm is a subroutine in other algorithms. Grover's algorithm can be deterministic if the phase of the oracle or the diffusion operator is delicately designed. The precision of the phases could be a problem. A near‐deterministic quantum search algorithm without the phase design is proposed. The algorithm has the same oracle and diffusion operators as Grover's algorithm. One additional component is the rescaled diffusion operator. It acts partially on the database. The success probability of Grover's algorithm is improved by the partial diffusion operator in two different ways. The possible cost is one or two more queries to the oracle. The deterministic search algorithm is also designed when searching one out of eight, sixteen, and thirty‐two.

arXiv:2407.10748•Advanced Quantum Technologies•Jan 3, 2025•3 citations
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.
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%.
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.
Grover's algorithm has achieved great success. But quantum search algorithms still are not complete algorithms because of Grover's Oracle. We concerned on this problem and present a new quantum search algorithm in adiabatic model without Oracle. We analyze the general difficulties in quantum search algorithms and show how to solve them in the present algorithm. As well this algorithm could deal with both single-solution and multi-solution searches without modification. We also implement this algorithm on NMR quantum computer. It is the first experiment which perform a real quantum database search rather than a marked-state search.
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 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.
Abstract Grover's algorithm solves the unstructured search problem. Grover's algorithm can find the target state with certainty only if searching one out of four. Designing the deterministic search algorithm can avoid any repetition of the algorithm, especially when Grover's algorithm is a subroutine in other algorithms. Grover's algorithm can be deterministic if the phase of the oracle or the diffusion operator is delicately designed. The precision of the phases could be a problem. A near‐deterministic quantum search algorithm without the phase design is proposed. The algorithm has the same oracle and diffusion operators as Grover's algorithm. One additional component is the rescaled diffusion operator. It acts partially on the database. The success probability of Grover's algorithm is improved by the partial diffusion operator in two different ways. The possible cost is one or two more queries to the oracle. The deterministic search algorithm is also designed when searching one out of eight, sixteen, and thirty‐two.