本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
Daniel Simon 於 1994 年發現了一種有效的量子演算法，用於查找 Z(2)(n) 的“隱藏移位”，這提供了第一個代數問題，量子電腦的速度比經典電腦的速度呈指數級增長。在本文中，我們研究西蒙問題對任意群的推廣。固定有限群 G，這是恢復右箭頭上的對合 (m) 的問題 = (m(1),..., m(n)) 是來自預言機 f 的 G(n) 的元素，其屬性為 f ((x) 右箭頭上。(y) 右箭頭上) = f ((x) 右箭頭箭頭) 雙箭頭上 (用目前的說法，這是 G(n) 形式的群上的隱藏子群問題 (HSP)，其中 G 是大小恆定的非阿貝爾群，並且隱藏子群要么是平凡的，要么是二階的。儘管 G(n) 形式的群具有簡單的乘積結構，但它們與對稱群 S-n 共享重要的表示論性質，其中 HSP 的解決方案將產生圖同構的量子演算法。特別是，用所謂的「標準方法」來解 HSP 需要對許多陪集態的張量積進行高度糾纏的測量。在本文中，我們提供了時間複雜度為 2(O(root n)) 的量子演算法，該演算法在右箭頭 = (m(1),..., m(n)) 上恢復隱藏的對合 (m) 是 G(n) 的一個元素，其中，如 Simon 的問題一樣，每個 m(i) 是已知元素上限，滿足恆等的元素上限，滿足 Dappam = kappak( ) 是滿足的元素上限，滿足 2Gappam = kappak 的元素上限，滿足恆等。我們的方法將庫柏伯格二面群篩法背後的一般想法與摩爾和羅素的「缺失諧波」方法結合。這些是第一個針對需要高度糾纏多寄存器傅立葉採樣的群族的重要 HSP 演算法。