論文の概要: On the Computational Complexity of Geometrically Local QAC0 circuits

• arxiv url: http://arxiv.org/abs/2604.07178v1
• Date: Wed, 08 Apr 2026 15:07:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-09 17:30:51.600095
• Title: On the Computational Complexity of Geometrically Local QAC0 circuits
• Title（参考訳）: 幾何学的局所QAC0回路の計算複雑性について
• Authors: Yangjing Dong, Fengning Ou, Penghui Yao,
• Abstract要約: 任意の$mathsfQAC0$回路は2次元局所的な$mathsfQAC0$回路で正確にシミュレートできることを示す。 本稿では,Parity関数を計算するために$mathsf1Dtext-QAC0 $ 回路上での対数深度を低くすることを示す。
• 参考スコア（独自算出の注目度）: 13.101369903953804
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The computational complexity of $\mathsf{QAC}^0$, which are constant-depth, polynomial-size quantum circuit families consisting of arbitrary single-qubit unitaries and $n$-qubit generalized Toffoli gates, has gained tremendous focus recently. In this work, we initiate the study of the computational complexity of geometrically local $\mathsf{QAC}^0$ circuits, where all the generalized Toffoli gates act on nearest neighbor qubits. We show that any $\mathsf{QAC}^0$ circuit can be exactly simulated by a two-dimensional geometrically local $\mathsf{QAC}^0$ circuit, i.e., a $\mathsf{2D\text{-}QAC}^{0}$ circuit, with a quadratic size blow-up. This implies that $\mathsf{QAC}^0 = \mathsf{2D\text{-}QAC}^{0}$. We further show that if there existed a $\mathsf{QAC}^0$ circuit that computes Parity with a bounded constant error, then for any $\varepsilon > 0$, there would exist a $\mathsf{2D\text{-}QAC}^{0}$ circuit that exactly computes Parity, with a very "thin" width $n^\varepsilon$. We further study the computational power of $\mathsf{1D\text{-}QAC}^{0} $ circuits, i.e., one-dimensional $\mathsf{QAC}^0$ circuits, which are the "thinnest" $\mathsf{2D\text{-}QAC}^{0}$ circuits. We prove a nearly logarithmic depth lower bound on $\mathsf{1D\text{-}QAC}^{0} $ circuits to compute the Parity function, even if allowing an unlimited number of ancilla. Furthermore, if the inputs are encoded in contiguous qubits, we prove that it requires a nearly linear depth $\mathsf{1D\text{-}QAC}^{0} $ circuit to compute the Parity function. This lower bound is almost tight. The results are proved via the combination of the restriction argument and the light-cone argument. These results may provide a new angle for studying the computational power of $\mathsf{QAC}^0$ circuits and for resolving the long-standing open problem of whether Parity is in $\mathsf{QAC}^0$.
• Abstract（参考訳）: 任意の1量子ビットのユニタリと$n$-qubit一般化トフォリゲートからなる多項式サイズの量子回路ファミリーである$\mathsf{QAC}^0$の計算複雑性は、最近著しく注目されている。 本研究では、幾何学的に局所的な$\mathsf{QAC}^0$回路の計算複雑性の研究を開始する。 任意の $\mathsf{QAC}^0$ 回路は2次元局所的な $\mathsf{QAC}^0$ 回路、すなわち $\mathsf{2D\text{-}QAC}^{0} 回路で正確にシミュレートできることを示す。 これは、$\mathsf{QAC}^0 = \mathsf{2D\text{-}QAC}^{0}$であることを意味する。 さらに、もし有界な定数誤差でパリティを計算する$\mathsf{QAC}^0$回路が存在するなら、任意の$\varepsilon > 0$に対して、非常に「薄い」幅の$n^\varepsilon$でパリティを正確に計算する$\mathsf{2D\text{-}QAC}^{0}$回路が存在する。 さらに、1次元の$\mathsf{QAC}^0$回路である$\mathsf{1D\text{-}QAC}^{0} $回路の計算パワーについて検討する。 無限個のアンシラを許すとしても、Parity関数を計算するために$\mathsf{1D\text{-}QAC}^{0} $ 回路上でほぼ対数深度を低くする。 さらに、入力が連続な量子ビットで符号化されている場合、パーティ関数を計算するのに、ほぼ線形深さ $\mathsf{1D\text{-}QAC}^{0} $ 回路が必要であることが証明される。 この下限はほとんどきつい。 結果は制約引数と光円錐引数の組み合わせによって証明される。 これらの結果は、$\mathsf{QAC}^0$の計算力を研究し、Parityが$\mathsf{QAC}^0$であるかどうかという長年の未解決問題を解くための新しい角度を与えることができる。

関連論文リスト

• 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)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

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