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

Noise Thresholds for Quantum Advantage in the Bernstein-Vazirani and Deutsch-Jozsa Algorithms

Muhammad Faizan, Muhammad Faryad

Published Aug 3, 2025• 0 citations
arXivHTMLPDF

Abstract

We analytically investigate the robustness of the Bernstein-Vazirani and Deutsch-Jozsa algorithms against single-qubit Pauli noise, of which bit-flip, phase-flip, and depolarizing noise are special cases, using the density-matrix formalism. For a general Pauli channel acting on each qubit after every gate, we derive exact closed-form expressions for the success probability of a single run as a function of the error probabilities and the number of qubits $n$, and validate them against Qiskit simulations. The noise enters only through the probability $\varepsilon$ with which each output bit is flipped. Under bit-flip noise with error probability $p > 1/2$ the most probable outcome of the Bernstein-Vazirani algorithm is the complement of the correct one, which classical post-processing corrects, whereas depolarizing and phase-flip noise never bias the output toward a wrong outcome. For the Deutsch-Jozsa algorithm, the success probability is the average over constant and balanced oracles, and the results are given for the single-variable balanced oracle, which is shown to be the least robust of all balanced oracles for $\varepsilon < 1/2$. For a single run, the tolerable error probability of both algorithms decreases as $1/n$. We then determine the minimum number of repetitions required for a given confidence and compare it with the number of queries of the classical algorithms. The threshold error probability below which the noisy Bernstein-Vazirani algorithm retains its query advantage increases with $n$, whereas that of the Deutsch-Jozsa algorithm with its standard readout decreases as $1/n$. This contrast indicates that algorithms whose answer is encoded in many independently decodable output bits are considerably more robust to noise than algorithms whose verdict depends on a single global outcome.

DOI
10.48550/arxiv.2508.01884

Related papers

Noise Sensitivity of Deutsch's Quantum Algorithm

Jiarui Shang

Noise accumulation remains a central limitation on the reliable execution of quantum algorithms. This study analyzes the sensitivity of Deutsch’s algorithm to global depolarizing noise using the density-matrix formalism. First, a general analytical expression is derived for the success probability of a quantum circuit subjected to repeated depolarizing channels. The expression relates algorithmic performance to the ideal success probability, the rank of the success projector, and the cumulative contraction factor across circuit layers. The framework is then applied to the two-qubit Deutsch circuit, with a global depolarizing channel introduced after each of its three effective unitary layers. This yields the closed-form success probability PD(λ)=(1+λ3)/2, where λ denotes the survival parameter of the channel. The analytical result is numerically verified in MATLAB for all four Boolean oracles over 404 parameter–oracle combinations. The maximum discrepancy between the analytical and numerical probabilities is 6.661×10-16, while the maximum trace error is 7.772×10-16, indicating agreement within double-precision floating-point accuracy. The results demonstrate how repeated global depolarization progressively reduces the ideal contribution to the output state and drives the classification probability toward the random-guessing limit. Although the model does not represent hardware-specific noise, it provides an exactly solvable benchmark for studying cumulative noise effects in elementary quantum circuits.

International Journal of Applied Science•Sep 29, 2026•0 citations

The Impact of Logical Errors on Quantum Algorithms

Omer Subasi, Sriram Krishnamoorthy

In this work, we explore the impact of logical stochastic Pauli and coherent Z-rotation errors on quantum algorithms. We evaluate six canonical quantum algorithms' intrinsic resilience to the logical qubit and gate errors by performing the Monte Carlo simulations guided by the quantum jump formalism. The results suggest that the resilience of the studied quantum algorithms decreases as the number of qubits and the depth of the algorithms' circuits increase for both Pauli and Z-rotation errors. Our results also suggest that the algorithms split into two different groups in terms of algorithmic resilience. The evolution of Hamiltonian, Simon and the quantum phase estimation algorithms are less resilient to logical errors than Grover's search, Deutsch-Jozsa and Bernstein-Vazirani algorithms.

arXiv:2111.03733•Nov 5, 2021•1 citation

Biased-noise qubits: a guide to efficient fault-tolerance using the hierarchy of errors

Diego Ruiz, Jérémie Guillaud, Christophe Vuillot +1 more

