本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
傅立葉採樣技術使量子演算法相對於現有最好的經典演算法實現了顯著的指數級加速，該技術由 Bernstein 和 Vazirani 引入，並由 Simon 和 Shor 開發為解決隱藏子群問題的方法。事實證明，這種方法對於阿貝爾群是成功的，從而產生了用於因式分解、提取離散對數和其他數論問題的有效演算法。然而，我們表明，即使在最弱的資訊理論意義上，這種方法也無法解決對稱群中的隱藏子群問題。特別是，我們表明這種方法無法解決圖同構問題。我們的工作意味著任何基於陪集態測量的量子方法都必須透過對多個陪集態使用糾纏測量來偏離原始框架。