論文の概要: Bounds on the QAC$^0$ Complexity of Approximating Parity
- arxiv url: http://arxiv.org/abs/2008.07470v3
- Date: Mon, 30 Nov 2020 10:19:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-06 00:59:50.011091
- Title: Bounds on the QAC$^0$ Complexity of Approximating Parity
- Title（参考訳）: 近似パリティのQAC$^0$複雑さに関する境界
- Authors: Gregory Rosenthal
- Abstract要約: その結果,QAC回路はサイズに関係なくパリティを近似できることがわかった。
QAC回路は1/2 + exp(-o(n/d))$ perroximation of parityを達成するために少なくとも$Omega(n/d)$ multi-qubit gateを必要とする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of
arbitrary arity. QAC$^0$ circuits are QAC circuits of constant depth, and are
quantum analogues of AC$^0$ circuits. We prove the following:
$\bullet$ For all $d \ge 7$ and $\varepsilon>0$ there is a depth-$d$ QAC
circuit of size $\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon))$ that
approximates the $n$-qubit parity function to within error $\varepsilon$ on
worst-case quantum inputs. Previously it was unknown whether QAC circuits of
sublogarithmic depth could approximate parity regardless of size.
$\bullet$ We introduce a class of "mostly classical" QAC circuits, including
a major component of our circuit from the above upper bound, and prove a tight
lower bound on the size of low-depth, mostly classical QAC circuits that
approximate this component.
$\bullet$ Arbitrary depth-$d$ QAC circuits require at least $\Omega(n/d)$
multi-qubit gates to achieve a $1/2 + \exp(-o(n/d))$ approximation of parity.
When $d = \Theta(\log n)$ this nearly matches an easy $O(n)$ size upper bound
for computing parity exactly.
$\bullet$ QAC circuits with at most two layers of multi-qubit gates cannot
achieve a $1/2 + \exp(-o(n))$ approximation of parity, even non-cleanly.
Previously it was known only that such circuits could not cleanly compute
parity exactly for sufficiently large $n$.
The proofs use a new normal form for quantum circuits which may be of
independent interest, and are based on reductions to the problem of
constructing certain generalizations of the cat state which we name "nekomata"
after an analogous cat y\=okai.
- Abstract（参考訳）: QAC回路は1量子ビットゲートと任意のアリティのトフォリゲートを持つ量子回路である。
QAC$^0$回路は一定の深さのQAC回路であり、AC$^0$回路の量子アナログである。
$\bullet$ For all $d \ge 7$ and $\varepsilon>0$ サイズ $\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon)$ の深さ-$$QAC回路が存在し、最悪の量子入力において、$n$-qubitパリティ関数を誤差$\varepsilon$ に近似する。
従来, 対数深度のQAC回路が, 大きさに関わらずパリティを近似できるか否かは分かっていなかった。
$\bullet$ 上界からの回路の主成分を含む古典的なQAC回路のクラスを導入し、この成分を近似する古典的なQAC回路である低深さのQAC回路のサイズに厳密な下界を証明します。
1/2 + \exp(-o(n/d))$パリティ近似を達成するには、少なくとも$\omega(n/d)$ multi-qubit ゲートを必要とする。
d = \Theta(\log n)$ のとき、これは計算パリティの計算上界の簡単な$O(n)$サイズとほぼ一致する。
マルチ量子ビットゲートの最大2層を持つ$\bullet$ qac回路は、パリティの1/2 + \exp(-o(n))$の近似は、非クリーンでも達成できない。
以前は、そのような回路は十分に大きな$n$のパリティを正確に計算できないことが知られていた。
この証明は、独立興味を持つ量子回路の新しい正規形を用いており、猫のy\=okaiの類似語にちなんで「ネコマタ」と命名する猫状態の特定の一般化問題への還元に基づいている。
関連論文リスト
- Low-degree approximation of QAC$^0$ circuits [0.0]
パリティ関数はQAC$0$で計算できないことを示す。
また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
論文 参考訳（メタデータ） (2024-11-01T19:04:13Z) - On the Computational Power of QAC0 with Barely Superlinear Ancillae [10.737102385599169]
深さ$$d$$mathrmQAC0$回路は、近似次数$ta(n)$の関数を計算するために$n1+3-d$アンシラを必要とする。
これは超線形サイズの$mathrmQAC0$上の最初の超線形下界である。
論文 参考訳（メタデータ） (2024-10-09T02:55:57Z) - Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。
十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
論文 参考訳（メタデータ） (2024-08-29T09:40:55Z) - A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳（メタデータ） (2024-06-17T20:54:11Z) - On the Pauli Spectrum of QAC0 [2.3436632098950456]
我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。
我々は新しい回路の低境界と学習結果を応用として得る。
論文 参考訳（メタデータ） (2023-11-16T07:25:06Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Adaptive constant-depth circuits for manipulating non-abelian anyons [65.62256987706128]
北エフの量子二重モデルは有限群$G$に基づく。
本稿では, (a) 基底状態の生成, (b) 任意の距離で分離されたエノン対の生成, (c) 非破壊的トポロジカル電荷測定のための量子回路について述べる。
論文 参考訳（メタデータ） (2022-05-04T08:10:36Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and
Energy [0.0]
しきい値回路$C$ of size $s$, depth $d$, energy $e$ and weight $w$ satisfies $log (rk(M_C)) le ed。
離散化ReLE回路や復号化シグモノイド回路などの他のニューラルネットワークのモデルに対しては、同様の不等式が離散化回路の$C$についても成り立つことを証明している。
論文 参考訳（メタデータ） (2021-07-01T05:37:53Z) - Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
本稿では量子回路マッピングQXXとその機械学習バージョンQXX-MLPを紹介する。
後者は、レイアウトされた回路の深さが小さくなるように最適なQXXパラメータ値を自動的に推論する。
近似を用いてレイアウト法を学習可能な経験的証拠を提示する。
論文 参考訳（メタデータ） (2020-07-29T05:26:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。