量子計算的演算法：離散對數與因數分解
量子電腦能飛快地分解巨大的數——並攻破守護網際網路的加密。
1994 年，一位數學家證明：一台還沒有人造出來的機器，原則上能破解守護著網際網路祕密的那些密碼。
核心想法
幾乎一切在線的安全通信——你的銀行、你的訊息、你的密碼——都押在一個簡單的賭注上：哪怕最快的電腦，要找出「相乘才得到某個巨大的數」的那兩個質數，也得花上比宇宙年齡還久的時間。彼得·肖爾卻表明：一台量子電腦——一種遵循量子物理規則、根本不同的機器——能很快贏下這個賭注。它能飛快地分解那些龐大的數——從而打開建立其上的密碼。
他的竅門，是把因數分解變成一個關於「節奏」的問題。你不去正面搜尋因數，而是去看藏在數裡的一種重複圖樣，找出它多久重複一次。量子電腦能讓許多可能性像層疊的波那樣相互干涉，於是一下子就「感覺」到這種重複。
它是如何誕生的
整個 1980 年代，少數物理學家——理查德·費曼也在其中——揣摩著：一台用量子零件造出來的電腦，能否做到普通機器做不到的事。這想法引人入勝，卻找不到一個非它不可的用途。直到 1994 年，在 AT&T 的貝爾實驗室，彼得·肖爾找到了一個。他在丹尼爾·西蒙關於「求隱藏週期」的巧妙結果之上，證明了量子機器能分解數、能攻破最廣為使用的密碼。
他那年十一月所作的報告，讓整個領域為之一震。一夜之間，量子計算不再是一樁奇思，而成了國家安全的大事；資金與人才紛紛湧入，而那場「真把這種機器造出來——並防住它」的漫長競賽，就此開始。
它為何重要
RSA 及其同族，守護著地球上幾乎每一條安全連接（RSA 就在本館中）。肖爾的結果是一個證明——而非一種預感：一台足夠大的量子電腦將攻破它們。正是這一個事實，掀起了全球對「後量子」密碼的搜尋——那是連量子電腦也攻不破的密碼；2024 年，首批這樣的標準正式發布，全世界的系統如今正在升級——而那台構成威脅的機器，還未誕生。
一個可以想像的畫面
想像一座上了鎖的鐘樓，它的門只有在你確知「兩記特定鐘聲之間隔著多少秒」時才會打開。一個拿著碼表的人，得聽上長得離譜的時間，才能確定那節奏。而一台量子電腦，就好比能同時聽見每一種可能的節奏一齊響起，再瞬間挑出那真正存在的一種。一旦它知道了節拍，門——以及門後的祕密——便自行打開。
它的位置
這是本館中那門密碼學的「暗面孿生」。迪菲與赫爾曼（1976），以及隨後的 RSA（1978），把公鑰密碼建立在被認為難得沒指望的問題之上；肖爾卻表明，那些問題只是對「我們當時擁有的機器」才難。他的工作，與圖靈「電腦究竟能做什麼」之問比肩而立，並指向一個未來：從金錢到比特幣（也在本館中）——一切的安全，或許都得重新築造。
A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation time by at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on a classical computer and which have been used as the basis of several proposed cryptosystems.