秀尔的算法和诗

作者: 张天蓉

来源: 返朴

发布日期: 2024-06-22 08:33:18

本文介绍了美国数学家彼得·秀尔及其提出的“秀尔量子算法”,该算法解决了大质数的因式分解问题,展示了量子计算在质因数分解问题上实现比经典计算机近乎指数级别的加速,对密码学界和量子计算研究产生了重大影响。同时,文章还提到了秀尔在量子纠错码方面的贡献,以及量子计算与经典计算的结合使用。

尽管费曼等人在1981年MIT会议上揭开了量子计算的序幕,但并未引起很大的反响,直到十几年后,美国数学家秀尔提出“秀尔量子算法”,才让量子计算研究开始步入快车道。彼得·秀尔目前是麻省理工学院(MIT)的应用数学教授,他出生于纽约市,在华盛顿特区和加利福尼亚州长大。秀尔从小表现出极高的数学天赋,就读高中时,他获得美国1977年数学奥林匹克竞赛第三名,同年又赢得国际数学奥林匹克竞赛银牌。

1981年,他在加州理工学院获得数学学士学位,1985年,他在麻省理工学院获得应用数学博士学位。在麻省理工学院获得博士学位后,秀尔在加州大学伯克利分校做了一年的博士后,然后接受了新泽西州贝尔实验室的职位。正是在那里,他开发了Shor算法,解决了大质数的因式分解问题。

费曼1981年在MIT作有关量子计算的主题发言时,秀尔还是加州理工的大四学生。他并不知道费曼演讲的内容,因为他主攻数学。

不过,秀尔也对物理感兴趣,听过费曼的理论物理课。1985年,他又读到大卫·多伊奇关于量子图灵机、量子计算以及量子邱奇-图灵论题的文章。秀尔发现,多伊奇和费曼在考虑量子计算时,都在思考着量子的基础,使他直觉意识到这很重要。之后,秀尔听了查尔斯·本内特在贝尔实验室做的一次量子信息报告,以及1992年优曼许·沃兹内尼到贝尔实验室来做关于量子图灵机报告。

秀尔开始思考是否可以用量子计算机更有效地解决一个实际问题,但没能真正取得进展,直到读到丹·西蒙的文章。

西蒙用了傅里叶变换来找出一个函数的周期。这点启发秀尔开始寻求在量子计算机上解决离散对数问题的方法。离散对数问题是一个有名的难题,如果你解决了它,很容易就找到了因数分解算法,就可以破解一些公钥加密系统,例如RSA。

秀尔算法一出,立刻带来了两个显著效应,一是展示了量子计算可以在质因数分解问题上实现比经典计算机近乎指数级别的加速,二是对密码学界的研究造成了不小的冲击,因为它可以用于破解互联网上广泛使用的RSA协议,给信息安全提出了新的挑战。

然而,因为量子比特的特殊性,无法直接观测,因而缺乏有效的纠错手段。两个主要的量子力学原理,海森堡不确定性原理和量子不可克隆定理,被视为纠错的最大阻碍。

面对以上挑战,秀尔再次挺身而出,构造了第一个量子纠错码方案,他把3位重复码嵌入另一个码。也就是说,将一个逻辑量子位,用9个物理量子位进行编码。秀尔的方案可以防止并纠正任何3个物理量子位上发生的任意量子错误。在这些发展之后,人们开始寻找其它的量子纠错码。

秀尔也提出了办法来克服量子态退相干不可测量的问题,以及量子比特不可克隆的困难,基本思想就是利用量子纠缠这个量子世界的独特现象。秀尔让编码一个逻辑量子比特的9个物理量子比特互相纠缠在一起。在这两个量子计算的重大突破之后,人们终于相信实际构建一台量子计算机是有巨大应用潜力和原理上可行的了,实验物理学家和工程师们正式登上历史舞台,并取得了丰硕的成果。

UUID: f529b9f4-c6d0-424d-899a-d7a97d5435d9

原始文件名: /home/andie/dev/tudou/annot/AI语料库-20240917-V2/AI语料库/返朴公众号-pdf2txt/2024/返朴_2024-06-22「转」_秀尔的算法和诗.txt

是否为广告: 否

处理费用: 0.0075 元