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/0605092 · Journal of the Optical Society of America B

Optical implementations, oracle equivalence, and the Bernstein-Vazirani algorithm

Arvind, Gurpreet Kaur, Geetu Narang

Published Jan 26, 2007• 12 citations
arXivHTMLPDF

Abstract

We describe a new implementation of the Bernstein-Vazirani algorithm that relies on the fact that the polarization states of classical light beams can be cloned. We explore the possibility of computing with waves and discuss a classical optical model capable of implementing any algorithm (on n qubits) that does not involve entanglement. The Bernstein-Vazirani algorithm (with a suitably modified oracle), wherein a hidden n-bit vector is discovered by one oracle query as against n oracle queries required classically, belongs to this category. In our scheme, the modified oracle is also capable of computing f(x) for a given x, which is not possible with earlier versions used in recent NMR and optics implementations of the algorithm.

DOI
10.1364/josab.24.000221

Related papers

Efficient optical implementation of the Bernstein-Vazirani algorithm

Pablo Londero, Christophe Dorrer, Matthew E. Anderson +3 more

We implement the Bernstein-Vazirani algorithm on a 15-bit register encoding ${2}^{15}$ elements using optics. The algorithm provides a polynomial speed up for oracle queries. The apparatus is physically efficient in that its size (i.e., space-time volume) scales linearly with the size (i.e., number of digits) of the register. We demonstrate also that the algorithm may be performed not only without entanglement, but also with a computational basis that does not consist of orthogonal states, and that this coding is the source of the efficiency of the algorithm.

Physical Review A•Jan 9, 2004•11 citations

Quantum oracles and the optical Bernstein-Vazirani algorithm

Ian A. Walmsley, Pablo Londero, Christophe Dorrer +3 more

We implement the Bernstein-Vazirani algorithm on a 15-bit register encoding 215-1 elements using optics. The apparatus is efficient in that the physical size of the apparatus scales linearly with the size (i.e. number of digits) of the register. We demonstrate also that the algorithm may be performed not only without entanglement, as Meyer has indicated, but also with a computational basis that does not consist of orthogonal states, and that this coding is the source of the efficiency of the algorithm. This raises several questions: is this the only algorithm that makes use of these simplifying features, or do all quantum Oracles in fact require exponential resources for their construction?

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Nov 18, 2003•0 citations

Entanglement and coherence in the Bernstein-Vazirani algorithm

Moein Naseri, Tulja Varun Kondra, Suchetana Goswami +2 more

Quantum algorithms can outperform their classical counterparts in various tasks, the most prominent example being Shor's algorithm for efficient prime factorization on a quantum computer. It is clear that one of the reasons for the speedup is the superposition principle of quantum mechanics, which allows a quantum processor to be in a superposition of different states at the same time. While such a superposition can lead to entanglement across different qubits of the processors, there also exist quantum algorithms that outperform classical ones using superpositions of individual qubits without entangling them. As an example, the Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. While the classical version of the algorithm requires multiple calls of the oracle to learn the bit string, a single query of the oracle is enough in the quantum case. In this article, we analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. For this, we introduce and study its probabilistic version, where the goal is to guess the bit string after a single call of the oracle. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state. We further demonstrate that a large amount of entanglement in the initial state prevents the algorithm from achieving optimal performance. We also apply our methods to quantum computation with mixed states, proving that pseudopure states achieve optimal performance for a given purity in the Bernstein-Vazirani algorithm. We further investigate quantum resources in the one clean qubit model, showing that the model can exhibit speedup over any known classical algorithm even with an arbitrarily little amount of multipartite entanglement, general quantum correlations, and coherence.

arXiv:2205.13610•Physical Review A•Dec 21, 2022•35 citations

Quantum Query Algorithms

Walid E. Gomaa

This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.

•Nov 19, 2025•0 citations

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

"Spectral Implementation" for creating pseudo-pure states and a three-qubit Bernstein-Vazirani's algorithm in NMR

Xinhua Peng, Xiwen Zhu, Ximing Fang +3 more

Based on ''spectral implementation'' proposed by Madi et al. (J. Chem. Phys. 109, 10603, 1998), we have experimentally realized a pseudo-pure state by the line-selective excitation and a three-qubit Bernstein-Vazirani's algorithm using a carbon-13 analine sample in NMR. The superiority of quantum computation to classical counterpart is well displayed.

•Feb 1, 2002•0 citations
We describe a new implementation of the Bernstein-Vazirani algorithm that relies on the fact that the polarization states of classical light beams can be cloned. We explore the possibility of computing with waves and discuss a classical optical model capable of implementing any algorithm (on n qubits) that does not involve entanglement. The Bernstein-Vazirani algorithm (with a suitably modified oracle), wherein a hidden n-bit vector is discovered by one oracle query as against n oracle queries required classically, belongs to this category. In our scheme, the modified oracle is also capable of computing f(x) for a given x, which is not possible with earlier versions used in recent NMR and optics implementations of the algorithm.
We implement the Bernstein-Vazirani algorithm on a 15-bit register encoding 215{2}^{15}215 elements using optics. The algorithm provides a polynomial speed up for oracle queries. The apparatus is physically efficient in that its size (i.e., space-time volume) scales linearly with the size (i.e., number of digits) of the register. We demonstrate also that the algorithm may be performed not only without entanglement, but also with a computational basis that does not consist of orthogonal states, and that this coding is the source of the efficiency of the algorithm.
We implement the Bernstein-Vazirani algorithm on a 15-bit register encoding 215-1 elements using optics. The apparatus is efficient in that the physical size of the apparatus scales linearly with the size (i.e. number of digits) of the register. We demonstrate also that the algorithm may be performed not only without entanglement, as Meyer has indicated, but also with a computational basis that does not consist of orthogonal states, and that this coding is the source of the efficiency of the algorithm. This raises several questions: is this the only algorithm that makes use of these simplifying features, or do all quantum Oracles in fact require exponential resources for their construction?
Quantum algorithms can outperform their classical counterparts in various tasks, the most prominent example being Shor's algorithm for efficient prime factorization on a quantum computer. It is clear that one of the reasons for the speedup is the superposition principle of quantum mechanics, which allows a quantum processor to be in a superposition of different states at the same time. While such a superposition can lead to entanglement across different qubits of the processors, there also exist quantum algorithms that outperform classical ones using superpositions of individual qubits without entangling them. As an example, the Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. While the classical version of the algorithm requires multiple calls of the oracle to learn the bit string, a single query of the oracle is enough in the quantum case. In this article, we analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. For this, we introduce and study its probabilistic version, where the goal is to guess the bit string after a single call of the oracle. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state. We further demonstrate that a large amount of entanglement in the initial state prevents the algorithm from achieving optimal performance. We also apply our methods to quantum computation with mixed states, proving that pseudopure states achieve optimal performance for a given purity in the Bernstein-Vazirani algorithm. We further investigate quantum resources in the one clean qubit model, showing that the model can exhibit speedup over any known classical algorithm even with an arbitrarily little amount of multipartite entanglement, general quantum correlations, and coherence.
This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.
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.