摘要 We propose definitions of QAC(0), the 量子 analog o

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

• SFI 頁面

論文資訊

• 類型：已發表論文
• 日期：2002

摘要

We propose definitions of QAC(0), the 量子 analog of the classical class AC(0) of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC[q], the analog of the class ACC[q] where Mod(q) gates are also allowed. We prove that parity or fanout allows us to construct 量子 MODq, gates in constant depth for any q, so QACC[2] = QACC. More generally, we show that for any q,p > 1, MODq is equivalent to MODp (up to constant depth and polynomial size). This implies that QAC(0) with unbounded fanout gates, denoted QAC(wf)(0), is the same as QACC[q] and QACC for all q. Since ACC[p] not equal ACC[q] whenever p and q are distinct primes, QACC[q] is strictly more powerful than its classical counterpart, as is QAC(0) when fanout is allowed. This adds to the growing list of 量子 complexity cla

※ 此為已發表論文，全文需透過期刊付費取得