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:quant-ph/0110034 · Physical Review Letters

Implementation of Quantum Search Algorithm using Classical Fourier Optics

Nandini Bhattacharya, H. B. van Linden van den Heuvell, R. J. C. Spreeuw

Published Mar 12, 2002• 161 citations
arXivHTMLPDF

Abstract

We report on an experiment on Grover's quantum search algorithm showing that classical waves can search a N-item database as efficiently as quantum mechanics can. The transverse beam profile of a short laser pulse is processed iteratively as the pulse bounces back and forth between two mirrors. We directly observe the sought item being found in approximately square root[N] iterations, in the form of a growing intensity peak on this profile. Although the lack of quantum entanglement limits the size of our database, our results show that entanglement is neither necessary for the algorithm itself, nor for its efficiency.

DOI
10.1103/physrevlett.88.137901

Related papers

Optical Implementation of Grover’s Algorithm: It’s all Done with Mirrors

Paul G. Kwiat, Jay Mitchell, Peter D. D. Schwindt +1 more

The essential operations of a quantum computer can all be accomplished using only standard linear optical elements (e.g., beamsplitters, waveplates, polarizers, etc.), with the individual bits represented by different spatial orpolarization degrees of freedom. The difference from a genuine quantum computer with distinct entangleable registers is that the optical implementation requires a number of elements which grows exponentially with the number of bits. However, by “compiling” the code, and making multiple use of redundant components, the required number of elements can be substantially reduced, allowing the realization of quantum algorithms involving several bits. Here we present a simple optical implementation of Grover’s algorithm for efficiently searching a database. In our example a database of four elements is searched with a single query, in contrast to the classical expected value of 2.25 queries. It is seen that the “quantum” computer in this case is no more than an interferometer, albeit a complicated one. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Kluwer Academic Publishers eBooks•Dec 19, 2005•4 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

Enhanced Quantum Search via Partial Diffusion and Entanglement with Linear Optics

Ahmed S. El Fiky, Ahmed Younes, A. R. Abdulghany +2 more

Searching for specific items in an unstructured database presents a vital computational problem. While the best-known classical search algorithm in a database of size$N$has a complexity$\mathrm{O}(N)$, Grover's quantum search algorithm exhibits a complexity$\mathrm{O}(\sqrt{N})$, featuring a quadratic speed-up. In this paper, we present an optical system that implements an enhanced version of the search algorithm proposed by Younis et al. The system uses linear optical components such as beam splitters, phase shifters, and wave plates, along with a single-photon source and photodetectors.

National Radio Science Conference•May 6, 2025•0 citations

Tight Bounds on Quantum Searching

Michel Boyer, Gilles Brassard A, Peter Høyer +1 more

We provide a tight analysis of Grover's algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Finally, we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm comes within 2.62% of being optimal.

arXiv:quant-ph/9605034•Fortschritte der Physik•Jun 1, 1998•756 citations

Entanglement in the Grover's Search Algorithm

Shantanav Chakraborty, Subhashish Banerjee, Satyabrata Adhikari +1 more

Quantum Algorithms have long captured the imagination of computer scientists and physicists primarily because of the speed up achieved by them over their classical counterparts using principles of quantum mechanics. Entanglement is believed to be the primary phenomena behind this speed up. However their precise role in quantum algorithms is yet unclear. In this article, we explore the nature of entanglement in the Grover's search algorithm. This algorithm enables searching of elements from an unstructured database quadratically faster than the best known classical algorithm. Geometric measure of entanglement has been used to quantify and analyse entanglement across iterations of the algorithm. We reveal how the entanglement varies with increase in the number of qubits and also with the number of marked or solution states. Numerically, it is seen that the behaviour of the maximum value of entanglement is monotonous with the number of qubits. Also, for a given value of the number of qubits, a change in the marked states alters the amount of entanglement. The amount of entanglement in the final state of the algorithm has been shown to depend solely on the nature of the marked states. Explicit analytical expressions are given showing the variation of entanglement with the number of iterations and the global maximum value of entanglement attained across all iterations of the algorithm.

arXiv:1305.4454•May 20, 2013•9 citations

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•8 citations
We report on an experiment on Grover's quantum search algorithm showing that classical waves can search a N-item database as efficiently as quantum mechanics can. The transverse beam profile of a short laser pulse is processed iteratively as the pulse bounces back and forth between two mirrors. We directly observe the sought item being found in approximately square root[N] iterations, in the form of a growing intensity peak on this profile. Although the lack of quantum entanglement limits the size of our database, our results show that entanglement is neither necessary for the algorithm itself, nor for its efficiency.
The essential operations of a quantum computer can all be accomplished using only standard linear optical elements (e.g., beamsplitters, waveplates, polarizers, etc.), with the individual bits represented by different spatial orpolarization degrees of freedom. The difference from a genuine quantum computer with distinct entangleable registers is that the optical implementation requires a number of elements which grows exponentially with the number of bits. However, by “compiling” the code, and making multiple use of redundant components, the required number of elements can be substantially reduced, allowing the realization of quantum algorithms involving several bits. Here we present a simple optical implementation of Grover’s algorithm for efficiently searching a database. In our example a database of four elements is searched with a single query, in contrast to the classical expected value of 2.25 queries. It is seen that the “quantum” computer in this case is no more than an interferometer, albeit a complicated one. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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.
Searching for specific items in an unstructured database presents a vital computational problem. While the best-known classical search algorithm in a database of sizeNNNhas a complexityO(N)\mathrm{O}(N)O(N), Grover's quantum search algorithm exhibits a complexityO(N)\mathrm{O}(\sqrt{N})O(N​), featuring a quadratic speed-up. In this paper, we present an optical system that implements an enhanced version of the search algorithm proposed by Younis et al. The system uses linear optical components such as beam splitters, phase shifters, and wave plates, along with a single-photon source and photodetectors.
We provide a tight analysis of Grover's algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Finally, we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm comes within 2.62% of being optimal.
Quantum Algorithms have long captured the imagination of computer scientists and physicists primarily because of the speed up achieved by them over their classical counterparts using principles of quantum mechanics. Entanglement is believed to be the primary phenomena behind this speed up. However their precise role in quantum algorithms is yet unclear. In this article, we explore the nature of entanglement in the Grover's search algorithm. This algorithm enables searching of elements from an unstructured database quadratically faster than the best known classical algorithm. Geometric measure of entanglement has been used to quantify and analyse entanglement across iterations of the algorithm. We reveal how the entanglement varies with increase in the number of qubits and also with the number of marked or solution states. Numerically, it is seen that the behaviour of the maximum value of entanglement is monotonous with the number of qubits. Also, for a given value of the number of qubits, a change in the marked states alters the amount of entanglement. The amount of entanglement in the final state of the algorithm has been shown to depend solely on the nature of the marked states. Explicit analytical expressions are given showing the variation of entanglement with the number of iterations and the global maximum value of entanglement attained across all iterations of the algorithm.
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.