本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
一段時間以來，人們已經知道圖同構可以簡化為隱藏子群問題（HSP）。更重要的是，量子計算中的大多數指數加速都是透過求解 HSP 實例來獲得的。由此產生的演算法的一個共同特徵是使用量子陪集狀態，它對隱藏子組進行編碼。一個懸而未決的問題是使用這些狀態來解決圖同構問題有多難。 Moore、Russell 和 Schulman [30] 最近表明，一個或一對陪集狀態只能提供指數級少量的資訊。一個潛在的能源來源是糾纏量子測量，它同時作用於許多狀態。我們證明，為了獲得圖同構情況下的有用信息，匹配信息理論上限，至少需要對 Ω(n log n) 陪集態進行糾纏量子測量。這可能被視為負面結果，因為高度糾纏的測量通常似乎很難實現。我們的主要定理非常通用，也排除了對其他一些群的少數陪集狀態使用聯合測量，例如 GL(n,Fpm) 和 Gn，其中 G 是有限的並且滿足合適的屬性。