作品“An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor”是什麼意思？
在An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor中，作者聲稱他們給出了一種多項式時間量子算法，用於在一類整數格上使用次指數逼近因子解決有界距離解碼問題。這個結果什麼意思？它會暗示格密碼學的不安全性嗎？它與Peter Shor的因子分解的量子算法一樣重要嗎？
目前還沒有公開論文，所以這個答案是初步的，基於演講和後續討論中提出的內容。除非有一篇論文可以驗證、評估並與之前的工作和已知結果進行比較，否則無法完全理解。然而，對情況的良好理解似乎已經出現。
tl;dr 是：作者解決的特殊問題很容易使用標準格算法（不需要量子）經典地解決，如本註釋所示。此外，核心的新量子步驟也可以經典地實現（並且更簡單有效）。因此，與我們已經知道的經典方法相比，這項工作沒有顯示出任何量子優勢，也沒有任何關於我們可以經典方法的新內容。詳情如下。
“關於一類整數格”子句是一個非常重要的限定詞。作者解決的 BDD 問題是格是“ $ q $ -ary”並由單個生成 $ n $ -維度模型- $ q $ 向量（或其中的一小部分），模數 $ q \gg 2^{\sqrt{n}} $ , 目標向量在 a $ \ll 2^{-\sqrt{n}} $ 晶格最小距離的因子。此設置與格密碼學中曾經使用過的任何設置相去甚遠（據我所知），因此結果不會對提議的格系統產生任何直接影響。當然，更廣泛的問題是這些技術是否會導致影響格加密的更強結果。
根據演講中給出的描述，幾位專家與會者認為，作者解決的特殊晶格問題很可能已經可以使用已知的經典技術輕鬆解決（不需要量子）。更新：事實證明確實如此，並在本說明中得到證實。換句話說，BDD 問題的特殊形式使得它很容易以已知且不出所料的方式解決。該算法只是 LLL 基礎縮減的標準序列，然後是 Babai 最近平面解碼，但表明這實際上有效依賴於 LLL 的一些更深（但以前已知）的屬性，而不是通常呼叫的屬性。
那麼更廣泛的問題呢：主要技術能否帶來我們目前無法通過經典方式獲得的更強大的結果？事實證明，核心量子步驟所完成的，“最壞情況到平均情況”的轉換，可以使用眾所周知的隨機化技術經典地（並且更簡單和有效）完成 - 所謂的“LWE自我減少”或“( $ q $ -ary) BDD 到 LWE 減少。” 詳見本文第 5 節和定理 5.3以及其中引用的早期作品。
更確切地說， $ n $ 維 $ q $ -ary BDD 表示相對距離 $ \alpha $ （作者考慮的問題）經典地減少到具有錯誤率的 LWE $ \alpha \cdot O(\sqrt{n}) $ . 雖然這種減少對於解決原來的 BDD 問題似乎沒有必要，但它表明核心的新量子步驟可以被經典的東西所取代，其性能至少相同（並且在參數方面可能甚至更好）。這表明主要的量子技術在這種情況下可能沒有任何新穎或令人驚訝的力量。
我創建了一個網站來眾包關於 NP intersect CoNP 中的晶格問題算法的已知資訊：
我們的論文上架了：
https://arxiv.org/abs/2201.13450
為了記錄，這是我們遵循的時間表：
直到 21 年 8 月 17 日，我們都非常徹底地閱讀了古典文學。經典算法也可以，這樣我們就可以將其回饋到量子算法中。但由於基本情況是經過充分研究的隱數問題的最壞情況類型，因此一無所知似乎是合理的。
8/17/21-9/21/21：我們詢問了 5 位專家對這個問題的了解。在一種情況下，我們指出了我們能找到的最好的經典方法。我們沒有收到關於新資訊的回复。
21 年 9 月 21 日：決定在演講中使用帶有一個向量的特殊基本情況，因為（1）它會幫助人們解決它，（2）這是量子研討會上的座談會演講，因此需要為廣大觀眾所接受。只有晶格或只有量子的談話已經是一個挑戰，將兩者結合起來，好吧，試試吧！21 年 9 月 21 日：小組討論了各種可能性，但沒有算法。
21 年 9 月 22 日：我們接觸到了一種針對特殊情況的新經典算法，在明確了我們的算法可以做什麼之後，修訂版概述瞭如何通過分析 LLL 來獲得更一般的情況。
22 年 1 月 31 日：我們的 Schnorr 界尚未收到經典答案。
肖恩