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

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

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

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

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

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

FPGA Acceleration of Quantum Circuit Primitives: Fixed-Point Microcoded Design and CPU Comparison

Shahriar Rizvi, Md. Nazrul Islam Mondal

Quantum algorithms such as the Quantum Fourier Transform (QFT), Grover’s Search, the Bernstein–Vazirani (BV) algorithm, and Bell-state generation are computationally intensive to emulate on classical processors due to the exponential growth of state vectors. This work presents a fixed-point, microcoded FPGA accelerator that achieves deterministic timing, near-unit fidelity, and linear scalability up to 4 qubits. The design features a microcoded control plane with pairwise and diagonal opcodes, fixed-point complex arithmetic, and subspace-gated execution (qubit0= LSB). We benchmark QFT(2–4), BV(2–4), Grover(4), and Bell(2) at 100 MHz and compare against equivalent CPU state-vector simulations. Across all algorithms, the FPGA demonstrates consistent latency reduction: QFT: 88×–154× (98.9–99.4% faster), BV: 54×–90× (98.1–98.9% faster), Bell: 282× (99.6% faster), and Grover-4: 14.2× (93.0% faster). Fidelity is near-unit for all programs except a single BV-2 run that yields 0.875 ; QFT, Bell, BV-3, BV-4 and Grover-4 achieve 1.000. Latency scales linearly with qubit count—growing by ~1.8× per additional qubit for QFT and ~1.6× for BV—confirming the deterministic and cycle-predictable nature of the microcoded architecture. Results reflect 100 MHz RTL simulation (Verilator); we report synthesis resources and post-P&R Fmax, and express speedups normalized to 100 MHz. These results show that even a modest FPGA can outperform our CPU state-vector baseline on small-n kernels while preserving deterministic, cycle-accurate timing for small-to-medium quantum workloads through spatial parallelism and hardware-level determinism.

International Conference on Electrical, Computer & Telecommunication Engineering (ICECTE)•Jan 29, 2026•0 citations

EFFICIENT ALGORITHM FOR INITIALIZING AMPLITUDE DISTRIBUTION OF A QUANTUM REGISTER

M. Andrecut, Mazhar Ali

The preparation of a quantum register in an arbitrary superposed quantum state is an important operation for quantum computation and quantum information processing. Here, we present an efficient algorithm which requires a polynomial number of elementary operations for initializing the amplitude distribution of a quantum register.

Modern Physics Letters B•Nov 20, 2001•4 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.
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.
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?
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 algorithms such as the Quantum Fourier Transform (QFT), Grover’s Search, the Bernstein–Vazirani (BV) algorithm, and Bell-state generation are computationally intensive to emulate on classical processors due to the exponential growth of state vectors. This work presents a fixed-point, microcoded FPGA accelerator that achieves deterministic timing, near-unit fidelity, and linear scalability up to 4 qubits. The design features a microcoded control plane with pairwise and diagonal opcodes, fixed-point complex arithmetic, and subspace-gated execution (qubit0= LSB). We benchmark QFT(2–4), BV(2–4), Grover(4), and Bell(2) at 100 MHz and compare against equivalent CPU state-vector simulations. Across all algorithms, the FPGA demonstrates consistent latency reduction: QFT: 88×–154× (98.9–99.4% faster), BV: 54×–90× (98.1–98.9% faster), Bell: 282× (99.6% faster), and Grover-4: 14.2× (93.0% faster). Fidelity is near-unit for all programs except a single BV-2 run that yields 0.875 ; QFT, Bell, BV-3, BV-4 and Grover-4 achieve 1.000. Latency scales linearly with qubit count—growing by ~1.8× per additional qubit for QFT and ~1.6× for BV—confirming the deterministic and cycle-predictable nature of the microcoded architecture. Results reflect 100 MHz RTL simulation (Verilator); we report synthesis resources and post-P&R Fmax, and express speedups normalized to 100 MHz. These results show that even a modest FPGA can outperform our CPU state-vector baseline on small-n kernels while preserving deterministic, cycle-accurate timing for small-to-medium quantum workloads through spatial parallelism and hardware-level determinism.