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:1508.03302 · International Journal of Quantum Information

Grover’s search with local and total depolarizing channel errors: Complexity analysis

Ilan Cohn, André L. Fonseca De Oliveira, Efrain Buksman, Jesús García López De Lacalle

Published Mar 1, 2016• 20 citations
arXivHTMLPDF

Abstract

In this paper, the effect of noise on Grover’s algorithm is analyzed, modeled as a total depolarizing channel (TDCh) and a local depolarizing channel (LDCh) in each qubit. The focus was not in error correction (e.g. by the fault-tolerant method), but to provide an insight to the kind of error, or degradation, that needs to be corrected. In the last years, analytical results regarding mainly the TDCh model have been obtained. In this paper, we extend these previous results to the local case, concluding that the degradation of Grover’s algorithm with the latter is worse than the former. It has been shown that for both cases with an N-dependent small enough error-width, smaller than [Formula: see text] for total error and [Formula: see text] for the local case, correction is not needed.

DOI
10.1142/s021974991650009x

Related papers

Order of Grover's search algorithm with both total and local depolarizing channel error

Jesús García López de Lacalle, Ilan Cohn, André Luiz Fonseca de Oliveira +1 more

Noise is an inherent part of quantum computation. Although there exists a fault-tolerant approach to quantum computing, this requires many computational resources. Hence, it is important to analyze how noise affects well-known algorithms. In this paper the effect of noise in Grover?s search algorithm is studied. The noise is modeled as both total depolarizing channel (TDCh), and local depolarizing channel (LDCh) in every qubit. An analysis of the order has been made analytically for the TDCh, and an approximation has been done for the LDCh.

•Jan 1, 2015•0 citations

Enfoque alternativo al análisis de errores de despolarización en el algoritmo de Grover

Jesús García López de Lacalle, André Luiz Fonseca de Oliveira, Ilan Cohn +1 more

En este articulo, se analizo el efecto de introducir ruido al algoritmo de Grover, modelado como ruido total de despolarizacion de canal (TDCh) y como ruido local de despolarizacion de canal (LDCh), utilizando un indice que caracteriza la propagacion de errores en estados cuanticos. Los resultados son comparados con los obtenidos anteriormente por Vrana et. al. [1] y Cohn et. al. [2], concluyendo que la degradacion del algoritmo de Grover con error local (LDCh) es aun peor que con error total (TDCh).

•Sep 1, 2015•0 citations

Effect of isotropic errors on the complexity of Grover's algorithm

Anurag Saha Roy, Jesús Lacalle

Isotropic errors have been shown to be immune to conventional error correction techniques. While general theoretical frameworks have been proposed to model such errors, there have been no studies so far analysing their concrete impact on practical use-cases. Here we explore the effect of isotropic errors on the complexity of Grover's search algorithm through numerical simulations, with an analysis of the impact on the algorithm's performance and success probability. The results provide insights into the robustness of Grover's algorithm against isotropic errors, highlighting potential challenges for implementations on noisy quantum hardware. All results presented here are obtained through numerical simulations using the open-source python library \texttt{isotropic} developed as part of this work. The source code, numerical simulations and documentation for the library are available online at https://www.github.com/lazyoracle/isotropic-error-analysis .

quant-pharXiv:2606.04817•Jun 4, 2026•0 citations

Comparative analysis for Effect of Noise in Grover’s Quantum Search Algorithm

Dushyant Kumar, Balwinder Raj, Gurmohan Singh

Abstract In quantum computing, Grover's technique is extremely vulnerable to several kinds of quantum noise in practice, which can seriously impair its functionality. This study examines how the algorithm's success probabilities is affected by several types of noise, such as rotational error, thermal noise, Two-State Purity (TSP) error, decay and decoherence, and depolarization variables. The findings demonstrate that the algorithm can accomplish flawless amplification of the goal state with negligible mistakes in non-target states when it is executed without noise. The most notable decrease among the noise kinds is caused by decay and decoherence errors and depolarization factors, which lower the likelihood of correctly detecting the target state from 1.0 to roughly 0.885 and 0.968, respectively. Thermal noise, TSP error, and rotational error, on the other hand, have less severe impacts and result in lesser deviations in both target and non-target states. These results demonstrate how crucial quantum error correction and noise reduction techniques are to guaranteeing Grover's algorithm's scalability and dependability in noisy quantum environments. To fully utilize the algorithm's promise in practical applications on both present-day and next quantum technology, these issues must be mitigated.

