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

Physical Review A

Dominant gate imperfection in Grover’s quantum search algorithm

Gui Lu Long, Yan Li, Wei Lin Zhang, Chang Cun Tu

Published Mar 10, 2000• 81 citations
Publisher

Abstract

It is found that systematic errors in phase inversions and random errors in Hadmard-Walsh transformations are the dominant gate imperfection in Grover's quantum search algorithm. They lead to reductions in the maximum probability of the marked state and affect the efficiency of the algorithm. Given the degree of inaccuracy, we find that to guarantee a half-rate of success, the size of the database should be on the order of $O(1/{\ensuremath{\delta}}^{2}),$ where $\ensuremath{\delta}$ is the uncertainty.

DOI
10.1103/physreva.61.042305

Related papers

An intrinsic limitation on the size of quantum database

Long, Gui Lu, Yan Li, Wei Lin Zhang +1 more

It is found that Grover's quantum search algorithm is not robust against phase inversion and Hadmard transformation inaccuracies. Imperfect phase inversions and Hadmard-Walsh transformations in Grover's quantum search algorithm lead to reductions in the maximum probability of the marked state and affect the efficiency of the algorithm. even in the absence of decoherence. Given the degrees of inaccuracies, we find that to guarantee half rate of success, the size of the database should be in the order of $O({1 \over δ^2})$, where $δ$ is the uncertainty.

arXiv:quant-ph/9910076•Oct 16, 1999•1 citation

Gate imperfection in the quantum random-walk search algorithm

Yun Li, Lei Ma, Jie Zhou

We study how imperfect quantum gates affect the quantum random-walk search algorithm. We find that systematic errors in phase inversions result in the reduction of the maximum probability of the marked state and lower the algorithm efficiency with an increasing degree of inaccuracy. The size of the database should be limited due to the inevitable errors. Finally, we compare the phase noise caused by such errors in the random-walk search algorithm with that in the Grover search algorithm.

Journal of Physics A Mathematical and General•Jul 5, 2006•7 citations

An improved phase error tolerance in Quantum search algorithm

Jin-Yuan Hsieh, Che‐Ming Li, Der-San Chuu

As the matching condition in Grover search algorithm is transgressed due to inevitable errors in phase inversions, it gives a reduction in maximum probability of success. With a given degree of maximum success, we have derive the generalized and imroved criterion for tolerated error and corresponding size of quantum database under the inevitable gate imperfections. The vanished inaccurancy to this condition has also been shown. Besides, a concise formula for evaluating minimum number of iterations is also presented in this work.

arXiv:quant-ph/0209073•Sep 11, 2002•4 citations

Phase Matching in Quantum Searching and the Improved Grover Algorithm

Yang Sun

We briefly introduced some of our recent work related to the phase matching condition in quantum searching algorithms and the improved Grover algorithm. When one replaces the two phase inversions in the Grover algorithm with arbitrary phase rotations, the modified algorithm usually fails in searching the marked state unless a phase matching condition is satisfied between the two phases. The Grover algorithm is not 100% in success rate, an improved Grover algorithm with zero-failure rate is given by replacing the phase inversions with angles that depends on the size of the database. Other aspects of the Grover algorithm such as the SO(3) picture of quantum searching, the dominant gate imperfections in the Grover algorithm are also mentioned.

Yuanzihe wuli pinglun•Jan 1, 2004•7 citations

Effects of systematic phase errors on optimized quantum random-walk search algorithm

Yuchao Zhang, Wan‐Su Bao, Xiang Wang +1 more

This study investigates the effects of systematic errors in phase inversions on the success rate and number of iterations in the optimized quantum random-walk search algorithm. Using the geometric description of this algorithm, a model of the algorithm with phase errors is established, and the relationship between the success rate of the algorithm, the database size, the number of iterations, and the phase error is determined. For a given database size, we obtain both the maximum success rate of the algorithm and the required number of iterations when phase errors are present in the algorithm. Analyses and numerical simulations show that the optimized quantum random-walk search algorithm is more robust against phase errors than Grover’s algorithm.

arXiv:1501.02098•Chinese Physics B•Jun 1, 2015•6 citations

Interference versus success probability in quantum algorithms with imperfections

