2007/11/09 by Daniel Braun, Bertrand Georgeot
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #quant-ph
paper · pdf · doi:10.1103/physreva.77.022318
published as Phys. Rev. A v. 77, 022318 (2008) · 21 pages, 16 figures
arxiv created 2007/11/09 · openalex publication_date 2008/02/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.