量子噪声对Shor算法的影响  

Effects of quantum noise on Shor’s algorithm

作　　者：黄天龙 吴永政 倪明[1] 汪士 叶永金 Huang Tian-Long;Wu Yong-Zheng;Ni Ming;Wang Shi;Ye Yong-Jin(The 32nd Research Institute of China Electronics Technology Group Corporation,Shanghai 201808,China)

机构地区：[1]中国电子科技集团公司第三十二研究所,上海201808

出　　处：《物理学报》2024年第5期43-58,共16页Acta Physica Sinica

摘　　要：Shor算法能够借助量子计算机以多项式级别复杂度解决大整数因式分解问题,从而破解一系列安全性基于大整数因式分解的加密算法,例如Rivest-Shamir-Adleman加密算法、Diffie-Hellman密钥交换协议等.由于量子测量结果是概率性的,在运行量子线路时很容易受到噪声的干扰,这将导致无法测量得到预期结果.本文分别研究了不同通道的噪声对Shor算法的影响,分别是去极化通道、状态制备与测量通道以及热退相干通道.本文模拟在噪声环境中运行Shor算法并且给出了数值结果.数值结果表明Shor算法成功分解整数的概率易受到噪声影响,其中去极化通道中的噪声能够以指数形式影响Shor算法成功分解整数的概率,其次是热退相干通道噪声,最后是状态制备与测量通道噪声,能够线性影响到Shor算法成功分解的概率.本文能够为后续纠错、改进Shor算法以及确定工程实现Shor算法所需要的保真度等提供建设性意见.Shor’s quantum factoring algorithm(Shor’s algorithm)can solve factorization problem of large integers by using a fully-operational quantum computer with the complexity of polynomial-time level,thereby cracking a series of encryption algorithms(such as Rivest-Shamir-Adleman encryption algorithm,and Diffie-Hellman key exchange protocol)whose security is guaranteed by factorizing large integers,which is a difficult problem.We are currently in a noisy intermediate-scale quantum era,which means that we can only operate on quantum computers with a limited number of qubits and we have to take care of the effects of quantum noise.Quantum states on a quantum computer are prone to quantum noise caused by low-fidelity gates or interactions between qubits and the environment,which results in inaccurate measurements.We study the influence of quantum noise on Shor’s algorithm through 3 typical quantum noise channels:the depolarizing channel,the state preparation and measurement channel,and the thermal relaxation channel.We successfully simulate the factorization of the numbers 15,21,and 35 into their corresponding prime factors by using the quantum circuit we have constructed on a classical computer.Then we simulate a running quantum circuit of Shor’s algorithm in a noisy environment with different level of noise for a certain type of noise channel and present numerical results.We can obtain precise measurements by calculating the state vector prior to measurement,instead of simulating and measuring expending much time,which contributes to higher efficiency.Each experiment is repeated 1000 times to reduce discrepancy.Our research indicates that Shor’s algorithm is easily affected by quantum noise.Successful rate of Shor’s algorithm decreases exponentially with the increase of noise level in the depolarizing channel,where the successful rate is an indicator we propose in this research to quantify the influence of noise on Shor’s algorithm,meanwhile the noise in the state preparation and measurement channel and the

关 键 词：量子计算 量子算法 量子噪声 Shor算法 

分 类 号：O413[理学—理论物理]