?內容來源：量子前哨（ID：Qforepost）
文丨浪味仙??排版丨浪味仙
行業動向：3700字丨10分鐘閱讀
5 月 20 日，由北京量子院、清華大學、數學工程與先進計算國家重點實驗室、南洋理工大學、量子信息前沿科學中心以及北京國家信息科學與技術研究中心共同組成的研究團隊，在知名學術期刊《Communications Physics》上發表了一篇重要研究論文。該論文題為《Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices》（用于解決 NISQ 設備上容錯學習問題的量子經典混合算法），由 Muxi Zheng 擔任第一作者，魏世杰和龍桂魯教授為通訊作者。
該研究提出了一種名為 HAWI（使用伊辛模型的量子+經典混合算法）的新型算法，在應對“容錯學習”（Learning-With-Errors,LWE）問題上帶來了創新突破，可以幫助我們更準確地分析量子計算機的影響，設置密碼的安全參數，為后量子密碼學和 NISQ 設備的實際應用開辟了新的前景。
何為
容錯學習問題？
容錯學習（LWE）問題，是一種在后量子密碼學和計算學習理論中都非常重要的基礎計算難題。
想象你是一名電報員，為了國家安全，你需要通過破譯數字加密電報，找出一串隱藏在某個遠程秘密基地中的“秘鑰”。（責任感和壓迫感是不是齊了~
下面是一些更詳細的信息：
1、在那個遠程的秘密基地中，藏著一串非常重要的“秘鑰”（假設是 996）。你需要找出它，因為它被秘密地存儲在基地中，當然你并不知道。
2、秘密基地中有一個“電報生成器”，它知道“秘鑰”是 996。
3、電報生成器的工作流程是：
a）它會隨機選擇一串數字（比如 123），作為電報的“頭部信息”。
b）它將這串“頭部信息”（123）和“秘密密鑰”（996）進行一番復雜的內部運算，假定二者相減得到結果 873。
c）這時，生成器會在 873 這個結果上故意加一點隨機的“誤差”，但這個誤差很小，比如使 873 變成 874。
d）最后，電報生成器會將“頭部信息”（123）和帶有干擾的運算結果（874）一起發送出去，成為一份“模糊電報”。
身為一名電報員，你會收到很多份這樣的“模糊電報”，每份都帶有正常的隨機干擾，也就是同時包含“頭部信息”和“包含誤差的結果”，你的任務就是利用所有這些真的“模糊電報”（劃重點：真的），通過復雜的分析和計算，最終找出隱藏在秘密基地里的那串“秘鑰”（996）。（對應 LWE-搜索問題）
為什么要劃重點呢？因為如果沒有這個限定詞，你的任務就會發生變化。
倘若你收到的“模糊電報”中，只有一部分是那臺使用“秘鑰”的電報生成器發出的，而另一部分則是完全隨機生成、沒有任何規律可循的亂碼。
此刻，這個任務類似“真假美猴王”：針對每一份收到的電報，判斷它是“使用秘鑰并帶有正常干擾的·真·模糊電報”，還是一份“毫無規律、完全隨機的亂碼”。這種情況下，你不需要找出秘鑰具體是什么，只需要分辨它是否“符合模式”即可。（對應 LWE-決策問題，本篇論文主要關注的是這一種。）
破譯“模糊電報”的任務，難就難在“誤差”上，它令你無法規避大量嘗試和巧妙推理，容錯學習（LWE）問題就是這樣一個從“有噪聲的線性信息”中“學習”出“秘密信息”的問題，正因為有噪聲的存在，才使得該問題的直接求解變得極為困難。
容錯學習（LWE）問題是后量子密碼學的核心計算難題之一，由于其被認為對經典計算機和量子計算機都具有計算難度，因此解決 LWE 問題對于構建未來安全的加密系統至關重要。
基于此，我們走近看看《Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices》（用于解決 NISQ 設備上容錯學習問題的量子經典混合算法）這篇論文是如何應對 LWE 這一問題的。
HAWI 創新算法
論文創新性地提出了一種 HAWI 算法，采用一套“組合拳”來應對容錯學習（LWE）問題，概括來說就是：
將 LWE 問題“轉化”成為“找最短路徑”問題（SVP），再將轉化出的 SVP 問題“編碼”成量子計算機能理解的能量模型（伊辛模型）。接下來，利用 NISQ 設備擅長的量子優化算法（如 QAOA），在經典計算機的配合下，尋找能量模型（伊辛模型）的最低點，從而揭示出 LWE 問題的秘密。
1、把“找秘密”變成“找最短路徑”
LWE 問題本質是“在有噪音的線索中找秘密數字”，論文首先把這個問題巧妙地“轉化”或者說“翻譯”成了另一個經典的數學難題：最短向量問題（Shortest Vector Problem, SVP）。
你可以把 SVP 問題想象成是在一個由很多點組成的“網格”里，我們要找到從原點出發，連接到其他點的“最短的路線”。而這條“最短的路線”，恰好可以對應 LWE 問題中的秘密數字。
這種轉化很重要，因為 SVP 問題雖然也難，但它有成熟的數學框架和算法研究基礎，還更適合量子計算機來處理。
2、量子-經典混合：聰明地分配任務
當前的量子計算機還處于“噪音多、規模小”的階段（NISQ），所以我們不能指望它一口氣解決所有問題。論文提出的 HAWI 算法，采用了量子+經典混合的這樣一種合理搭配，就像團隊協作。
?圖源論文：量子+經典混合算法的工作流程
a）經典計算機：負責把 LWE 問題“轉化”成 SVP 問題，并進一步把 SVP 問題“編碼”成一種量子計算機能理解的語言——伊辛模型（Ising Hamiltonian）。這是一種描述粒子之間相互作用的能量函數，它的最低能量狀態往往對應著問題的解。
b）量子計算機：負責尋找伊辛模型的“最低能量狀態”。找到這個最低能量狀態，就意味著找到了 SVP 問題中的“最短路線”，從而也就找到了 LWE 問題中的“秘密數字”。
c）經典計算機：再把量子計算機找到的這個最低能量狀態“解碼”回 LWE 問題的“秘密數字”。
這種分工合作，充分利用了經典計算機的邏輯處理能力和量子計算機在處理特定優化問題上的巨大優勢，同時還避開了 NISQ 設備現在還無法處理大規模復雜計算的限制。
3、適應 NISQ 設備：利用量子近似優化算法（QAOA）
尋找伊辛模型的最低能量狀態，在量子計算中可以通過多種方法實現，其中一種重要方法就是量子近似優化算法（QAOA）。
QAOA 是專門為 NISQ 設備設計的，它是一種迭代算法，通過不斷調整參數，逐步逼近最優解，能夠在當前的硬件限制下，通過近似和迭代盡可能發揮量子優勢。
本篇論文還特別研究了如何為 QAOA 設計合適的參數，來提高它在解決 LWE 問題上的成功率，就像給 QAOA 做了一本“學習秘籍”，讓它能更有效地找到“最短路線”，以及“秘密數字”。
4、實際驗證：小步快跑
這篇論文的另一個突破是，他們在 IBM 量子平臺上，選擇了 2 維 LWE 問題作為測試對象，用一個 5?量子比特的設備驗證了這種算法，成功解決了小規模的 LWE 問題。值得一提的是，驗證算法所需要的量子比特數量為 m（m+1），其中 m 為樣本數量，而在實際應用中，所需的量子比特數量遠小于這一理論上限。
?圖源論文：結果驗證了方法的有效性
雖然是小規模的 LWE 問題，但這就像是成功地用真實量子設備“點亮了一盞燈”，足以驗證該算法在基本邏輯和流程上的正確性與可行性，為未來解決更大規模的 LWE 問題打下了堅實基礎。
總的來說，論文提出的這種方法結合了經典計算的靈活性和量子計算的特定優勢，是在當前量子技術水平下，邁向解決重要密碼學難題的務實一步。不可避免地，這種方法仍面臨一些挑戰，例如要將這一算法擴展到解決具有實際密碼學意義的更大規模 LWE 問題，其表現仍需進一步驗證。
未來，該研究團隊還將采用其他方法求解哈密頓量基態，如量子虛時間演化、量子蒙特卡洛（QMC）、量子退火、量子行走等，從而進一步研究 LWE 問題。此外，除了本文所述的短整數解（SIS）策略，LWE 問題還有其他解法路徑，如有界距離解碼（BDD）策略，這些方法同樣與格問題密切相關。因此，研究在與量子優化算法結合時，哪些經典策略在求解格問題中更具效率，是一個值得深入探討的方向。
Reference：
https://www.nature.com/articles/s42005-025-02126-w#:~:text=Firstly%2C%20we%20use%20classical%20techniques,is%20closer%20to%20the%20solution.
)
