論文の概要: 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（参考訳）: 量子デバイスの急速な進化は、古典コンピューティングに対する量子優位性を実験的に確立するための努力を加速させた。 しかし、多くの量子優位性の実証は、計算的仮定と検証問題に頼っている。 さらに、古典的アルゴリズムと機械学習の安定した進歩は、証明可能で事実上実証可能な量子優位性という問題を移動目標にしている。 本研究では,並列量子計算が従来よりも計算能力が高いことを示す。 可変表現率を持つニューラルネットワークをモデル化する定数深さの多項式偏差閾値回路は、局所ゲートを持つ小さな定数深度量子回路で解ける特定の問題を解くことができず、量子的に大きな計算パワーを許容するバイアスの値が証明される。 さらに、有界接続を持つ素次元量子ドット上の普遍量子コンピュータによって一定深さで解ける問題の族を同定するが、多項式サイズのバイアスしきい値回路では困難である。 これにより、より高次元の非局所ゲームの基本理論を、幅広い物理プラットフォームで動作する新興デバイスに計算上の優位性を持たせることができる。 最後に、これらの量子的優位性は全ての素キューディ次元におけるノイズに対して頑健であり、すべての接続性を持ち、実用的魅力を高めていることを示す。

関連論文リスト

• Digital quantum simulation of many-body systems: Making the most of intermediate-scale, noisy quantum computers [51.56484100374058]
  この論文は量子デバイス上の量子力学をシミュレートすることを中心にしている。 本稿では,量子力学における最も関連性の高い量子アルゴリズムの概要を紹介する。 近い将来に量子シミュレーションの恩恵を受けることができる量子力学における関連する問題を同定する。
  論文  参考訳（メタデータ） (2025-08-29T10:37:19Z)
• Coupled Cluster Downfolding Theory in Simulations of Chemical Systems on Quantum Hardware [9.389379035303165]
  古典的資源が、現在の量子デバイスの制約に適合する次元によって特徴づけられる有効ハミルトニアンを構築するためにどのように使用されるかを示す。 このようなフレキシブルなハイブリッドアルゴリズムは、問題のサイズを利用可能な量子資源に合わせることができ、ノイズの多い中間スケール量子(QNIS)デバイスと将来のフォールトトレラント量子コンピュータの間の橋渡しとして機能する、と我々は主張する。
  論文  参考訳（メタデータ） (2025-07-01T21:34:29Z)
• Quantum Algorithms Without Coherent Quantum Access [0.0]
  ほとんどの量子スピードアップは、古典的な情報をコヒーレントな量子的にアクセスできるサブルーチンに依存している。 このようなアクセスがなければ、量子コンピュータは古典的なコンピュータよりも強いものではないことが示されている。 本研究では,いくつかの量子アルゴリズムの変種を開発する。
  論文  参考訳（メタデータ） (2025-03-04T11:24:28Z)
• 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)
• The multimode conditional quantum Entropy Power Inequality and the squashed entanglement of the multimode extreme bosonic Gaussian channels [53.253900735220796]
  不等式はボゾン量子モードの最も一般的な線形混合の出力の最小条件フォン・ノイマンエントロピーを決定する。 ボソニック量子系は、量子状態における電磁放射の数学的モデルを構成する。
  論文  参考訳（メタデータ） (2024-10-18T13:59:50Z)
• 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)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  量子学習理論の最近の進歩は、様々な古典的な入力によって生成された測定データから、大きな量子ビット回路の線形特性を効率的に学習できるのか? 我々は、小さな予測誤差を達成するためには、$d$で線形にスケーリングするサンプルの複雑さが必要であることを証明し、それに対応する計算複雑性は、dで指数関数的にスケールする可能性がある。 そこで本研究では,古典的影と三角展開を利用したカーネルベースの手法を提案し,予測精度と計算オーバーヘッドとのトレードオフを制御可能とした。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
  本稿では,量子コンピュータによって解を加速できる問題のクラスを記述するためのアプローチを検討する。 初期量子状態を所望の状態に変換するユニタリ演算は、1ビットと2ビットのゲートの列に分解可能である必要がある。
  論文  参考訳（メタデータ） (2024-03-25T15:47:35Z)
• 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)
• Quantum algorithms: A survey of applications and end-to-end complexities [88.57261102552016]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• 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)
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm [0.0]
  本研究は,同種LDEを解くための効率的な量子アルゴリズムを構築するために,量子振幅減衰演算を資源として利用する新しい手法を提案する。 このようなオープンな量子系にインスパイアされた回路は、非干渉法で解の実際の指数項を構成することができることを示す。
  論文  参考訳（メタデータ） (2021-11-10T11:25:32Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• 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)
• Limitations of optimization algorithms on noisy quantum devices [0.0]
  我々は、古典的アルゴリズムと、短期的な量子デバイス上で動作している量子アルゴリズムを比較する透過的な方法を提案する。 我々のアプローチは、量子状態がノイズモデルの定点にどれだけ早く収束するかを決定するエントロピック不等式の組み合わせに基づいている。
  論文  参考訳（メタデータ） (2020-09-11T17:07:26Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Googleの最近の量子超越性実験は、量子コンピューティングがランダムな回路サンプリングという計算タスクを実行する遷移点を示している。 観測された量子ランタイムの利点の制約を、より多くの量子ビットとゲートで検討する。
  論文  参考訳（メタデータ） (2020-05-05T20:11:53Z)

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

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