Fugu-MT 論文翻訳(概要): On the Computational Power of QAC0 with Barely Superlinear Ancillae

論文の概要: On the Computational Power of QAC0 with Barely Superlinear Ancillae

arxiv url: http://arxiv.org/abs/2410.06499v2
Date: Thu, 31 Oct 2024 02:46:04 GMT
ステータス: 処理完了
システム内更新日: 2024-11-01 17:09:37.133495
Title: On the Computational Power of QAC0 with Barely Superlinear Ancillae
Title（参考訳）: 超線形アンシラを用いたQAC0の計算パワーについて
Authors: Anurag Anshu, Yangjing Dong, Fengning Ou, Penghui Yao,
Abstract要約: 深さ$$d$$mathrmQAC0$回路は、近似次数$ta(n)$の関数を計算するために$n1+3-d$アンシラを必要とする。これは超線形サイズの$mathrmQAC0$上の最初の超線形下界である。
参考スコア（独自算出の注目度）: 10.737102385599169
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: $\mathrm{QAC}^0$ is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore [arXiv: 9903046] as a quantum counterpart of $\mathrm{AC}^0$, along with the conjecture that $\mathrm{QAC}^0$ circuits can not compute PARITY. In this work we make progress on this longstanding conjecture: we show that any depth-$d$ $\mathrm{QAC}^0$ circuit requires $n^{1+3^{-d}}$ ancillae to compute a function with approximate degree $\Theta(n)$, which includes PARITY, MAJORITY and $\mathrm{MOD}_k$. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first superlinear lower bound on the super-linear sized $\mathrm{QAC}^0$. Regarding PARITY, we show that any further improvement on the size of ancillae to $n^{1+\exp(-o(d))}$ would imply that PARITY $\not\in$ QAC0. These lower bounds are derived by giving low-degree approximations to $\mathrm{QAC}^0$ circuits. We show that a depth-$d$ $\mathrm{QAC}^0$ circuit with $a$ ancillae, when applied to low-degree operators, has a degree $(n+a)^{1-3^{-d}}$ polynomial approximation in the spectral norm. This implies that the class $\mathrm{QLC}^0$, corresponding to linear size $\mathrm{QAC}^0$ circuits, has approximate degree $o(n)$. This is a quantum generalization of the result that $\mathrm{LC}^0$ circuits have approximate degree $o(n)$ by Bun, Robin, and Thaler [SODA 2019]. Our result also implies that $\mathrm{QLC}^0\neq\mathrm{NC}^1$.
Abstract（参考訳）: $\mathrm{QAC}^0$ は、任意の単一キュービットユニタリとマルチキュービットトフォリゲートからなる定数深さ多項式サイズの量子回路の族である。ムーア (arXiv: 9903046) によって$\mathrm{AC}^0$ の量子対として導入され、$\mathrm{QAC}^0$ 回路がPARITYを計算できないという予想とともに導入された。この研究において、我々はこの長年の予想を前進させる: 深さ-d$$\mathrm{QAC}^0$回路は、近似次数$\Theta(n)$で関数を計算するために$n^{1+3^{-d}}$ ancillaeを必要とし、PARITY、MAJORITY、$\mathrm{MOD}_k$を含む。さらに、量子状態合成と量子チャネル合成の超線形下界を確立する。これは超線型サイズ $\mathrm{QAC}^0$ 上の最初の超線型下界である。 PARITY については、ancillae のサイズを $n^{1+\exp(-o(d))}$ に改善すると、PARITY $\not\in$ QAC0 となる。これらの下界は、$\mathrm{QAC}^0$回路に低次近似を与えることによって導かれる。低次作用素に適用すると、d$$$$\mathrm{QAC}^0$回路がスペクトルノルムの次数$(n+a)^{1-3^{-d}}$多項式近似を持つことを示す。これは、線型サイズ $\mathrm{QAC}^0$ に対応するクラス $\mathrm{QLC}^0$ が近似次数 $o(n)$ を持つことを意味する。これは、$\mathrm{LC}^0$ 回路が、Bun, Robin, Thaler [SODA 2019] による近似次数 $o(n)$ を持つという結果の量子一般化である。我々の結果は、$\mathrm{QLC}^0\neq\mathrm{NC}^1$であることを意味する。

関連論文リスト

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)
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)
Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文参考訳（メタデータ） (2024-06-03T17:56:58Z)
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)
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)
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)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
Bounds on the QAC$^0$ Complexity of Approximating Parity [0.0]
その結果,QAC回路はサイズに関係なくパリティを近似できることがわかった。 QAC回路は1/2 + exp(-o(n/d))$ perroximation of parityを達成するために少なくとも$Omega(n/d)$ multi-qubit gateを必要とする。
論文参考訳（メタデータ） (2020-08-17T16:51:04Z)

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

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