Qubits with strongly biased noise, in which phase-flip errors are orders of magnitude more frequent than bit-flips, arise both naturally, as in electron and nuclear spins, and by engineering, as in stabilized cat qubits. This noise structure holds the promise of reducing the daunting hardware overhead of fault-tolerant quantum computing, but exploiting it requires physical operations that do not convert frequent phase-flips into rare bit-flips. In this review, we analyze the most prominent fault-tolerant protocols for biased-noise qubits, organized according to the available set of such bias-preserving operations. When this set is restricted to the CZ gate together with preparation and measurement in the X basis, we show that the complexity of the required syndrome extraction gadgets essentially cancels the benefit of the noise bias: at experimentally relevant error rates, one may as well ignore the bias and rely on standard error correction designed for depolarizing noise. The situation changes drastically when a bias-preserving CX gate is available: the hierarchy of errors can then be reflected in the structure of the code, with frequent phase-flips corrected by a dedicated high-threshold code and rare bit-flips by concatenation with a high-rate code. The same hierarchy also enables hardware-efficient preparation of magic states. Finally, as a bias-preserving CX is forbidden in naturally biased platforms and challenging in engineered ones, we present a measurement-based architecture in which a high-fidelity quantum non-demolition readout of multi-qubit Pauli Z operators takes its place, extending these overhead reductions to a much broader range of physical platforms.

quant-pharXiv:2607.20143•Jul 23, 2026•0 citations

Invariance of success probability in Grover's quantum search under local noise with memory

Sheikh Parvez Mandal, Ahana Ghoshal, Chirag Srivastava +1 more

We analyze the robustness of Grover's quantum search algorithm performed by a quantum register under a possibly time-correlated noise acting locally on the qubits. We model the noise as originating from an arbitrary but fixed unitary evolution $U$ of some noisy qubits. The noise can occur with some probability in the interval between any pair of consecutive noiseless Grover evolutions. Although each run of the algorithm is a unitary process, the noise model leads to decoherence when all possible runs are considered. We derive a set of unitary $U$'s, called good noises, for which the success probability of the algorithm at any given time remains unchanged with varying nontrivial total number $m$ of noisy qubits in the register. The result holds irrespective of the presence of any time correlations in the noise. We show that only when $U$ is either of the Pauli matrices ${\ensuremath{\sigma}}_{x}$ and ${\ensuremath{\sigma}}_{z}$ (which give rise to $m$-qubit bit-flip and phase-damping channels, respectively, in the time-correlation-less case), the algorithm's success probability stays unchanged when increasing or decreasing $m$. In contrast, when $U$ is the Pauli matrix ${\ensuremath{\sigma}}_{y}$ (giving rise to $m$-qubit bit-phase flip channel in the time-correlation-less case), the success probability at all times stays unaltered as long as the parity (even or odd) of the total number $m$ remains the same. This asymmetry between the Pauli operators stems from the inherent symmetry-breaking existing within the Grover circuit. We further show that the positions of the noisy sites are irrelevant in the case of any of the Pauli noises. The results are illustrated in the cases of time-correlated and time-correlation-less noise. We find that the former case leads to a better performance of the noisy algorithm. We also discuss physical scenarios where our chosen noise model is of relevance.

arXiv:2112.02640•Physical Review A•Feb 21, 2023•2 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

Hard decoding algorithm for optimizing thresholds under general Markovian noise

Christopher Chamberland, Joel J. Wallman, Stefanie J. Beale +1 more

Quantum error correction is instrumental in protecting quantum systems from noise in quantum computing and communication settings. Pauli channels can be efficiently simulated and threshold values for Pauli error rates under a variety of error-correcting codes have been obtained. However, realistic quantum systems can undergo noise processes that differ significantly from Pauli noise. In this paper, we present an efficient hard decoding algorithm for optimizing thresholds and lowering failure rates of an error-correcting code under general completely positive and trace-preserving (i.e., Markovian) noise. We use our hard decoding algorithm to study the performance of several error-correcting codes under various non-Pauli noise models by computing threshold values and failure rates for these codes. We compare the performance of our hard decoding algorithm to decoders optimized for depolarizing noise and show improvements in thresholds and reductions in failure rates by several orders of magnitude. Our hard decoding algorithm can also be adapted to take advantage of a code's non-Pauli transversal gates to further suppress noise. For example, we show that using the transversal gates of the 5-qubit code allows arbitrary rotations around certain axes to be perfectly corrected. Furthermore, we show that Pauli twirling can increase or decrease the threshold depending upon the code properties. Lastly, we show that even if the physical noise model differs slightly from the hypothesized noise model used to determine an optimized decoder, failure rates can still be reduced by applying our hard decoding algorithm.

