論文の概要: Hardness and Complexity Transition of Noisy Random Circuit Sampling

• arxiv url: http://arxiv.org/abs/2607.20804v1
• Date: Thu, 23 Jul 2026 00:23:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-24 18:26:25.251872
• Title: Hardness and Complexity Transition of Noisy Random Circuit Sampling
• Title（参考訳）: ノイズランダム回路サンプリングの硬さと複雑度遷移
• Authors: Byeongseon Go, Changhun Oh, Hyunseok Jeong,
• Abstract要約: ランダム回路サンプリングは量子優位性を示す主要な候補である。 中心的な問題は、古典的にシミュラブルかつ古典的にハードな状態の間のノイズ-強度境界を特定することである。 同じアーキテクチャ上のノイズの多いRCSは、古典的なシミュレートが難しいままであることを示す。
• 参考スコア（独自算出の注目度）: 0.49764328892172127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random circuit sampling (RCS) is a leading candidate for demonstrating quantum advantage, supported by strong complexity-theoretic evidence of hardness in the ideal setting and by rapid experimental progress to date. In practice, however, noise is unavoidable, and a central problem is to identify the noise-strength boundary between classically simulable and classically hard regimes. In this work, we establish an architecture-general hardness bound for this boundary for the standard local depolarizing noise of strength $γ$. Assuming the standard average-case #P-hardness conjecture for ideal RCS, we show that, for any circuit architecture satisfying this conjecture, noisy RCS on the same architecture remains hard to simulate classically within any inverse-polynomial total variation distance whenever $γ=O(\log n/(nd))$ for $n$-qubit circuits of depth $d$, unless the polynomial hierarchy collapses. Crucially, noisy-RCS hardness follows without any additional conjectural or architecture-specific assumption beyond those already entering the ideal-RCS hardness framework. Our proof combines a low-degree polynomial extrapolation with a monotonicity reduction showing that efficient classical simulation at one depolarizing noise strength implies efficient simulation at every larger strength. Together, these ingredients transfer the standard ideal-RCS hardness conjecture to sampling hardness at a prespecified noise strength. Finally, combining the convergence-to-uniformity result of Dalzell et al. [Commun. Math. Phys. 405, 78 (2024)] with our monotonicity reduction yields efficient classical simulation for $γ=ω(\log n/(nd))$ on layered, regularly connected architectures. Thus, wherever the two architectural settings overlap, this identifies $γ=Θ(\log n/(nd))$ as the asymptotic complexity-transition scale.
• Abstract（参考訳）: ランダム回路サンプリング(RCS)は量子優位を示す主要な候補であり、理想的な設定における硬さの強い複雑性理論的な証拠と、現在までの急速な実験的進歩によって支えられている。 しかし、実際にはノイズは避けられないものであり、古典的にシミュラブルな状態と古典的にハードな状態の間のノイズ-強度境界を特定することが中心的な問題である。 本研究では, 強度$γ$の標準局所偏極雑音に対して, この境界に対するアーキテクチャ一般硬さを確立する。 理想RCSの標準平均ケース#P-ハードネス予想を仮定すると、この予想を満たす任意の回路アーキテクチャにおいて、多項式階層が崩壊しなければ、$γ=O(\log n/(nd))$ for $n$-qubit circuits of depth $d$に対して、同じアーキテクチャ上のノイズRCSは、任意の逆多項式の総変分距離内で古典的にシミュレートすることが困難である。 重要なことに、ノイズの多いRCS硬さは、既に理想的なRCS硬さフレームワークに入るもの以外に、余分な形やアーキテクチャ固有の仮定を伴わない。 我々は,低次多項式外挿法と単調性低減法を組み合わせることで,1つの非偏極雑音強度における効率的な古典的シミュレーションは,全ての大きな強度における効率的なシミュレーションを意味することを示す。 これらの成分は共に、標準理想RCS硬さ予想を、あらかじめ特定された雑音強度でサンプリング硬さに伝達する。 最後に、Dalzell et al [Commun. Math. Phys. 405, 78 (2024)] の収束-一様性結果と我々の単調性還元を組み合わせれば、層状で周期的に連結されたアーキテクチャ上での$γ=ω(\log n/(nd))$の効率的な古典的シミュレーションが得られる。 したがって、2つのアーキテクチャ設定が重なり合う場合であっても、これは漸近的複雑性-遷移スケールとして$γ=(\log n/(nd))$を識別する。

関連論文リスト

• Polynomial Mixing Times of Simulated Tempering for Mixture Targets by Conductance Decomposition [4.008356608627647]
  位置シフトのみが異なる対数凹成分の混合物から採取した模擬温度計の理論的複雑さについて検討した。 主な結果は、メトロポリス・ランゲヴィンアルゴリズム(MALA)と組み合わせた模擬テンパリングの初めての保証を確立することである。 この証明は、拡張空間上に構築された補助マルコフ連鎖に適用される、$s$コンダクタンスの一般的な状態分解定理に基づいている。
  論文  参考訳（メタデータ） (2025-11-01T21:16:35Z)
• Pauli path simulations of noisy quantum circuits beyond average case [0.3277163122167433]
  深さ$n$ qubitsのランダム量子回路では、パウリパス法を用いて出力状態からのサンプリングを効率よく行うことができる。 我々は、Tゲートであるゲートの分数とノイズ率の相似性について十分な条件を導出し、ノイズがより速い速度で導入された場合、シミュレーションは古典的に容易になることを示す。
  論文  参考訳（メタデータ） (2024-07-22T21:58:37Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD [73.55632827932101]
  SGLDにおけるノイズ構造を操作することにより,情報理論の一般化を最適化する。 低経験的リスクを保証するために制約を課すことで、最適なノイズ共分散が期待される勾配共分散の平方根であることを証明する。
  論文  参考訳（メタデータ） (2021-10-26T15:02:27Z)
• Interactive quantum advantage with noisy, shallow Clifford circuits [0.0]
  本稿では,Grier と Schaeffer の対話プロトコルに耐雑音性を加えるための戦略を示す。 この削減の重要な要素は、古典的なシミュレーションタスクにおける平均ケースの硬さを示すことである。 シュミレートするために$oplus$L-hardの量子タスクでさえそうであることを示す。
  論文  参考訳（メタデータ） (2021-02-13T00:54:45Z)
• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise [4.8728183994912415]
  Valiant(1985)の悪意のあるノイズの存在下で$mathRd$の半空間の効率的なPAC学習を研究します。 Awasthi et alのアルゴリズムのための新しい分析を提示します。 そして、ほぼ最適に近いサンプル複雑性を$tildeo(d)$という値で達成できることを示します。 Bbbshoutyetal (2002) のより一般的で強力なノイズモデルにアルゴリズムと解析を拡張し、ほぼ最適なノイズ耐性とサンプルの複雑さを時間内に達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-02-11T20:18:20Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。 この場合、最先端の結果を上回る新たな複雑さが証明される。 本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
  論文  参考訳（メタデータ） (2020-05-21T17:05:27Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  ランダム量子回路は古典的にシミュレートするのは難しいと見なされる。 典型例の近似シミュレーションは, 正確なシミュレーションとほぼ同程度に困難であることを示す。 また、十分に浅いランダム回路はより一般的に効率的にシミュレーション可能であると推測する。
  論文  参考訳（メタデータ） (2019-12-31T19:00:00Z)

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

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