Effects of imperfections for Shor’s factorization algorithm

2007/01/31 by Ignacio García-Mata, Ignacio Garcia-Mata, Klaus M. Frahm +1
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum and electron transport phenomena #quant-ph

paper · pdf · doi:10.1103/physreva.75.052311

published as Phys. Rev. A 75, 052311 (2007) · 10 pages, 10 figures, 1 table. Added references and new data. Erratum added as appendix. 1 Figure and 1 Table added. Research is available at http://www.quantware.ups-tlse.fr/

openalex publication_date 2007/05/09 · arxiv created 2007/09/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study effects of imperfections induced by residual couplings between qubits on the accuracy of Shor's algorithm using numerical simulations of realistic quantum computations with up to 30 qubits. The factoring of numbers up to N=943 show that the width of peaks, which frequencies allow to determine the factors, grow exponentially with the number of qubits. However, the algorithm remains operational up to a critical coupling strength ϵ_c which drops only polynomially with log₂\phantom\rule0.2em0exN. The numerical dependence of ϵ_c on log₂\phantom\rule0.2em0exN is explained by analytical estimates that allows one to obtain the scaling for functionality of Shor's algorithm on realistic quantum computers with a large number of qubits.

Citations

• Scalability of Shor’s algorithm with a limited set of rotation gates
• Phase diagram for the Grover algorithm with static imperfections
• Eigenstates of an operating quantum computer: hypersensitivity to static imperfections
• Fast quantum modular exponentiation
• Quantum networks for elementary arithmetic operations
• Quantum computation of the Anderson transition in the presence of imperfections
• Quantum computing of quantum chaos in the kicked rotator model