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:quant-ph/9903070 · Physical Review A

Noise in Grover’s quantum search algorithm

B. Pablo-Norman, M. Ruiz-Altaba

Published Dec 8, 1999• 34 citations
arXivHTMLPDF

Abstract

Grover's quantum algorithm improves any classical search algorithm. We show how random Gaussian noise at each step of the algorithm can be modeled easily because of the exact recursion formulas available for computing the quantum amplitude in Grover's algorithm. We study the algorithm's intrinsic robustess when no quantum correction codes are used, and evaluate how much noise the algorithm can bear with, in terms of the size of the phone book and a desired probability of finding the correct result. The algorithm loses efficiency when noise is added, but does not slow down. We also study the maximal noise under which the iterated quantum algorithm is just as slow as the classical algorithm. In all cases, the width of the allowed noise scales with the size of the phone book as ${N}^{\ensuremath{-}2/3}.$

DOI
10.1103/physreva.61.012301

Related papers

Robustness of the quantum search algorithm

B. Pablo-Norman, M. Ruiz-Altaba

We find exact results for Grover's quantum search algorithm and analyze its behavior under noisy situations when no quantum correction codes are available.We compute how the algorithm slows down: it is still better than a classical one, provided the noise is smaller than some bound, which we also compute.

AIP conference proceedings•Jan 1, 1999•0 citations

Effect of unitary noise on Grover’s quantum search algorithm

Daniel Shapira, Shay Mozes, Ofer Biham

The effect of unitary noise on the performance of Grover's quantum search algorithm is studied. This type of noise may result from tiny fluctuations and drift in the parameters of the (quantum) components performing the computation. The resulting operations are still unitary, but not precisely those assumed in the design of the algorithm. Here we focus on the effect of such noise in the Hadamard gate W, which is an essential component in each iteration of the quantum search process. To this end W is replaced by a noisy Hadamard gate U. The parameters of U at each iteration are taken from an arbitrary probability distribution (e.g., a Gaussian distribution) and are characterized by their statistical moments around the parameters of W. For simplicity, we assume that the noise is unbiased and isotropic, namely, all noise variables in the parametrization we use have zero average and the same standard deviation $\ensuremath{\epsilon}.$ The noise terms at different calls to U are assumed to be uncorrelated. For a search space of size ${N=2}^{n}$ (where n is the number of qubits used to span this space) it is found that as long as $\ensuremath{\epsilon}<{O(n}^{\ensuremath{-}1/2}{N}^{\ensuremath{-}1/4})$ the algorithm maintains significant efficiency, while above this noise level its operation is hampered completely. It is also found that below this noise threshold, when the search fails, it is likely to provide a state that differs from the marked state by only a few bits. This feature can be used to search for the marked state by a classical postprocessing, even if the quantum search has failed, thus improving the success rate of the search process.

arXiv:quant-ph/0307142•Physical Review A•Apr 1, 2003•49 citations

Quantum Search using Grover’s Algorithm: Principles, Performance, and Applications

Anggit Gusti Nugraheni, Heri Mahyuzar, Sri Hastuti

Quantum search is one of the most important algorithmic developments in quantum computing because it demonstrates how quantum principles can improve the efficiency of solving unstructured search problems. Grover’s algorithm provides a quadratic speed-up over classical linear search by reducing query complexity from O(N) to O(√N), where N represents the size of the search space. This review examines the principles, performance, and applications of Grover’s algorithm, with emphasis on its theoretical foundation and practical relevance. The discussion covers the roles of superposition, quantum interference, oracle operations, diffusion operators, and amplitude amplification in increasing the probability of measuring a desired solution. The manuscript also reviews the computational performance of quantum search in comparison with classical search methods and considers its relevance to database searching, combinatorial optimisation, cryptography, machine learning, bioinformatics, quantum chemistry, and materials science. The review highlights that Grover’s algorithm is not limited to database retrieval, as many computationally intensive problems can be reformulated as search or optimisation tasks. However, practical implementation remains constrained by current quantum hardware limitations, including decoherence, quantum noise, limited qubit availability, circuit depth, and the difficulty of designing efficient oracles. Despite these challenges, continuing progress in quantum hardware, error correction, cloud-based quantum platforms, and hybrid quantum-classical architectures suggests that quantum search will remain an important area of research. Overall, Grover’s algorithm represents a foundational quantum algorithm with significant theoretical value and potential long-term application in computational domains involving large and unstructured search spaces.

Asian journal of mathematics and computer research•Jun 23, 2026•0 citations

White Noise in Quantum Random Walk Search Algorithm

Лей Ма, Du Jiang-Feng, Yun Li +3 more

