論文の概要: The Robustness of QAC0

• arxiv url: http://arxiv.org/abs/2610.02154v1
• Date: Thu, 01 Oct 2026 17:51:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.356271
• Title: The Robustness of QAC0
• Title（参考訳）: QAC0のロバスト性
• Abstract要約: エラー耐性とゲートセットの変更に関して$mathsfQAC0$のロバスト性について検討する。 並列な$W$-test of citegrier_morris_wuの誤差は完全に、正確な振幅増幅の新たな応用によって排除できることを示す。 すべての$mathsfQAC0$回路は、一般化されたToffoli、$S$およびHadamardゲートからなる$mathsfQAC0$回路で概ね実装できる。
• 参考スコア（独自算出の注目度）: 0.9023122463034333
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work we study the robustness of $\mathsf{QAC}^0$ with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for $\mathsf{QAC}^0$ circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel $W$-test of \cite{grier_morris_wu} can be eliminated entirely via a novel application of exact amplitude amplification in the many-copies context. Consequently, we find that $\mathsf{QAC}^0$ can \textit{exactly} simulate $\mathsf{TC}^0$ with polynomially many copies of the classical input and that for every fixed prime $p$ exact $\mathsf{QAC}^0$, $\mathsf{EQAC}^0$, can compute total Boolean functions outside of $\mathsf{AC}^0[p]$. Second, we ask to what extent the computational power of $\mathsf{QAC}^0$ follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that $\mathsf{QAC}^0$ is in fact robust to restrictions on which single-qubit gates are permitted: every $\mathsf{QAC}^0$ circuit can be approximately implemented by a $\mathsf{QAC}^0$ circuit consisting of just generalized Toffoli, $S$, and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.
• Abstract（参考訳）: この研究では、誤り耐性とゲートセットの変更に関して、$\mathsf{QAC}^0$のロバスト性を研究する。 まず, ブール関数を演算する回路に対して, 一般に$\mathsf{QAC}^0$の非ゼロ誤差が許容されるかどうかを検討する。 We show that the error inherent in the parallel $W$-test of \cite{grier_morris_wu} could be completely by a novel application of exact amplitude amplification in the many-copies context。 したがって、$\mathsf{QAC}^0$ can \textit{exactly} は、古典的な入力の多項式的に多くのコピーで $\mathsf{TC}^0$ をシミュレートし、すべての固定素数$p$ exact $\mathsf{QAC}^0$, $\mathsf{EQAC}^0$ に対して、$\mathsf{AC}^0[p]$ 以外のブール関数を計算できる。 第二に、任意の単一キュービットゲートが回路の任意の点で使用されるという事実から、$\mathsf{QAC}^0$ の計算パワーはどの程度の値になるのかを問う。 すべての$\mathsf{QAC}^0$回路は、単に一般化されたToffoli、$S$およびHadamardゲートからなる$\mathsf{QAC}^0$回路で概ね実装できる。 さらに、この近似回路は、元の回路の古典的な記述から効率的に構築することができる。

関連論文リスト

• QAC0 Can Prepare Every Logarithmic-Qubit State [1.4018975578160688]
  $mathsfQAC0$は定数深度$mathrmpoly(n)$-ancilla回路のクラスである。 すべての$O(log n)$-qubit状態は、$mathrmpoly(n)$-ancilla $mathsfQAC0$サーキットによって正確に、クリーンに作成できることを示す。
  論文  参考訳（メタデータ） (2026-09-15T16:35:52Z)
• On the Computational Complexity of Geometrically Local QAC0 circuits [13.101369903953804]
  任意の$mathsfQAC0$回路は2次元局所的な$mathsfQAC0$回路で正確にシミュレートできることを示す。 本稿では,Parity関数を計算するために$mathsf1Dtext-QAC0 $ 回路上での対数深度を低くすることを示す。
  論文  参考訳（メタデータ） (2026-04-08T15:07:09Z)
• $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input) [0.9023122463034333]
  $mathsfQAC0$は、任意の単一量子ビットゲートと一般化されたトフォリゲートから構成される定数深さ量子回路のクラスである。 我々は、$mathsfQAC0$回路が従来の回路よりもはるかに強力であることを示す。
  論文  参考訳（メタデータ） (2026-01-06T18:40:44Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• On the Pauli Spectrum of QAC0 [2.3436632098950456]
  我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。 我々は新しい回路の低境界と学習結果を応用として得る。
  論文  参考訳（メタデータ） (2023-11-16T07:25:06Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。