論文の概要: $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)

• arxiv url: http://arxiv.org/abs/2601.03243v1
• Date: Tue, 06 Jan 2026 18:40:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-07 17:02:13.062553
• Title: $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
• Title（参考訳）: $\mathsf{QAC}^0$contains $\mathsf{TC}^0$ (入力の多くのコピーを含む)
• Authors: Daniel Grier, Jackson Morris, Kewen Wu,
• Abstract要約: $mathsfQAC0$は、任意の単一量子ビットゲートと一般化されたトフォリゲートから構成される定数深さ量子回路のクラスである。 我々は、$mathsfQAC0$回路が従来の回路よりもはるかに強力であることを示す。
• 参考スコア（独自算出の注目度）: 0.9023122463034333
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: $\mathsf{QAC}^0$ is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical $\mathsf{AC}^0$ lower bounds to $\mathsf{QAC}^0$ have failed. We give one possible explanation of this: $\mathsf{QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation $\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]$ for decision problems, which also resolves for the first time whether $\mathsf{AC}^0$ could be more powerful than $\mathsf{QAC}^0$. Moreover, we prove that $\mathsf{QAC}^0$ circuits can compute a wide range of Boolean functions if given multiple copies of the input: $\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0$. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.
• Abstract（参考訳）: $\mathsf{QAC}^0$ は任意の単一キュービットゲートと一般化されたトフォリゲートから構成される定数深さ多項式サイズの量子回路のクラスである。 これは、非自明なブール関数の計算に役立たなかった定数深度量子計算の最小の自然クラスであることは間違いない。 それにもかかわらず、古典的な $\mathsf{AC}^0$ 境界を $\mathsf{QAC}^0$ に移植しようとする多くの試みは失敗した。 $\mathsf{QAC}^0$ 回路は従来の回路よりもはるかに強力である。 決定問題に対する非条件分離 $\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]$ を示し、$\mathsf{AC}^0$ が$\mathsf{QAC}^0$ よりも強力であるかどうかを初めて解決する。 さらに、入力の複数のコピーが与えられた場合、$\mathsf{QAC}^0$回路が幅広いブール関数を計算可能であることを証明した。 その過程で,いくつかの近似定数深度構造を正確にする振幅増幅手法を導入する。

関連論文リスト

• 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)
• Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [6.8680041558282054]
  並列量子計算は,従来よりも計算能力が高いことを示す。 我々は、新しい量子コンピュータに計算上の優位性を持たせて、より高次元の非局所ゲーム理論を橋渡しする。
  論文  参考訳（メタデータ） (2024-08-29T09:40:55Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Parity vs. AC0 with simple quantum preprocessing [0.0]
  我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。 私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
  論文  参考訳（メタデータ） (2023-11-22T20:27:05Z)
• Monogamy of entanglement between cones [43.57338639836868]
  モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。 我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
  論文  参考訳（メタデータ） (2022-06-23T16:23:59Z)
• 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)

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

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