arXiv:1612.02830•Physical Review A•Apr 21, 2017•36 citations
We analytically investigate the robustness of the Bernstein-Vazirani and Deutsch-Jozsa algorithms against single-qubit Pauli noise, of which bit-flip, phase-flip, and depolarizing noise are special cases, using the density-matrix formalism. For a general Pauli channel acting on each qubit after every gate, we derive exact closed-form expressions for the success probability of a single run as a function of the error probabilities and the number of qubits nnn, and validate them against Qiskit simulations. The noise enters only through the probability ε\varepsilonε with which each output bit is flipped. Under bit-flip noise with error probability p>1/2p > 1/2p>1/2 the most probable outcome of the Bernstein-Vazirani algorithm is the complement of the correct one, which classical post-processing corrects, whereas depolarizing and phase-flip noise never bias the output toward a wrong outcome. For the Deutsch-Jozsa algorithm, the success probability is the average over constant and balanced oracles, and the results are given for the single-variable balanced oracle, which is shown to be the least robust of all balanced oracles for ε<1/2\varepsilon < 1/2ε<1/2. For a single run, the tolerable error probability of both algorithms decreases as 1/n1/n1/n. We then determine the minimum number of repetitions required for a given confidence and compare it with the number of queries of the classical algorithms. The threshold error probability below which the noisy Bernstein-Vazirani algorithm retains its query advantage increases with nnn, whereas that of the Deutsch-Jozsa algorithm with its standard readout decreases as 1/n1/n1/n. This contrast indicates that algorithms whose answer is encoded in many independently decodable output bits are considerably more robust to noise than algorithms whose verdict depends on a single global outcome.
Noise accumulation remains a central limitation on the reliable execution of quantum algorithms. This study analyzes the sensitivity of Deutsch’s algorithm to global depolarizing noise using the density-matrix formalism. First, a general analytical expression is derived for the success probability of a quantum circuit subjected to repeated depolarizing channels. The expression relates algorithmic performance to the ideal success probability, the rank of the success projector, and the cumulative contraction factor across circuit layers. The framework is then applied to the two-qubit Deutsch circuit, with a global depolarizing channel introduced after each of its three effective unitary layers. This yields the closed-form success probability PD(λ)=(1+λ3)/2, where λ denotes the survival parameter of the channel. The analytical result is numerically verified in MATLAB for all four Boolean oracles over 404 parameter–oracle combinations. The maximum discrepancy between the analytical and numerical probabilities is 6.661×10-16, while the maximum trace error is 7.772×10-16, indicating agreement within double-precision floating-point accuracy. The results demonstrate how repeated global depolarization progressively reduces the ideal contribution to the output state and drives the classification probability toward the random-guessing limit. Although the model does not represent hardware-specific noise, it provides an exactly solvable benchmark for studying cumulative noise effects in elementary quantum circuits.
In this work, we explore the impact of logical stochastic Pauli and coherent Z-rotation errors on quantum algorithms. We evaluate six canonical quantum algorithms' intrinsic resilience to the logical qubit and gate errors by performing the Monte Carlo simulations guided by the quantum jump formalism. The results suggest that the resilience of the studied quantum algorithms decreases as the number of qubits and the depth of the algorithms' circuits increase for both Pauli and Z-rotation errors. Our results also suggest that the algorithms split into two different groups in terms of algorithmic resilience. The evolution of Hamiltonian, Simon and the quantum phase estimation algorithms are less resilient to logical errors than Grover's search, Deutsch-Jozsa and Bernstein-Vazirani algorithms.
Qubits with strongly biased noise, in which phase-flip errors are orders of magnitude more frequent than bit-flips, arise both naturally, as in electron and nuclear spins, and by engineering, as in stabilized cat qubits. This noise structure holds the promise of reducing the daunting hardware overhead of fault-tolerant quantum computing, but exploiting it requires physical operations that do not convert frequent phase-flips into rare bit-flips. In this review, we analyze the most prominent fault-tolerant protocols for biased-noise qubits, organized according to the available set of such bias-preserving operations. When this set is restricted to the CZ gate together with preparation and measurement in the X basis, we show that the complexity of the required syndrome extraction gadgets essentially cancels the benefit of the noise bias: at experimentally relevant error rates, one may as well ignore the bias and rely on standard error correction designed for depolarizing noise. The situation changes drastically when a bias-preserving CX gate is available: the hierarchy of errors can then be reflected in the structure of the code, with frequent phase-flips corrected by a dedicated high-threshold code and rare bit-flips by concatenation with a high-rate code. The same hierarchy also enables hardware-efficient preparation of magic states. Finally, as a bias-preserving CX is forbidden in naturally biased platforms and challenging in engineered ones, we present a measurement-based architecture in which a high-fidelity quantum non-demolition readout of multi-qubit Pauli Z operators takes its place, extending these overhead reductions to a much broader range of physical platforms.
We analyze the robustness of Grover's quantum search algorithm performed by a quantum register under a possibly time-correlated noise acting locally on the qubits. We model the noise as originating from an arbitrary but fixed unitary evolution UUU of some noisy qubits. The noise can occur with some probability in the interval between any pair of consecutive noiseless Grover evolutions. Although each run of the algorithm is a unitary process, the noise model leads to decoherence when all possible runs are considered. We derive a set of unitary UUU's, called good noises, for which the success probability of the algorithm at any given time remains unchanged with varying nontrivial total number mmm of noisy qubits in the register. The result holds irrespective of the presence of any time correlations in the noise. We show that only when UUU is either of the Pauli matrices ${\ensuremath{\sigma}}_{x}$ and ${\ensuremath{\sigma}}_{z}$ (which give rise to mmm-qubit bit-flip and phase-damping channels, respectively, in the time-correlation-less case), the algorithm's success probability stays unchanged when increasing or decreasing mmm. In contrast, when UUU is the Pauli matrix ${\ensuremath{\sigma}}_{y}$ (giving rise to mmm-qubit bit-phase flip channel in the time-correlation-less case), the success probability at all times stays unaltered as long as the parity (even or odd) of the total number mmm remains the same. This asymmetry between the Pauli operators stems from the inherent symmetry-breaking existing within the Grover circuit. We further show that the positions of the noisy sites are irrelevant in the case of any of the Pauli noises. The results are illustrated in the cases of time-correlated and time-correlation-less noise. We find that the former case leads to a better performance of the noisy algorithm. We also discuss physical scenarios where our chosen noise model is of relevance.
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.
Quantum error correction is instrumental in protecting quantum systems from noise in quantum computing and communication settings. Pauli channels can be efficiently simulated and threshold values for Pauli error rates under a variety of error-correcting codes have been obtained. However, realistic quantum systems can undergo noise processes that differ significantly from Pauli noise. In this paper, we present an efficient hard decoding algorithm for optimizing thresholds and lowering failure rates of an error-correcting code under general completely positive and trace-preserving (i.e., Markovian) noise. We use our hard decoding algorithm to study the performance of several error-correcting codes under various non-Pauli noise models by computing threshold values and failure rates for these codes. We compare the performance of our hard decoding algorithm to decoders optimized for depolarizing noise and show improvements in thresholds and reductions in failure rates by several orders of magnitude. Our hard decoding algorithm can also be adapted to take advantage of a code's non-Pauli transversal gates to further suppress noise. For example, we show that using the transversal gates of the 5-qubit code allows arbitrary rotations around certain axes to be perfectly corrected. Furthermore, we show that Pauli twirling can increase or decrease the threshold depending upon the code properties. Lastly, we show that even if the physical noise model differs slightly from the hypothesized noise model used to determine an optimized decoder, failure rates can still be reduced by applying our hard decoding algorithm.