Fugu-MT 論文翻訳(概要): Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth

論文の概要: Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth

arxiv url: http://arxiv.org/abs/2408.16378v1
Date: Thu, 29 Aug 2024 09:40:55 GMT
ステータス: 処理完了
システム内更新日: 2024-08-30 14:22:45.098369
Title: Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
Title（参考訳）: 定数深さの有界多項式しきい値回路から無条件に$\mathsf{QNC}^0$を分離する
Authors: Min-Hsiu Hsieh, Leandro Mendes, Michael de Oliveira, Sathyawageeswar Subramanian,
Abstract要約: 制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
参考スコア（独自算出の注目度）: 8.66267734067296
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study classes of constant-depth circuits with gates that compute restricted polynomial threshold functions, recently introduced by [Kum23] as a family that strictly generalizes $\mathsf{AC}^0$. Denoting these circuit families $\mathsf{bPTFC}^0[k]$ for $\textit{bounded polynomial threshold circuits}$ parameterized by an integer-valued degree-bound $k$, we prove three hardness results separating these classes from constant-depth quantum circuits ($\mathsf{QNC}^0$). $\hspace{2em}$ - We prove that the parity halving problem [WKS+19], which $\mathsf{QNC}^0$ over qubits can solve with certainty, remains average-case hard for polynomial size $\mathsf{bPTFC}^0[k]$ circuits for all $k=\mathcal{O}(n^{1/(5d)})$. $\hspace{2em}$ - We construct a new family of relation problems based on computing $\mathsf{mod}\ p$ for each prime $p>2$, and prove a separation of $\mathsf{QNC}^0$ circuits over higher dimensional quantum systems (`qupits') against $\mathsf{bPTFC}^0[k]$ circuits for the same degree-bound parameter as above. $\hspace{2em}$ - We prove that both foregoing results are noise-robust under the local stochastic noise model, by introducing fault-tolerant implementations of non-Clifford $\mathsf{QNC}^0/|\overline{T^{1/p}}>$ circuits, that use logical magic states as advice. $\mathsf{bPTFC}^0[k]$ circuits can compute certain classes of Polynomial Threshold Functions (PTFs), which in turn serve as a natural model for neural networks and exhibit enhanced expressivity and computational capabilities. Furthermore, for large enough values of $k$, $\mathsf{bPTFC}^0[k]$ contains $\mathsf{TC}^0$ as a subclass. The main challenges we overcome include establishing classical average-case lower bounds, designing non-local games with quantum-classical gaps in winning probabilities and developing noise-resilient non-Clifford quantum circuits necessary to extend beyond qubits to higher dimensions.
Abstract（参考訳）: 制限多項式しきい値関数を計算するゲートを持つ定数深さ回路のクラスについて、最近[Kum23]により、$\mathsf{AC}^0$を厳密に一般化する族として導入された。これらの回路群を$\mathsf{bPTFC}^0[k]$ for $\textit{bounded polynomial threshold circuits}$パラメータ化すると、これらのクラスを定数深さ量子回路(\mathsf{QNC}^0$)から分離する3つの硬度結果が証明される。 $\hspace{2em}$ - パリティ半減算問題 [WKS+19] は qubits 上の$\mathsf{QNC}^0$ が確実に解けることを証明し、多項式サイズに対して $\mathsf{bPTFC}^0[k]$ の平均ケースハードは、すべての$k=\mathcal{O}(n^{1/(5d)})$ に対して残る。 $\hspace{2em}$ - 計算量$\mathsf{mod}\ p$を各素数$p>2$に対して構築し、高次元量子システム(`qupits')上の$\mathsf{QNC}^0$回路と、上記の次数有界パラメータに対する$\mathsf{bPTFC}^0[k]$回路との分離を証明する。 $\hspace{2em}$ - どちらの結果も局所確率的ノイズモデルの下でノイズロスであることを証明するため、非Clifford $\mathsf{QNC}^0/|\overline{T^{1/p}}>のフォールトトレラントな実装を導入する。 $\mathsf{bPTFC}^0[k]$回路は、ポリノミアル閾値関数(PTF)のある種のクラスを計算できる。さらに、$k$, $\mathsf{bPTFC}^0[k]$は、サブクラスとして$\mathsf{TC}^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)
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)
A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文参考訳（メタデータ） (2022-01-31T22:19:49Z)
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文参考訳（メタデータ） (2020-12-14T18:14:08Z)
Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文参考訳（メタデータ） (2020-12-03T14:03:20Z)

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

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