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.16378v2
Date: Wed, 17 Sep 2025 17:45:34 GMT
ステータス: 翻訳完了
システム内更新日: 2025-09-18 18:41:50.509806
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要約: 並列量子計算は,従来よりも計算能力が高いことを示す。我々は、新しい量子コンピュータに計算上の優位性を持たせて、より高次元の非局所ゲーム理論を橋渡しする。
参考スコア（独自算出の注目度）: 6.8680041558282054
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The rapid evolution of quantum devices fuels concerted efforts to experimentally establish quantum advantage over classical computing. Many demonstrations of quantum advantage, however, rely on computational assumptions and face verification challenges. Furthermore, steady advances in classical algorithms and machine learning make the issue of provable, practically demonstrable quantum advantage a moving target. In this work, we unconditionally demonstrate that parallel quantum computation can exhibit greater computational power than previously recognized. We prove that polynomial-size biased threshold circuits of constant depth -- which model neural networks with tunable expressivity -- fail to solve certain problems solvable by small constant-depth quantum circuits with local gates, for values of the bias that allow quantifiably large computational power. Additionally, we identify a family of problems that are solvable in constant depth by a universal quantum computer over prime-dimensional qudits with bounded connectivity, but remain hard for polynomial-size biased threshold circuits. We thereby bridge the foundational theory of non-local games in higher dimensions with computational advantage on emerging devices operating on a wide range of physical platforms. Finally, we show that these quantum advantages are robust to noise across all prime qudit dimensions with all-to-all connectivity, enhancing their practical appeal.
Abstract（参考訳）: 量子デバイスの急速な進化は、古典コンピューティングに対する量子優位性を実験的に確立するための努力を加速させた。しかし、多くの量子優位性の実証は、計算的仮定と検証問題に頼っている。さらに、古典的アルゴリズムと機械学習の安定した進歩は、証明可能で事実上実証可能な量子優位性という問題を移動目標にしている。本研究では,並列量子計算が従来よりも計算能力が高いことを示す。可変表現率を持つニューラルネットワークをモデル化する定数深さの多項式偏差閾値回路は、局所ゲートを持つ小さな定数深度量子回路で解ける特定の問題を解くことができず、量子的に大きな計算パワーを許容するバイアスの値が証明される。さらに、有界接続を持つ素次元量子ドット上の普遍量子コンピュータによって一定深さで解ける問題の族を同定するが、多項式サイズのバイアスしきい値回路では困難である。これにより、より高次元の非局所ゲームの基本理論を、幅広い物理プラットフォームで動作する新興デバイスに計算上の優位性を持たせることができる。最後に、これらの量子的優位性は全ての素キューディ次元におけるノイズに対して頑健であり、すべての接続性を持ち、実用的魅力を高めていることを示す。

関連論文リスト

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)
Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文参考訳（メタデータ） (2022-07-28T17:50:53Z)
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)

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

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