本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
我們提出了 QAC(0) 的定義，QAC(0) 是具有任意扇入的 AND 和 OR 閘的恆定深度電路的經典類別 AC(0) 的量子模擬，以及 QACC[q] 的定義，QACC[q] 是 ACC[q] 類別的模擬，其中也允許使用 Mod(q) 閘。我們證明奇偶校驗或扇出允許我們構造量子 MODq，即任何 q 的恆定深度的閘，因此 QACC[2] = QACC。更一般地，我們證明對於任何 q,p > 1，MODq 等價於 MODp（達到恆定深度和多項式大小）。這表示具有無界扇出門的 QAC(0)，表示為 QAC(wf)(0)，與 QACC[q] 和所有 q 的 QACC 相同。由於只要 p 和 q 是不同的質數，ACC[p] 就不等於 ACC[q]，因此 QACC[q] 嚴格來說比其經典對應物更強大，就像允許扇出時的 QAC(0) 一樣。這增加了不斷增長的量子複雜性類別的列表，這些類別被證明比其經典對應物更強大。我們也開發了在相關語言類別方面證明 QACC 上限的技術。我們定義了與 QACC[2] 密切相關的語言類別，並表明它們的受限版本可以透過多項式大小的電路進行模擬。透過進一步的限制，與 QACC[2] 算子相關的語言類別可以透過多項式大小和恆定深度的經典閾值電路來模擬。