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• 1 citation
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

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

Quantum Algorithm Performance Under Noise: A Qiskit Aer Simulation Study and IBM Quantum Hardware Comparative Analysis

Yuvraj Mehta

This study examines how noise affects the reliability of quantum circuits through two complementary approaches: a controlled simulation using Qiskit Aer and an execution study on real IBM Quantum hardware. In simulation, five noise models (bit-flip, phase-flip, depolarizing, readout, and thermal-relaxation) were applied to a parameterized benchmark circuit across varying qubit counts, circuit depths, and noise strengths, producing 6,000 experimental observations. Success probability declined substantially as qubit count and circuit depth increased, with bit-flip, phase-flip, and depolarizing noise degrading performance far more severely (mean success probabilities of 0.597, 0.580, and 0.607) than readout noise (0.917) or thermal-relaxation noise (0.982). The same benchmark circuit was then executed on the ibm_marrakesh processor across 150 hardware runs (150,000 shots). Hardware performance remained consistently high (mean success probability 0.992), declining with qubit count (0.998 at two qubits to 0.986 at six) but showing little sensitivity to circuit depth. These results indicate that controlled noise mechanisms and real hardware degrade circuit performance through different dynamics, with implications for interpreting simulated noise models relative to physical device behavior.

•Oct 4, 2026•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•38 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.
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.
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.
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 study examines how noise affects the reliability of quantum circuits through two complementary approaches: a controlled simulation using Qiskit Aer and an execution study on real IBM Quantum hardware. In simulation, five noise models (bit-flip, phase-flip, depolarizing, readout, and thermal-relaxation) were applied to a parameterized benchmark circuit across varying qubit counts, circuit depths, and noise strengths, producing 6,000 experimental observations. Success probability declined substantially as qubit count and circuit depth increased, with bit-flip, phase-flip, and depolarizing noise degrading performance far more severely (mean success probabilities of 0.597, 0.580, and 0.607) than readout noise (0.917) or thermal-relaxation noise (0.982). The same benchmark circuit was then executed on the ibm_marrakesh processor across 150 hardware runs (150,000 shots). Hardware performance remained consistently high (mean success probability 0.992), declining with qubit count (0.998 at two qubits to 0.986 at six) but showing little sensitivity to circuit depth. These results indicate that controlled noise mechanisms and real hardware degrade circuit performance through different dynamics, with implications for interpreting simulated noise models relative to physical device behavior.
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.