Fugu-MT 論文翻訳(概要): QAC0 Can Prepare Every Logarithmic-Qubit State

論文の概要: QAC0 Can Prepare Every Logarithmic-Qubit State

arxiv url: http://arxiv.org/abs/2609.17408v1
Date: Tue, 15 Sep 2026 16:35:52 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-16 14:56:08.621135
Title: QAC0 Can Prepare Every Logarithmic-Qubit State
Title（参考訳）: QAC0はすべての対数量子状態を準備できる
Abstract要約: $mathsfQAC0$は定数深度$mathrmpoly(n)$-ancilla回路のクラスである。すべての$O(log n)$-qubit状態は、$mathrmpoly(n)$-ancilla $mathsfQAC0$サーキットによって正確に、クリーンに作成できることを示す。
参考スコア（独自算出の注目度）: 1.4018975578160688
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: $\mathsf{QAC}^0$ is the class of constant-depth $\mathrm{poly}(n)$-ancilla circuits obtained by extending $\mathsf{QNC}^0$, the class of local circuits, to include nonlocal interactions via arbitrary width Toffoli gates. It is believed to be weaker than its counterpart, $\mathsf{QNC}^0_f$, obtained by including arbitrary-width FANOUT gates instead ($\mathsf{QAC}^0 \subseteq \mathsf{QNC}^0_f$ [Moo99]). In this note, we show that every $O(\log n)$-qubit state can be exactly and cleanly prepared by a $\mathrm{poly}(n)$-ancilla $\mathsf{QAC}^0$ circuit. Previous known $\mathrm{poly}(n)$-ancilla circuits for arbitrary such states are only known via additional access to either FANOUT or QRAM (indexing) gates [Ros21b, GGJ26b], neither of which are known to be in $\mathsf{QAC}^0$. Equivalently, prior constructions of arbitrary $n$-qubit states in $\mathsf{QAC}^0$ require doubly exponential size and we obtain an exponential factor improvement.
Abstract（参考訳）: $\mathsf{QAC}^0$ は、局所回路のクラスである $\mathsf{QNC}^0$ を拡張して得られる定数深度 $\mathrm{poly}(n)$-ancilla 回路のクラスである。代わりに任意の幅の FANOUT ゲート ($\mathsf{QAC}^0 \subseteq \mathsf{QNC}^0_f$ [Moo99]) を含むことにより得られる。ここでは、すべての$O(\log n)$-qubit状態が、$\mathrm{poly}(n)$-ancilla $\mathsf{QAC}^0$回路によって正確に、クリーンに作成可能であることを示す。既知の$\mathrm{poly}(n)$-ancilla 回路は FANOUT または QRAM (indexing) ゲート [Ros21b, GGJ26b] への追加アクセスによってのみ知られ、どちらも $\mathsf{QAC}^0$ ではない。同様に、$\mathsf{QAC}^0$ における任意の $n$-qubit 状態の以前の構成は2倍指数関数のサイズを必要とし、指数係数の改善が得られる。

関連論文リスト

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)
On the Capacity Region of Individual Key Rates in Vector Linear Secure Aggregation [55.126702858312456]
すべてのユーザがキーを保持する必要はないことを示し、それによって文学における最もよく知られた到達可能な領域を厳密に拡大する。以上の結果から,各ユーザがキーを保持する必要はないという新たな事実が明らかになった。
論文参考訳（メタデータ） (2026-01-06T18:34:07Z)
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)
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)
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)
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)

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

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