The quantum random walk is a possible approach to construct new quantum search algorithms. It has been shown by Shenvi et al. [Phys. Rev. A 67 (2003) 52307 that a kind of algorithm can perform an oracle search on a database of N items with O ( N 1/2 ) calling to the oracle, yielding a speedup similar to other quantum search algorithms. We study the effect of white or Gaussian noise on this algorithm. The algorithm loses efficiency when noise is added. We also show that noise on the target state plays a more important role than that on other states. Finally we compare the effects of similar types of noise in the quantum random walk search algorithm and Grover's search algorithm.

Chinese Physics Letters•Mar 30, 2006•4 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

Optimization of Grover's Search Algorithm

Varun Garg, Anupama Pande

Abstract—Quantum mechanical computers unlike classical computers can be in a superposition of states and carry out multiple operations at the same time. Grover has shown that a quantum computer can do a random database search in O ( √ N) steps. He has further proved that using the superposition of the states in quantum computing, a quantum computer should be able to do a search in a single step. He has stated that the query generated to do this search will require Ω(NlogN) steps. In this paper we aim at optimizing the Grover’s search algorithm. In our algorithm, we have repeated the inversion step a number of times instead of stopping after a single step. Measurement after a single step required a larger number of subsystems which impaired the effectiveness of the algorithm leading to Ω(NlogN) steps in the preparation and processing of the query. Repetition of the inversion step brought the the number of subsystems down drastically by increasing the amplitude of the desired state.We have proved that by doing so the overall effectiveness of Grover’s algorithm can be brought down to Ω ( 3 √ N). Keywords: Quantum mechanical computers, Grover’s search algorithm, inversion step, probability and amplitude.

•Jan 1, 2008•0 citations
Grover's quantum algorithm improves any classical search algorithm. We show how random Gaussian noise at each step of the algorithm can be modeled easily because of the exact recursion formulas available for computing the quantum amplitude in Grover's algorithm. We study the algorithm's intrinsic robustess when no quantum correction codes are used, and evaluate how much noise the algorithm can bear with, in terms of the size of the phone book and a desired probability of finding the correct result. The algorithm loses efficiency when noise is added, but does not slow down. We also study the maximal noise under which the iterated quantum algorithm is just as slow as the classical algorithm. In all cases, the width of the allowed noise scales with the size of the phone book as N\ensuremath−2/3.{N}^{\ensuremath{-}2/3}.N\ensuremath−2/3.
The effect of unitary noise on the performance of Grover's quantum search algorithm is studied. This type of noise may result from tiny fluctuations and drift in the parameters of the (quantum) components performing the computation. The resulting operations are still unitary, but not precisely those assumed in the design of the algorithm. Here we focus on the effect of such noise in the Hadamard gate W, which is an essential component in each iteration of the quantum search process. To this end W is replaced by a noisy Hadamard gate U. The parameters of U at each iteration are taken from an arbitrary probability distribution (e.g., a Gaussian distribution) and are characterized by their statistical moments around the parameters of W. For simplicity, we assume that the noise is unbiased and isotropic, namely, all noise variables in the parametrization we use have zero average and the same standard deviation $\ensuremath{\epsilon}.$ The noise terms at different calls to U are assumed to be uncorrelated. For a search space of size N=2n{N=2}^{n}N=2n (where n is the number of qubits used to span this space) it is found that as long as $\ensuremath{\epsilon}<{O(n}^{\ensuremath{-}1/2}{N}^{\ensuremath{-}1/4})$ the algorithm maintains significant efficiency, while above this noise level its operation is hampered completely. It is also found that below this noise threshold, when the search fails, it is likely to provide a state that differs from the marked state by only a few bits. This feature can be used to search for the marked state by a classical postprocessing, even if the quantum search has failed, thus improving the success rate of the search process.
Quantum search is one of the most important algorithmic developments in quantum computing because it demonstrates how quantum principles can improve the efficiency of solving unstructured search problems. Grover’s algorithm provides a quadratic speed-up over classical linear search by reducing query complexity from O(N) to O(√N), where N represents the size of the search space. This review examines the principles, performance, and applications of Grover’s algorithm, with emphasis on its theoretical foundation and practical relevance. The discussion covers the roles of superposition, quantum interference, oracle operations, diffusion operators, and amplitude amplification in increasing the probability of measuring a desired solution. The manuscript also reviews the computational performance of quantum search in comparison with classical search methods and considers its relevance to database searching, combinatorial optimisation, cryptography, machine learning, bioinformatics, quantum chemistry, and materials science. The review highlights that Grover’s algorithm is not limited to database retrieval, as many computationally intensive problems can be reformulated as search or optimisation tasks. However, practical implementation remains constrained by current quantum hardware limitations, including decoherence, quantum noise, limited qubit availability, circuit depth, and the difficulty of designing efficient oracles. Despite these challenges, continuing progress in quantum hardware, error correction, cloud-based quantum platforms, and hybrid quantum-classical architectures suggests that quantum search will remain an important area of research. Overall, Grover’s algorithm represents a foundational quantum algorithm with significant theoretical value and potential long-term application in computational domains involving large and unstructured search spaces.
The quantum random walk is a possible approach to construct new quantum search algorithms. It has been shown by Shenvi et al. [Phys. Rev. A 67 (2003) 52307 that a kind of algorithm can perform an oracle search on a database of N items with O ( N 1/2 ) calling to the oracle, yielding a speedup similar to other quantum search algorithms. We study the effect of white or Gaussian noise on this algorithm. The algorithm loses efficiency when noise is added. We also show that noise on the target state plays a more important role than that on other states. Finally we compare the effects of similar types of noise in the quantum random walk search algorithm and Grover's search algorithm.
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.
Abstract—Quantum mechanical computers unlike classical computers can be in a superposition of states and carry out multiple operations at the same time. Grover has shown that a quantum computer can do a random database search in O ( √ N) steps. He has further proved that using the superposition of the states in quantum computing, a quantum computer should be able to do a search in a single step. He has stated that the query generated to do this search will require Ω(NlogN) steps. In this paper we aim at optimizing the Grover’s search algorithm. In our algorithm, we have repeated the inversion step a number of times instead of stopping after a single step. Measurement after a single step required a larger number of subsystems which impaired the effectiveness of the algorithm leading to Ω(NlogN) steps in the preparation and processing of the query. Repetition of the inversion step brought the the number of subsystems down drastically by increasing the amplitude of the desired state.We have proved that by doing so the overall effectiveness of Grover’s algorithm can be brought down to Ω ( 3 √ N). Keywords: Quantum mechanical computers, Grover’s search algorithm, inversion step, probability and amplitude.