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

Implementation of the Bernstein–Vazirani Quantum Algorithm on the IBM Q Computers

Sydney Wang, Athena Zheng

The complexity of certain classical computer algorithms can be reduced by a quantum algorithm completing the same task. We examine the implementation of the Bernstein–Vazirani algorithm. It finds the hidden n-bit string s from the function fs(x)=sx that takes an n-bit input string x and outputs one bit, the dot product. This algorithm reduces the complexity from n queries for the best classical algorithm to just one. Though the quantum algorithm theoretically always gives the correct string, in practice, factors such as decoherence of the physical qubits due to external noise reduce the algorithm’s accuracy. By implementing the algorithm on the IBM 5-qubit and 14-qubit quantum computers, we are able to analyze correlations between the accuracy of the results and the properties of the physical qubits used. Not all qubits are pairwise connected, nor do they have the same coherence times. Using Python to build the quantum circuits, we create several implementations of the circuit with different qubits. We establish that 1/T1, 1/T2, and gate errors are positively correlated with calculation errors. Consequently, we observe that the 14-qubit quantum computer, on average, is more prone to errors than the 5-qubit quantum computer.

•Jan 1, 2019•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

Deutsch-Jozsa and Bernstein-Vazirani algorithm using single-particle discrete-time quantum walk

Ravi Sangwan, Vikas Ramaswamy, Henry Sukumar +1 more

The paper introduces an efficient implementation of the Deutsch-Jozsa and Bernstein-Vazirani algorithm using the single-particle discrete-time quantum walk. We also provide a detailed optical framework with specific optical components to achieve these implementations in the photonic quantum walk scheme by simultaneously exploiting both polarization and path degrees of freedom. These implementations demonstrate improved resource efficiency while maintaining the exponential speedup characteristic of both algorithms. This work contributes to the growing field of universal quantum computing using singleparticle discrete-time quantum walk.

arXiv:2508.14659•IEEE International Conference on Electronics, Computing and Communication Technologies (CONECCT)•Jul 10, 2025•2 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.
The complexity of certain classical computer algorithms can be reduced by a quantum algorithm completing the same task. We examine the implementation of the Bernstein–Vazirani algorithm. It finds the hidden n-bit string s from the function fs(x)=sx that takes an n-bit input string x and outputs one bit, the dot product. This algorithm reduces the complexity from n queries for the best classical algorithm to just one. Though the quantum algorithm theoretically always gives the correct string, in practice, factors such as decoherence of the physical qubits due to external noise reduce the algorithm’s accuracy. By implementing the algorithm on the IBM 5-qubit and 14-qubit quantum computers, we are able to analyze correlations between the accuracy of the results and the properties of the physical qubits used. Not all qubits are pairwise connected, nor do they have the same coherence times. Using Python to build the quantum circuits, we create several implementations of the circuit with different qubits. We establish that 1/T1, 1/T2, and gate errors are positively correlated with calculation errors. Consequently, we observe that the 14-qubit quantum computer, on average, is more prone to errors than the 5-qubit quantum computer.
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.
The paper introduces an efficient implementation of the Deutsch-Jozsa and Bernstein-Vazirani algorithm using the single-particle discrete-time quantum walk. We also provide a detailed optical framework with specific optical components to achieve these implementations in the photonic quantum walk scheme by simultaneously exploiting both polarization and path degrees of freedom. These implementations demonstrate improved resource efficiency while maintaining the exponential speedup characteristic of both algorithms. This work contributes to the growing field of universal quantum computing using singleparticle discrete-time quantum walk.