論文の概要: $\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$回路が幅広いブール関数を計算可能であることを証明した。 その過程で,いくつかの近似定数深度構造を正確にする振幅増幅手法を導入する。

関連論文リスト

• Linear-Size QAC0 Channels: Learning, Testing and Hardness [13.101369903953804]
  現在の雑音量子ハードウェアは、短時間で忠実な量子計算しか実行できない。 本稿では,サブ指数実行時間とクエリを用いた$mathbfQAC0$チャネルの最初のアルゴリズムを提案する。 また,Choi行列のスペクトルノルム距離とダイヤモンドノルム距離の両方の下で,$mathbfQAC0$チャネルを学習する際のクエリ複雑性を指数関数的に低くする。
  論文  参考訳（メタデータ） (2025-10-01T07:19:38Z)
• Low-degree approximation of QAC$^0$ circuits [0.0]
  パリティ関数はQAC$0$で計算できないことを示す。 また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
  論文  参考訳（メタデータ） (2024-11-01T19:04:13Z)
• 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)
• On the Pauli Spectrum of QAC0 [2.3436632098950456]
  我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。 我々は新しい回路の低境界と学習結果を応用として得る。
  論文  参考訳（メタデータ） (2023-11-16T07:25:06Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• 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)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• 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)

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

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