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:2607.06033

Quantum Resources and Performance in the Initialization-Free Bernstein-Vazirani Algorithm

Haesol Han, Alexander Streltsov, Soojoon Lee

quant-phSubmitted Jul 7, 2026• Announced Jul 8, 2026• 0 citations
arXivHTMLPDF

Abstract

Naseri et al. [Phys. Rev. A 106, 062429 (2022); arXiv:2205.13610] studied which quantum resources in initial states are essential for the probabilistic Bernstein-Vazirani (BV) algorithm, defining its performance as the optimal average success probability over all measurements. In this work, we consider a variant of BV algorithm, which is called the initialization-free (IF) BV algorithm, in which an arbitrary ancilla state as the oracle register is allowed, to improve the performance. We derive an explicit formula for the performance of the probabilistic IF-BV algorithm and obtain a necessary and sufficient condition for an initial state to achieve maximal performance. We further prove that, under a suitable ordering assumption on the coefficients of the initial state, the probabilistic IF-BV algorithm outperforms the standard probabilistic BV algorithm.

Comments
10 pages, no figures; includes appendix

Related papers

Generalization of the Bernstein–Vazirani algorithm beyond qubit systems

Koji Nagata, Han J.F. Geurdes, Santanu Kumar Patro +3 more

Quantum Studies Mathematics and Foundations•May 20, 2019•8 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

Effects of noise on performance of Bernstein-Vazirani algorithm

Gupta, Archi, Priya Ghosh, Kornikar Sen +1 more

The Bernstein-Vazirani (BV) algorithm offers exceptional accuracy in finding the hidden bit string of a function. We explore how the algorithm performs in real-world situations where noise can potentially interfere with its performance. In order to assess the impact of imperfect equipments, we introduce various forms of glassy disorders into the effect of the Hadamard gates used in the Bernstein-Vazirani circuit. We incorporated disorders of five different forms, viz., Haar-uniform with finite cutoff, spherical Gaussian, discrete circular, spherical Cauchy-Lorentz, and squeezed. We find that the effectiveness of the algorithm decreases with increasing disorder strength in all cases. Additionally, we demonstrate that as the number of bits in the secret string increases, the success probability of correctly guessing the string becomes increasingly insensitive to the type of disorder and instead depends only on the mean and spread of the disorder. We compare our results with the performance of the analogous classical algorithm in the presence of similar noise. When the length of the secret string is small or moderate, the quantum BV algorithm is found to be more efficient compared to the classical algorithm for almost all types of disorders under consideration, unless the strength of the disorder is very high and the disorder follows a discrete circular distribution. However, if we move to extremely large secret strings, the success probability of the disordered BV algorithm merges with the success probability of the disordered classical algorithm for all considered disorders having arbitrary strengths. The limit on the length of the string after which the efficiency of the quantum algorithm becomes equivalent to the classical algorithm depends on the amount of disorder and not on the type of disorder.

arXiv:2305.19745•May 31, 2023•3 citations

Quantum Algorithms for Simulation, Optimization, and Estimation

Dhrumilkumar Patel

344 pages

•Apr 3, 2026•0 citations

Quantum State Probability Distribution Optimization Algorithm

Jincheng Zhang

Quantum State Probability Distribution Optimization Algorithm

•Sep 4, 2026•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
Naseri et al. [Phys. Rev. A 106, 062429 (2022); arXiv:2205.13610] studied which quantum resources in initial states are essential for the probabilistic Bernstein-Vazirani (BV) algorithm, defining its performance as the optimal average success probability over all measurements. In this work, we consider a variant of BV algorithm, which is called the initialization-free (IF) BV algorithm, in which an arbitrary ancilla state as the oracle register is allowed, to improve the performance. We derive an explicit formula for the performance of the probabilistic IF-BV algorithm and obtain a necessary and sufficient condition for an initial state to achieve maximal performance. We further prove that, under a suitable ordering assumption on the coefficients of the initial state, the probabilistic IF-BV algorithm outperforms the standard probabilistic BV algorithm.
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 Bernstein-Vazirani (BV) algorithm offers exceptional accuracy in finding the hidden bit string of a function. We explore how the algorithm performs in real-world situations where noise can potentially interfere with its performance. In order to assess the impact of imperfect equipments, we introduce various forms of glassy disorders into the effect of the Hadamard gates used in the Bernstein-Vazirani circuit. We incorporated disorders of five different forms, viz., Haar-uniform with finite cutoff, spherical Gaussian, discrete circular, spherical Cauchy-Lorentz, and squeezed. We find that the effectiveness of the algorithm decreases with increasing disorder strength in all cases. Additionally, we demonstrate that as the number of bits in the secret string increases, the success probability of correctly guessing the string becomes increasingly insensitive to the type of disorder and instead depends only on the mean and spread of the disorder. We compare our results with the performance of the analogous classical algorithm in the presence of similar noise. When the length of the secret string is small or moderate, the quantum BV algorithm is found to be more efficient compared to the classical algorithm for almost all types of disorders under consideration, unless the strength of the disorder is very high and the disorder follows a discrete circular distribution. However, if we move to extremely large secret strings, the success probability of the disordered BV algorithm merges with the success probability of the disordered classical algorithm for all considered disorders having arbitrary strengths. The limit on the length of the string after which the efficiency of the quantum algorithm becomes equivalent to the classical algorithm depends on the amount of disorder and not on the type of disorder.
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.