•Dec 1, 2025•0 citations

Quantum Error Correction Protects Quantum Search Algorithms Against Decoherence

Panagiotis Botsinis, Zunaira Babar, Dimitrios Alanis +4 more

Abstract When quantum computing becomes a wide-spread commercial reality, Quantum Search Algorithms (QSA) and especially Grover’s QSA will inevitably be one of their main applications, constituting their cornerstone. Most of the literature assumes that the quantum circuits are free from decoherence. Practically, decoherence will remain unavoidable as is the Gaussian noise of classic circuits imposed by the Brownian motion of electrons, hence it may have to be mitigated. In this contribution, we investigate the effect of quantum noise on the performance of QSAs, in terms of their success probability as a function of the database size to be searched, when decoherence is modelled by depolarizing channels’ deleterious effects imposed on the quantum gates. Moreover, we employ quantum error correction codes for limiting the effects of quantum noise and for correcting quantum flips. More specifically, we demonstrate that, when we search for a single solution in a database having 4096 entries using Grover’s QSA at an aggressive depolarizing probability of 10−3, the success probability of the search is 0.22 when no quantum coding is used, which is improved to 0.96 when Steane’s quantum error correction code is employed. Finally, apart from Steane’s code, the employment of Quantum Bose-Chaudhuri-Hocquenghem (QBCH) codes is also considered.

Scientific Reports•Dec 7, 2016•31 citations

Grover search under localized dephasing

Daniel Reitzner, Mark S. Hillery

Decoherence in quantum searches, and in the Grover search, in particular, has already been extensively studied, leading very quickly to the loss of the quadratic speedup over the classical case, when searching for some target (marked) element within a set of size $N$. The noise models used were, however, almost always global. In this paper, we study Grover search under the influence of localized partially dephasing noise of rate $p$. We find that, in the case when the size $k$ of the affected subspace is much smaller than $N$ and the target is unaffected by the noise, namely when $kp\ensuremath{\ll}\sqrt{N}$, the quadratic speedup is retained. Once these restrictions are not met, the quadratic speedup is lost. If the target is affected by the noise, the noise rate needs to scale as $1/\sqrt{N}$ to keep the speedup. We also observe an intermediate region, where if $k\ensuremath{\sim}{N}^{\ensuremath{\mu}}$ and the target is unaffected, the speedup seems to obey ${N}^{\ensuremath{\mu}}$, which for $\ensuremath{\mu}>0.5$ is worse than the quantum, but better than the classical case. We also put obtained results for quantum searches into perspective of quantum walks and searches on graphs.