Daniel Braun, Bertrand Georgeot

We study the importance of interference for the performance of Shor's factoring algorithm and Grover's search algorithm using a recently proposed interference measure. To this aim we introduce systematic unitary errors, random unitary errors, and decoherence processes in these algorithms. We show that unitary errors which destroy the interference destroy the efficiency of the algorithm, too. However, unitary errors may also create useless additional interference. In such a case the total amount of interference can increase, while the efficiency of the quantum computation decreases. For decoherence due to phase flip errors, interference is destroyed for small error probabilities, and converted into destructive interference for error probabilities approaching 1, leading to success probabilities which can even drop below the classical value. Our results show that in general, interference is necessary in order for a quantum algorithm to outperform classical computation, but large amounts of interference are not sufficient and can even lead to destructive interference with worse than classical success rates.

arXiv:0711.1513•Physical Review A•Feb 14, 2008•7 citations
It is found that systematic errors in phase inversions and random errors in Hadmard-Walsh transformations are the dominant gate imperfection in Grover's quantum search algorithm. They lead to reductions in the maximum probability of the marked state and affect the efficiency of the algorithm. Given the degree of inaccuracy, we find that to guarantee a half-rate of success, the size of the database should be on the order of O(1/\ensuremathδ2),O(1/{\ensuremath{\delta}}^{2}),O(1/\ensuremathδ2), where \ensuremathδ\ensuremath{\delta}\ensuremathδ is the uncertainty.
It is found that Grover's quantum search algorithm is not robust against phase inversion and Hadmard transformation inaccuracies. Imperfect phase inversions and Hadmard-Walsh transformations in Grover's quantum search algorithm lead to reductions in the maximum probability of the marked state and affect the efficiency of the algorithm. even in the absence of decoherence. Given the degrees of inaccuracies, we find that to guarantee half rate of success, the size of the database should be in the order of O(1δ2)O({1 \over δ^2})O(δ21​), where δδδ is the uncertainty.
As the matching condition in Grover search algorithm is transgressed due to inevitable errors in phase inversions, it gives a reduction in maximum probability of success. With a given degree of maximum success, we have derive the generalized and imroved criterion for tolerated error and corresponding size of quantum database under the inevitable gate imperfections. The vanished inaccurancy to this condition has also been shown. Besides, a concise formula for evaluating minimum number of iterations is also presented in this work.
We briefly introduced some of our recent work related to the phase matching condition in quantum searching algorithms and the improved Grover algorithm. When one replaces the two phase inversions in the Grover algorithm with arbitrary phase rotations, the modified algorithm usually fails in searching the marked state unless a phase matching condition is satisfied between the two phases. The Grover algorithm is not 100% in success rate, an improved Grover algorithm with zero-failure rate is given by replacing the phase inversions with angles that depends on the size of the database. Other aspects of the Grover algorithm such as the SO(3) picture of quantum searching, the dominant gate imperfections in the Grover algorithm are also mentioned.
This study investigates the effects of systematic errors in phase inversions on the success rate and number of iterations in the optimized quantum random-walk search algorithm. Using the geometric description of this algorithm, a model of the algorithm with phase errors is established, and the relationship between the success rate of the algorithm, the database size, the number of iterations, and the phase error is determined. For a given database size, we obtain both the maximum success rate of the algorithm and the required number of iterations when phase errors are present in the algorithm. Analyses and numerical simulations show that the optimized quantum random-walk search algorithm is more robust against phase errors than Grover’s algorithm.
We study the importance of interference for the performance of Shor's factoring algorithm and Grover's search algorithm using a recently proposed interference measure. To this aim we introduce systematic unitary errors, random unitary errors, and decoherence processes in these algorithms. We show that unitary errors which destroy the interference destroy the efficiency of the algorithm, too. However, unitary errors may also create useless additional interference. In such a case the total amount of interference can increase, while the efficiency of the quantum computation decreases. For decoherence due to phase flip errors, interference is destroyed for small error probabilities, and converted into destructive interference for error probabilities approaching 1, leading to success probabilities which can even drop below the classical value. Our results show that in general, interference is necessary in order for a quantum algorithm to outperform classical computation, but large amounts of interference are not sufficient and can even lead to destructive interference with worse than classical success rates.