論文の概要: Exponential Quantum Speedup on Structured Hard Instances of Maximum Independent Set

• arxiv url: http://arxiv.org/abs/2601.17686v1
• Date: Sun, 25 Jan 2026 04:18:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-27 15:23:08.210531
• Title: Exponential Quantum Speedup on Structured Hard Instances of Maximum Independent Set
• Title（参考訳）: 最大独立集合の構造的ハードインスタンスの指数量子スピードアップ
• Authors: Vicky Choi,
• Abstract要約: 我々は、古典的にハードな最大独立集合(MIS)のインスタンス群を特定し、非確率的アディバティック量子最適化アルゴリズムの設計と解析を行う。 このアルゴリズムは時間内に実行され、横フィールド量子と最先端の古典的解法の両方に対して指数的なスピードアップを達成する。 これはスピードアップの根底にある特異な量子機構を特定し、なぜ効率的な古典的なアナログが存在しないのかを説明する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Establishing quantum speedup for computationally hard problems of practical relevance, particularly combinatorial optimization problems, remains a central challenge in quantum computation. In this work, we identify a structurally defined family of classically hard maximum independent set (MIS) instances, and design and analyze a non-stoquastic adiabatic quantum optimization algorithm that exploits this structure. The algorithm runs in polynomial time and achieves an exponential speedup over both transverse-field quantum annealing and state-of-the-art classical solvers on these instances, under assumptions supported by analytical and numerical evidence. We identify the essential quantum mechanism enabling the speedup as the use of a non-stoquastic XX-driver to access a larger sign-structured admissible subspace beyond the stoquastic regime, which allows sign-generating quantum interference to create smooth evolution paths that bypass tunneling. This identifies a distinctive quantum mechanism underlying the speedup and explains why no efficient classical analogue is likely to exist. In addition, our analysis produces scalable small-scale models, derived from our structural reduction, that capture the essential dynamics of the algorithm. These models provide a concrete opportunity for verification of the quantum advantage mechanism on currently available universal quantum computers.
• Abstract（参考訳）: 実用的関連性(特に組合せ最適化問題)の計算困難問題に対する量子スピードアップの確立は、量子計算における中心的な課題である。 本研究では、古典的にハードな最大独立集合(MIS)のインスタンスの構造的に定義されたファミリを特定し、この構造を利用する非確率的断熱量子最適化アルゴリズムの設計と解析を行う。 このアルゴリズムは多項式時間で実行され、解析的および数値的エビデンスによって支持された仮定の下で、これらのインスタンス上の横場量子アニールと最先端の古典的解法を指数関数的に高速化する。 我々は,非確率的なXX-ドライバを用いて,量子干渉によってトンネルをバイパスするスムーズな進化経路を創り出すことが可能な量子機構を同定した。 これはスピードアップの根底にある特異な量子機構を特定し、なぜ効率的な古典的なアナログが存在しないのかを説明する。 さらに,本解析は,アルゴリズムの本質的ダイナミクスを捉える構造的縮小から導かれる,スケーラブルな小規模モデルを生成する。 これらのモデルは、現在利用可能な普遍量子コンピュータ上で量子優位メカニズムを検証するための具体的な機会を提供する。

関連論文リスト

• VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [50.95799256262098]
  変分量子回路(VQC)は量子機械学習を約束するが、表現性、訓練性、耐雑音性の課題に直面している。 本稿では,VQCが学習中に古典多層パーセプトロンの第一層重みを生成するハイブリッドアーキテクチャであるVQC-MLPNetを提案する。
  論文  参考訳（メタデータ） (2025-06-12T01:38:15Z)
• Classical Algorithms for Hamiltonian Dynamics Mean Value and Guided Local Hamiltonian Problem [9.550310003133555]
  本稿では,任意の局所量子系の短時間ダイナミクスをシミュレーションする,効率的な古典的アルゴリズムを提案する。 また,探索型局所ハミルトニアン(GLH)問題を定値加算誤差に効率よく解く量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-06T09:59:12Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  量子学習理論の最近の進歩は、様々な古典的な入力によって生成された測定データから、大きな量子ビット回路の線形特性を効率的に学習できるのか? 我々は、小さな予測誤差を達成するためには、$d$で線形にスケーリングするサンプルの複雑さが必要であることを証明し、それに対応する計算複雑性は、dで指数関数的にスケールする可能性がある。 そこで本研究では,古典的影と三角展開を利用したカーネルベースの手法を提案し,予測精度と計算オーバーヘッドとのトレードオフを制御可能とした。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Quantum Dissipative Search via Lindbladians [0.0]
  我々は、構造化されていない古典的な探索空間上の純粋に散逸した量子ランダムウォークを解析する。 ある種のジャンプ演算子は量子過程を古典的過程に複製させ、他方はオープン量子(OQRW)と古典的ランダムウォークの違いをもたらすことを示す。 また,従来観測されていた2次高速化も明らかにし,OQRWは古典的検索ほど効率的ではないことを示した。
  論文  参考訳（メタデータ） (2024-07-16T14:39:18Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  本稿では,量子回路の初期化を最適化するために,古典計算資源を利用するスケーラブルな手法を提案する。 本手法は, PQCのトレーニング性, 性能を, 様々な問題において著しく向上させることを示す。 古典的コンピュータを用いて限られた量子資源を増強する手法を実証することにより、量子コンピューティングにおける量子と量子に着想を得たモデル間の相乗効果を実証する。
  論文  参考訳（メタデータ） (2022-08-29T15:24:03Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。 変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。 量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
  論文  参考訳（メタデータ） (2021-08-09T18:00:05Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  53量子ビット量子プロセッサにおける量子スクランブルのダイナミクスを実験的に検討する。 演算子の拡散は効率的な古典的モデルによって捉えられるが、演算子の絡み合いは指数関数的にスケールされた計算資源を必要とする。
  論文  参考訳（メタデータ） (2021-01-21T22:18:49Z)

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

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