Shor’s algorithm does not factor large integers in the presence of noise  

作　　者：Jin-Yi CAI 

机构地区：[1]College of Letters and Science,University of Wisconsin,Madison WI 53706,USA

出　　处：《Science China(Information Sciences)》2024年第7期301-316,共16页中国科学（信息科学）（英文版）

摘　　要：We consider Shor’s quantum factoring algorithm in the setting of noisy quantum gates.Under a generic model of random noise for(controlled)rotation gates,we prove that the algorithm does not factor integers of the form pq when the noise exceeds a vanishingly small level in terms of n-the number of bits of the integer to be factored,where p and q are from a well-defined set of primes of positive density.We further prove that with probability 1−o(1)over random prime pairs(p,q),Shor’s factoring algorithm does not factor numbers of the form pq,with the same level of random noise present.

关 键 词：random noise Shor’s algorithm rotation gates quantum computing prime factorization 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]