arXiv:1712.06558•Physical Review A•Jan 23, 2019•20 citations
In this paper, the effect of noise on Grover’s algorithm is analyzed, modeled as a total depolarizing channel (TDCh) and a local depolarizing channel (LDCh) in each qubit. The focus was not in error correction (e.g. by the fault-tolerant method), but to provide an insight to the kind of error, or degradation, that needs to be corrected. In the last years, analytical results regarding mainly the TDCh model have been obtained. In this paper, we extend these previous results to the local case, concluding that the degradation of Grover’s algorithm with the latter is worse than the former. It has been shown that for both cases with an N-dependent small enough error-width, smaller than [Formula: see text] for total error and [Formula: see text] for the local case, correction is not needed.
Noise is an inherent part of quantum computation. Although there exists a fault-tolerant approach to quantum computing, this requires many computational resources. Hence, it is important to analyze how noise affects well-known algorithms. In this paper the effect of noise in Grover?s search algorithm is studied. The noise is modeled as both total depolarizing channel (TDCh), and local depolarizing channel (LDCh) in every qubit. An analysis of the order has been made analytically for the TDCh, and an approximation has been done for the LDCh.
En este articulo, se analizo el efecto de introducir ruido al algoritmo de Grover, modelado como ruido total de despolarizacion de canal (TDCh) y como ruido local de despolarizacion de canal (LDCh), utilizando un indice que caracteriza la propagacion de errores en estados cuanticos. Los resultados son comparados con los obtenidos anteriormente por Vrana et. al. [1] y Cohn et. al. [2], concluyendo que la degradacion del algoritmo de Grover con error local (LDCh) es aun peor que con error total (TDCh).
Isotropic errors have been shown to be immune to conventional error correction techniques. While general theoretical frameworks have been proposed to model such errors, there have been no studies so far analysing their concrete impact on practical use-cases. Here we explore the effect of isotropic errors on the complexity of Grover's search algorithm through numerical simulations, with an analysis of the impact on the algorithm's performance and success probability. The results provide insights into the robustness of Grover's algorithm against isotropic errors, highlighting potential challenges for implementations on noisy quantum hardware. All results presented here are obtained through numerical simulations using the open-source python library \texttt{isotropic} developed as part of this work. The source code, numerical simulations and documentation for the library are available online at https://www.github.com/lazyoracle/isotropic-error-analysis .
Abstract In quantum computing, Grover's technique is extremely vulnerable to several kinds of quantum noise in practice, which can seriously impair its functionality. This study examines how the algorithm's success probabilities is affected by several types of noise, such as rotational error, thermal noise, Two-State Purity (TSP) error, decay and decoherence, and depolarization variables. The findings demonstrate that the algorithm can accomplish flawless amplification of the goal state with negligible mistakes in non-target states when it is executed without noise. The most notable decrease among the noise kinds is caused by decay and decoherence errors and depolarization factors, which lower the likelihood of correctly detecting the target state from 1.0 to roughly 0.885 and 0.968, respectively. Thermal noise, TSP error, and rotational error, on the other hand, have less severe impacts and result in lesser deviations in both target and non-target states. These results demonstrate how crucial quantum error correction and noise reduction techniques are to guaranteeing Grover's algorithm's scalability and dependability in noisy quantum environments. To fully utilize the algorithm's promise in practical applications on both present-day and next quantum technology, these issues must be mitigated.
Abstract When quantum computing becomes a wide-spread commercial reality, Quantum Search Algorithms (QSA) and especially Grover’s QSA will inevitably be one of their main applications, constituting their cornerstone. Most of the literature assumes that the quantum circuits are free from decoherence. Practically, decoherence will remain unavoidable as is the Gaussian noise of classic circuits imposed by the Brownian motion of electrons, hence it may have to be mitigated. In this contribution, we investigate the effect of quantum noise on the performance of QSAs, in terms of their success probability as a function of the database size to be searched, when decoherence is modelled by depolarizing channels’ deleterious effects imposed on the quantum gates. Moreover, we employ quantum error correction codes for limiting the effects of quantum noise and for correcting quantum flips. More specifically, we demonstrate that, when we search for a single solution in a database having 4096 entries using Grover’s QSA at an aggressive depolarizing probability of 10−3, the success probability of the search is 0.22 when no quantum coding is used, which is improved to 0.96 when Steane’s quantum error correction code is employed. Finally, apart from Steane’s code, the employment of Quantum Bose-Chaudhuri-Hocquenghem (QBCH) codes is also considered.
Decoherence in quantum searches, and in the Grover search, in particular, has already been extensively studied, leading very quickly to the loss of the quadratic speedup over the classical case, when searching for some target (marked) element within a set of size NNN. The noise models used were, however, almost always global. In this paper, we study Grover search under the influence of localized partially dephasing noise of rate ppp. We find that, in the case when the size kkk of the affected subspace is much smaller than NNN and the target is unaffected by the noise, namely when $kp\ensuremath{\ll}\sqrt{N}$, the quadratic speedup is retained. Once these restrictions are not met, the quadratic speedup is lost. If the target is affected by the noise, the noise rate needs to scale as 1/N1/\sqrt{N}1/N​ to keep the speedup. We also observe an intermediate region, where if $k\ensuremath{\sim}{N}^{\ensuremath{\mu}}$ and the target is unaffected, the speedup seems to obey ${N}^{\ensuremath{\mu}}$, which for $\ensuremath{\mu}>0.5$ is worse than the quantum, but better than the classical case. We also put obtained results for quantum searches into perspective of quantum walks and searches on graphs.