論文の概要: Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity

• arxiv url: http://arxiv.org/abs/2510.06324v1
• Date: Tue, 07 Oct 2025 18:00:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.123762
• Title: Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
• Title（参考訳）: 近似マルコビアン性下での準多項式時間における古典的な雑音量子回路のサンプリング
• Authors: Yifan F. Zhang, Su-un Lee, Liang Jiang, Sarang Gopalakrishnan,
• Abstract要約: 局所偏極雑音下で量子回路をシミュレーションするために,$nrmpolylog(n)$ timeで動作する古典的アルゴリズムを提案する。 我々の結果は古典的シミュラビリティの境界を大きく拡張し、ノイズがマルコビアン性や古典的シミュラビリティを近似的に強制することを示唆している。
• 参考スコア（独自算出の注目度）: 0.616870773176256
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While quantum computing can accomplish tasks that are classically intractable, the presence of noise may destroy this advantage in the absence of fault tolerance. In this work, we present a classical algorithm that runs in $n^{\rm{polylog}(n)}$ time for simulating quantum circuits under local depolarizing noise, thereby ruling out their quantum advantage in these settings. Our algorithm leverages a property called approximate Markovianity to sequentially sample from the measurement outcome distribution of noisy circuits. We establish approximate Markovianity in a broad range of circuits: (1) we prove that it holds for any circuit when the noise rate exceeds a constant threshold, and (2) we provide strong analytical and numerical evidence that it holds for random quantum circuits subject to any constant noise rate. These regimes include previously known classically simulable cases as well as new ones, such as shallow random circuits without anticoncentration, where prior algorithms fail. Taken together, our results significantly extend the boundary of classical simulability and suggest that noise generically enforces approximate Markovianity and classical simulability, thereby highlighting the limitation of noisy quantum circuits in demonstrating quantum advantage.
• Abstract（参考訳）: 量子コンピューティングは古典的に難解なタスクを達成できるが、ノイズの存在はフォールトトレランスの欠如においてこの利点を損なう可能性がある。 本研究では,局所偏極雑音下での量子回路のシミュレーションに,$n^{\rm{polylog}(n)}$時間で動作する古典的アルゴリズムを提案する。 提案アルゴリズムは, ノイズ回路の測定結果分布から逐次サンプリングを行うために, 近似マルコビアン性と呼ばれる特性を利用する。 我々は, 広い範囲の回路において近似マルコビアン性(マルコビアン性)を確立する: 1) 雑音速度が一定の閾値を超えるとき, 任意の回路に対して有することを示す; (2) 一定の雑音速度を受けるランダム量子回路に対して有する強い解析的および数値的証拠を提供する。 これらのレギュレーションには、以前のアルゴリズムが失敗する反集中のない浅いランダム回路のような、従来知られていた古典的なシミュレート可能なケースや、新しいものが含まれる。 本研究の結果は,古典的シミュラビリティの境界を著しく拡張し,量子的優位性を示すため,ノイズが近似的マルコビアン性や古典的シミュラビリティを強制することが示唆された。

関連論文リスト

• When quantum resources backfire: Non-gaussianity and symplectic coherence in noisy bosonic circuits [1.0874100424278175]
  本稿では,雑音のあるボソニック回路をシミュレーションするための$textitdisplacement propagation$アルゴリズムを提案する。 我々はいくつかの計算位相遷移を同定し、極小ノイズレベルでもボソニック回路を効率よく古典的にシミュレートできる状態を明らかにする。 通常、ボソニックな量子優位性、すなわち非ガウス的性やシンプレクティックなコヒーレンスに関連付けられた計算資源は、古典的にノイズの存在をシミュレートしやすくする。
  論文  参考訳（メタデータ） (2025-10-08T17:25:47Z)
• Limitations of Noisy Geometrically Local Quantum Circuits [0.2039123720459736]
  ノイズが分散した雑音量子回路は、$omega(log n)$ depthで均一分布に収束し、$n$は量子ビットの数である。 我々は、我々の境界はまだゆるいものであり、$Theta(1)$-depthしきい値がパーコレーション効果によるシミュラビリティに十分であると予想する。
  論文  参考訳（メタデータ） (2025-10-07T18:08:23Z)
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings [0.2796197251957244]
  ノイズ量子回路をシミュレーションするための並列化可能なテンソルネットワークに基づく古典的アルゴリズムを提案する。 我々のアルゴリズムは、行列積状態の特定のアンサンブルによるノイズ量子系の状態を表す。
  論文  参考訳（メタデータ） (2025-08-07T18:00:20Z)
• Non-perturbative switching rates in bistable open quantum systems: from driven Kerr oscillators to dissipative cat qubits [72.41778531863143]
  単一モードバイスタブルオープン量子系におけるスイッチング率の予測にはパス積分手法を用いる。 本研究は,マルチ安定な単体および多体オープン量子系におけるスイッチング現象を探索するための新たな道を開く。
  論文  参考訳（メタデータ） (2025-07-24T18:01:36Z)
• Bayesian Quantum Amplitude Estimation [46.03321798937855]
  量子振幅推定のための問題調整およびノイズ認識ベイズアルゴリズムであるBAEを提案する。 耐障害性シナリオでは、BAEはハイゼンベルク限界を飽和させることができ、デバイスノイズが存在する場合、BAEはそれを動的に特徴付け、自己適応することができる。 本稿では,振幅推定アルゴリズムのベンチマークを提案し,他の手法に対してBAEをテストする。
  論文  参考訳（メタデータ） (2024-12-05T18:09:41Z)
• A polynomial-time classical algorithm for noisy quantum circuits [1.2708457954150887]
  雑音量子回路のための時空古典的アルゴリズムを提供する。 我々のアプローチは、雑音が非局所的相関を指数的に減衰させるという直感に基づいている。 定音率の場合、ほとんどの入力状態において誤差緩和が効率的である任意の量子回路は、古典的にはほとんどの入力状態においてシミュレート可能である。
  論文  参考訳（メタデータ） (2024-07-17T17:48:39Z)
• Scalable noisy quantum circuits for biased-noise qubits [37.69303106863453]
  安定猫量子ビットの既存システムに動機づけられたビットフリップ誤差のみに影響されるバイアスノイズ量子ビットを考察する。 現実的なノイズモデルでは、位相フリップは無視できないが、Pauli-Twirling近似では、ベンチマークが最大106ドルのゲートを含む回路の正しさを確認できる。
  論文  参考訳（メタデータ） (2023-05-03T11:27:50Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Googleの最近の量子超越性実験は、量子コンピューティングがランダムな回路サンプリングという計算タスクを実行する遷移点を示している。 観測された量子ランタイムの利点の制約を、より多くの量子ビットとゲートで検討する。
  論文  参考訳（メタデータ） (2020-05-05T20:11:53Z)

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

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