想象一下，你和一些朋友一起參觀一個迷宮。你進入後不久就從出口出來了，然後等待了幾個小時你的朋友才出來。很自然地，他們會問你走的路——你肯定可以原路返回並向他們展示路線，對吧？
但在一個由量子物理學奇怪定律支配的世界裡，情況並非如此。二十年前，量子計算研究人員開發了一種演算法，利用這些定律以比在普通經典計算機上執行的任何演算法快得多的速度遍歷一種特定的數學迷宮。但這種加速是有代價的：快速量子演算法找到了出口，但不知道它是如何到達那裡的。
研究人員長期以來一直想知道這種權衡是否不可避免。真的不可能在不忘記路徑的情況下快速找到出口嗎？
關於支援科學新聞
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您正在幫助確保有關塑造我們今天世界的發現和想法的具有影響力的故事的未來。
“你甚至需要問這個問題，這真是令人難以置信，” 馬里蘭州蓋瑟斯堡國家標準與技術研究所的計算機科學家 Matthew Coudron 說。
去年 11 月，Coudron 和兩位同事朝著解決這個長期存在的問題邁出了一大步：他們 證明，在廣泛而自然的快速量子演算法類別中，沒有任何演算法可以找到透過特殊迷宮（稱為焊接樹圖）的路徑。結果表明，任何假設的非盲目猜測的尋路演算法都必須暫時失去對入口的跟蹤，才有成功的機會。看來遺忘是不可避免的。
“我絕對想不到他們竟然能證明這一點，”巴黎國家科學研究中心計算機科學基礎研究所的量子計算研究員 Simon Apers 說，並補充說，這一結果“對於說明量子演算法能做什麼和不能做什麼非常有用”。
量子提升
量子計算機的能力部分歸功於一種稱為疊加的現象，這種現象實際上使它們能夠同時探索經典計算機需要單獨考慮的許多選項。但這 並沒有那麼簡單，就像同時執行多個計算以節省時間一樣。檢查選擇疊加的結果永遠不會揭示結果的疊加——相反，你只會獲得一個可能的結果，每個結果都有不同的機率。量子演算法依賴於這樣一個事實，即對這些機率的貢獻可以像池塘表面的波浪一樣相互干擾，從而提高獲得正確答案的機率，同時降低獲得其他每個結果的機率。
由於干涉必須恰到好處地發揮作用，因此並非每個計算任務都適合量子加速，事實上，在量子計算首次被提出幾十年後，研究人員仍在研究量子演算法可以在哪裡提供幫助。但他們取得了一些顯著的成功。1994 年，Peter Shor 開發了一種量子演算法，用於分解大數——這項任務對於經典計算機來說顯然很困難，是現代密碼學的基礎。Shor 的演算法可以快速分解非常大的數字，以至於所有已知的經典演算法實際上都將變得毫無用處。
1996 年，計算機科學家 Lov Grover 找到了第二個潛在的實際例子：一種量子演算法，用於解決非常通用的搜尋問題，類似於在許多相同的盒子中找到隱藏的單個物品。
“在經典方法中，你可以做的就是隨機嘗試一個，看看它是否好，然後再試一次，看看它是否好，然後你一直嘗試，直到找到一個好的元素，”Apers 說。這種方法花費的時間與盒子的數量成正比。將該數字乘以 100，搜尋速度將慢 100 倍。
使用量子演算法，你可以做得更好。Grover 證明，如果你設定所有盒子的疊加，你可以利用干涉實際上保證演算法最終會選擇正確的盒子。整個過程花費的時間與盒子數量的平方根成正比：將該數字增加 100 倍只會將執行時間增加 10 倍。
Grover 的演算法非常簡單地說明了量子疊加的價值，但它實現的加速相對適中——遠遠超出最佳經典演算法範圍的任務也會難倒 Grover 的演算法。Shor 的分解演算法讓人們看到了量子計算機和經典計算機能力之間巨大的鴻溝。是否存在 Grover 搜尋問題的變體，它像分解一樣——對於經典計算機來說實際上是棘手的，但對於量子計算機來說卻很容易？
在 20 世紀 90 年代後期，研究人員開始探索這個問題，將其重新表述為關於圖的問題——由點或節點組成的網路，由稱為邊的線連線。任何搜尋問題都可以用圖論的語言來表達，其中一個節點代表起點，另一個節點代表目的地，邊代表沿途每一步的可能選擇
例如，Grover 的問題對應於搜尋一個圖中每個節點都連線到每個其他節點的圖（因為你可以按任何順序開啟盒子）。給定搜尋問題的不同經典演算法相當於一次探索相應圖的一個節點的不同策略，而量子演算法可以沿多個邊以疊加方式移動。
分支擴充套件
2002 年，一個計算機科學家團隊最終確定了一個經典棘手的搜尋問題，量子演算法可以輕鬆解決。他們從一個簡單的圖開始，稱為樹，其中每個節點發芽兩條邊，通向另外兩個節點，每個節點又分裂成另外兩個分支，依此類推。從單個“根”節點開始，樹圖分支多次，然後在稱為“葉子”的最後一層節點中結束。該團隊想象取兩棵相同的樹，並透過將它們定位為葉子彼此面對，然後使用隨機過程將一棵樹上的每個葉子連線到另一棵樹上的兩個葉子，從而將它們“焊接”在一起。然後他們提出了以下問題：從焊接樹圖的一個根開始，你能找到通往另一個根的路嗎？
如果沒有對圖的鳥瞰圖，任何嘗試解決此搜尋問題的經典演算法在到達圖的中間層後都會徹底迷失——所有邊看起來都相同，並且無法區分指向前方的邊和指向後方的邊。演算法可能會意外地偶然發現出口節點，但它花費在徘徊上的平均時間會隨著樹中層數的增加呈指數增長。
2002 年論文的作者證明，一種簡單的量子演算法——一種透過疊加許多路徑在圖中均勻傳播的“量子游走”——可以更快地找到通往出口的路。這是因為焊接樹圖的對稱佈局導致路徑之間發生干涉，從而將流量集中在向前方向。拉脫維亞大學的計算機科學家 Alexander Belov 說，出口節點“就像演算法的焦點”。
這種量子游走演算法很有可能在與層數成正比的時間內收斂到出口。這使其比任何經典演算法都快得多——加速效果與 Shor 的分解演算法相當。但是，導致量子加速的干涉也消除了演算法在其通往出口的路徑上遍歷的所有記錄。
研究人員想知道是否有可能兼得魚和熊掌——一種快速演算法，可以識別從入口到出口的路徑。
“如果僅僅是基本的量子游走以某種方式找到出口，那就行不通，”馬里蘭大學帕克分校的計算機科學家 Andrew Childs 說，他作為研究生與人合著了 2002 年的論文，並與 Coudron 合作研究了新成果。“但也許你可以以某種方式改進它。”
改進它
最早著手解決這個問題的人之一是 Ansis Rosmanis，他現在是名古屋大學數學研究生院的計算機科學家。在 2010 年的一篇論文中，Rosmanis 開發了一類他稱為“量子蛇形遊走”的演算法，這些演算法使用關於它們去過哪裡的記憶來補充標準的量子游走演算法。
當標準量子游走演算法在圖中流動時，它的下一步完全取決於它當前所處的位置——它是如何到達那裡的並不重要。相比之下，在 Rosmanis 的蛇形遊走中，你需要知道過去才能預測未來。具體而言，蛇形遊走的演變由“蛇”決定，蛇是遊走先前經過的相鄰節點串。蛇形遊走有很多種，其中在這些蛇的長度在遊走過程中如何變化等方面存在差異。
Rosmanis 表明，儘管量子蛇形遊走記住了它們的軌跡，但使用多條蛇的疊加的量子蛇形遊走仍然可以表現出有益的干涉，並且某些蛇形遊走原則上可以找到通往出口的路徑。但他找不到一種特定的蛇形遊走演算法可以快速做到這一點，他也無法證明這種演算法不存在。蛇形遊走似乎很有希望，但太滑溜了，難以確定。Rosmanis 的工作是近十年來關於尋路問題的最後結論。
然後在 2019 年，Coudron 在不同的背景下遇到了焊接樹圖：他和一位同事證明，所有找到出口的量子游走演算法都缺乏一種在已知可為其他問題產生指數級量子加速的演算法中普遍存在的屬性。該結果與尋路沒有直接關係，但 Coudron 開始懷疑，使他能夠證明關於所有焊接樹圖演算法屬性的這一概括性陳述的數學技術也可能有助於解決蛇形遊走（或其他演算法）是否可以找到路徑的問題。在那年晚些時候搬到馬里蘭州後，他與 Childs 開始合作，希望能果斷地解決這個問題。
Childs、Coudron 和他們的研究生 Amin Shiraz Gilani 首先做了兩個假設來限制問題的範圍。首先，他們決定忽略那些試圖傳送到圖中隨機點以期偶然發現出口的古怪演算法。這種策略就像試圖透過尋找漏洞來利用來擊敗電子遊戲——技術上可能，但違背了問題的精神。也很難想象這種行為會有所幫助，因為在大圖上，落在正確位置的機率變得微乎其微。忽略隨機跳躍的演算法使分析剩餘的演算法變得更容易，作者將這些演算法稱為“真正的”演算法——這些演算法包括 Rosmanis 的蛇形遊走演算法，以及可能還有其他人尚未發現的其他演算法。
作者的第二個更實質性的假設是，快速尋路演算法將保持“紮根”——也就是說，它將建立一條通往出口節點的路徑，而永遠不會丟失對入口的跟蹤。許多蛇形遊走是紮根的，但原則上，非紮根的蛇形遊走可能會找到通往出口的路徑——它必須從入口節點分離，然後在稍後找到入口和出口。
這三位研究人員證明，對於每個真正的紮根量子演算法，他們都可以設計出一種經典演算法來模擬其可觀察的行為。由於他們還可以證明，沒有經典演算法可以快速找到出口，因此這足以排除這一大類可能的量子尋路演算法。真正的紮根演算法根本無法聚集足夠的干涉來找到透過迷宮的路徑。
前進的道路
新的結果不一定是故事的結局。“即使在研究量子演算法相當長一段時間後，它們仍然讓我感到驚訝，”米德爾伯里學院的計算機科學家 Shelby Kimmel 在一封電子郵件中寫道。可能仍然存在研究人員考慮的類別之外的巧妙尋路演算法，只是等待被發現。
雖然非真正的演算法似乎極不可能奏效，但非紮根演算法或許可以透過從中間某個位置開始構建從入口到出口的路徑。“也許你可以將其設定為蛇進入並變得非紮根的方式，但隨後不知何故決定伸展開來，”Childs 說。“這仍然沒有排除。”
研究人員尚未找到 Childs 和他的同事 20 年前發現的指數級量子加速的實際應用，部分原因是它依賴於焊接樹圖的特殊對稱性，而這種對稱性不太可能存在於任何現實世界的網路中。但通常，瞭解量子演算法不能做什麼也具有同樣的價值。Shor 發現了一種用於分解大數的快速量子演算法，這威脅要破壞最先進的密碼學，強調了需要已知對量子演算法也很難的問題。
一種不受 Shor 演算法攻擊的密碼學依賴於在特定圖上難以找到點之間路徑的假設。透過焊接樹進行尋路的證據對於量子演算法來說確實很困難，這可能會激勵研究人員開發基於焊接樹圖的新密碼協議，儘管他們到目前為止還沒有取得任何成功。
“也許這意味著這個問題中存在的結構型別不適合編碼我們關心的那些問題，”Childs 說。“或者也許你只需要以正確的方式看待它。”
經 Quanta 雜誌 許可轉載，西蒙斯基金會 的編輯獨立出版物，其使命是透過報道數學以及物理和生命科學領域的研究進展和趨勢來增強公眾對科學的理解。閱讀此處的原始文章。