論文の概要: Entanglement Barriers from Computational Complexity: Matrix-Product-State Approach to Satisfiability

• arxiv url: http://arxiv.org/abs/2602.20299v1
• Date: Mon, 23 Feb 2026 19:29:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-25 17:34:53.501606
• Title: Entanglement Barriers from Computational Complexity: Matrix-Product-State Approach to Satisfiability
• Title（参考訳）: 計算複雑性からの絡み合い障壁: マトリックス-生産状態アプローチによる満足度
• Authors: Tim Pokart, Frank Pollmann, Jan Carl Budich,
• Abstract要約: 我々は、このNP完全問題に対する指数的硬さを反映して、量子絡み合い障壁が想像上の時間に現れることを論じる。 我々の発見は、この量子に着想を得たアプローチの限界を照らし、量子絡み合いにおいて、純粋に古典的な計算複雑性がどのように現れるかを示すものである。
• 参考スコア（独自算出の注目度）: 0.003748389192021574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We approach the 3-SAT satisfiability problem with the quantum-inspired method of imaginary time propagation (ITP) applied to matrix product states (MPS) on a classical computer. This ansatz is fundamentally limited by a quantum entanglement barrier that emerges in imaginary time, reflecting the exponential hardness expected for this NP-complete problem. Strikingly, we argue based on careful analysis of the structure imprinted onto the MPS by the 3-SAT instances that this barrier arises from classical computational complexity. To reveal this connection, we elucidate with stochastic models the specific relationship between the classical hardness of the $\sharp$P $\supseteq$ NP-complete counting problem $\sharp$3-SAT and the entanglement properties of the quantum state. Our findings illuminate the limitations of this quantum-inspired approach and demonstrate how purely classical computational complexity can manifest in quantum entanglement. Furthermore, we present estimates of the non-stabilizerness required by the protocol, finding a similar resource barrier. Specifically, the necessary amount of non-Clifford operations scales superlinearly in system size, thus implying extensive resource requirements of ITP on different architectures such as Clifford circuits or gate-based quantum computers.
• Abstract（参考訳）: 本稿では,古典コンピュータ上の行列積状態 (MPS) に適用した仮想時間伝搬法 (ITP) を用いて, 3SAT の満足度問題にアプローチする。 このアンザッツは基本的に、NP完全問題に期待される指数的硬さを反映して、想像的な時間で現れる量子絡み合い障壁によって制限される。 厳密には、3SATインスタンスによってMPSにインプリントされた構造を慎重に分析し、この障壁は古典的な計算複雑性から生じると論じる。 この関係を明らかにするために、我々は、$\sharp$P $\supseteq$ NP-complete counting problem $\sharp$3-SAT の古典的硬さと量子状態の絡み合い特性との間の特定の関係を確率モデルで解明する。 我々の発見は、この量子に着想を得たアプローチの限界を照らし、量子絡み合いにおいて、純粋に古典的な計算複雑性がどのように現れるかを示すものである。 さらに、プロトコルが要求する非安定化度の推定を行い、同様のリソースバリアを見つける。 具体的には、必要量の非クリフォード演算はシステムサイズで超直線的にスケールするため、クリフォード回路やゲートベースの量子コンピュータのような異なるアーキテクチャ上でのIPPの広範なリソース要求が示唆される。

関連論文リスト

• Exponential Quantum Speedup on Structured Hard Instances of Maximum Independent Set [0.0]
  我々は、古典的にハードな最大独立集合(MIS)のインスタンス群を特定し、非確率的アディバティック量子最適化アルゴリズムの設計と解析を行う。 このアルゴリズムは時間内に実行され、横フィールド量子と最先端の古典的解法の両方に対して指数的なスピードアップを達成する。 これはスピードアップの根底にある特異な量子機構を特定し、なぜ効率的な古典的なアナログが存在しないのかを説明する。
  論文  参考訳（メタデータ） (2026-01-25T04:18:35Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  量子学習理論の最近の進歩は、様々な古典的な入力によって生成された測定データから、大きな量子ビット回路の線形特性を効率的に学習できるのか? 我々は、小さな予測誤差を達成するためには、$d$で線形にスケーリングするサンプルの複雑さが必要であることを証明し、それに対応する計算複雑性は、dで指数関数的にスケールする可能性がある。 そこで本研究では,古典的影と三角展開を利用したカーネルベースの手法を提案し,予測精度と計算オーバーヘッドとのトレードオフを制御可能とした。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Limitations of Fault-Tolerant Quantum Linear System Solvers for Quantum Power Flow [1.0032961794537367]
  量子コンピュータは、古典的コンピュータにとって難解な問題を解くことを約束する。 現実的な量子優位性は、そのような問題を解くためにエンドツーエンドの時間が量子アルゴリズムで要求される時間を超える場合、そのような問題に対して存在すると言える。 QPFアルゴリズムの使用によるスピードアップは、最先端のアルゴリズムによって解決された古典的なPFと比較して指数関数であるとしばしば主張される。
  論文  参考訳（メタデータ） (2024-02-13T17:36:18Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Learning the Complexity of Weakly Noisy Quantum States [0.5662299435213419]
  ターゲット量子状態の古典的シャドウ表現を利用して、弱雑音量子状態の回路複雑性を予測する。 本研究は,学習アルゴリズムと量子状態複雑性の橋渡しを行い,量子状態の固有特性を特徴付ける学習アルゴリズムのパワーを強調した。
  論文  参考訳（メタデータ） (2023-03-31T06:02:44Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  本稿では,量子回路の初期化を最適化するために,古典計算資源を利用するスケーラブルな手法を提案する。 本手法は, PQCのトレーニング性, 性能を, 様々な問題において著しく向上させることを示す。 古典的コンピュータを用いて限られた量子資源を増強する手法を実証することにより、量子コンピューティングにおける量子と量子に着想を得たモデル間の相乗効果を実証する。
  論文  参考訳（メタデータ） (2022-08-29T15:24:03Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。 量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。 我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
  論文  参考訳（メタデータ） (2021-06-11T18:00:09Z)

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

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