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/0012114 · Physical Review A

Implementation of a quantum algorithm to solve the Bernstein-Vazirani parity problem without entanglement on an ensemble quantum computer

Jiangfeng Du, Mingjun Shi, Xianyi Zhou, Yangmei Fan, Bangjiao Ye, Rongdian Han, Jihui Wu

Published Sep 11, 2001• 51 citations
arXivHTMLPDF

Abstract

Bernstein and Varizani have given the first quantum algorithm to solve the parity problem in which a strong violation of the classical information theoretic bound comes about. In this paper we refine this algorithm with fewer resources and implement a two-qubit algorithm in a single query on an ensemble quantum computer.
DOI
10.1103/physreva.64.042306

Related papers

A Generalization of Bernstein-Vazirani Algorithm to Qudit Systems

R Narayanan Krishna, Vishesh Makwana, Ananda Padhmanabhan Suresh

A quantum algorithm to solve the parity problem is better than its most efficient classical counter- part with a separation that is polynomial in the number of queries. This was shown by E. Bernstein and U. Vazirani and was one of the earliest indications that the quantum information processing can outperform the classical one by a significant margin. The problem and its solution both is usually stated for a 2-level system since we generally work with bits/qubits. However, many works have been done generalizing known quantum computing techniques to higher level systems. Following this, we look at a generalization of the Bernstein-Vazirani algorithm implemented on a general qudit system.

arXiv:1609.03185•Sep 11, 2016•5 citations

Single quantum querying of a database

Barbara M. Terhal, John A. Smolin

We present a class of fast quantum algorithms, based on Bernstein and Vazirani's parity problem, that retrieves the entire contents of a quantum database $Y$ in a single query. The class includes binary search problems and coin-weighing problems. We compare the efficiency of these quantum algorithms with the classical algorithms that are bounded by the classical information-theoretic bound. We show the connection between classical algorithms based on several compression codes and our quantum-mechanical method.

arXiv:quant-ph/9705041•Physical Review A•Sep 1, 1998•56 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

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

Quantum Algorithm for Finding Sets Intersection

Shengping Tian, Ping Wang, Xiaomei Chen

We propose a quantum algorithm to solve the intersection problem of two sets by extending Bernstein-Vazirani algorithm. Given set and set . In the classic algorithm, we need to query times to find the solution of set . However, in our quantum algorithm, we need only one quantum query to find the set .

International Conference on Intelligent Computing, Automation and Systems (ICICAS)•Dec 1, 2019•0 citations

Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm

Si-Qi Zhou, Jin-Min Liang, Jiayin Peng +3 more

Quantum entanglement and coherence are crucial resources in quantum information theory. In some scenarios, however, it is not necessary to directly estimate entanglement or coherence measures to quantify the capabilities of a state in quantum information processing. Instead, fully entangled fraction and coherence fraction are two alternatives for entanglement and coherence in specific quantum tasks. Here, we establish a link between the coherence fraction and the Bernstein-Vazirani algorithm, which has several potential applications including cryptography and database search. We show that the success probability of the generalized Bernstein-Vazirani algorithm depends only on the coherence fraction of the initial state rather than its entanglement or coherence. Moreover, we discuss the coherence fraction dynamics and establish a relation between the operator's coherence fraction and the algorithm's success probability. Our findings highlight how quantum coherence fraction influences the efficiency of quantum algorithms.

quant-pharXiv:2511.06845•Advanced Quantum Technologies•Nov 11, 2025•0 citations
A quantum algorithm to solve the parity problem is better than its most efficient classical counter- part with a separation that is polynomial in the number of queries. This was shown by E. Bernstein and U. Vazirani and was one of the earliest indications that the quantum information processing can outperform the classical one by a significant margin. The problem and its solution both is usually stated for a 2-level system since we generally work with bits/qubits. However, many works have been done generalizing known quantum computing techniques to higher level systems. Following this, we look at a generalization of the Bernstein-Vazirani algorithm implemented on a general qudit system.
We present a class of fast quantum algorithms, based on Bernstein and Vazirani's parity problem, that retrieves the entire contents of a quantum database YYY in a single query. The class includes binary search problems and coin-weighing problems. We compare the efficiency of these quantum algorithms with the classical algorithms that are bounded by the classical information-theoretic bound. We show the connection between classical algorithms based on several compression codes and our quantum-mechanical method.
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.
Quantum entanglement and coherence are crucial resources in quantum information theory. In some scenarios, however, it is not necessary to directly estimate entanglement or coherence measures to quantify the capabilities of a state in quantum information processing. Instead, fully entangled fraction and coherence fraction are two alternatives for entanglement and coherence in specific quantum tasks. Here, we establish a link between the coherence fraction and the Bernstein-Vazirani algorithm, which has several potential applications including cryptography and database search. We show that the success probability of the generalized Bernstein-Vazirani algorithm depends only on the coherence fraction of the initial state rather than its entanglement or coherence. Moreover, we discuss the coherence fraction dynamics and establish a relation between the operator's coherence fraction and the algorithm's success probability. Our findings highlight how quantum coherence fraction influences the efficiency of quantum algorithms.