論文の概要: Quadratic Quantum Speedup for Finding Independent Set of a Graph

• arxiv url: http://arxiv.org/abs/2510.26395v1
• Date: Thu, 30 Oct 2025 11:35:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-31 16:05:09.786309
• Title: Quadratic Quantum Speedup for Finding Independent Set of a Graph
• Title（参考訳）: グラフの独立集合を見つけるための二次量子スピードアップ
• Authors: Xianjue Zhao, Peiyun Ge, Li You, Biao Wu,
• Abstract要約: グラフ内の独立集合を見つけるための量子アディアバティックアルゴリズム(QAA)の二次的高速化が解析的に証明されている。 スケールが$O(n2)$の古典的アルゴリズムと比較して、我々の量子アルゴリズムは、大きなISを見つけるために$O(n2)$の時間複雑性を達成し、サイズ2ISを特定するために$O(n)$に還元する。
• 参考スコア（独自算出の注目度）: 5.668733678326325
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A quadratic speedup of the quantum adiabatic algorithm (QAA) for finding independent sets (ISs) in a graph is proven analytically. In comparison to the best classical algorithm with $O(n^2)$ scaling, where $n$ is the number of vertexes, our quantum algorithm achieves a time complexity of $O(n^2)$ for finding a large IS, which reduces to $O(n)$ for identifying a size-2 IS. The complexity bounds we obtain are confirmed numerically for a specific case with the $O(n^2)$ quantum algorithm outperforming the classical greedy algorithm, that also runs in $O(n^2)$. The definitive analytical and numerical evidence for the quadratic quantum speedup benefited from an analytical framework based on the Magnus expansion in the interaction picture (MEIP), which overcomes the dependence on the ground state degeneracy encountered in conventional energy gap analysis. In addition, our analysis links the performance of QAA to the spectral structure of the median graph, bridging algorithmic complexity, graph theory, and experimentally realizable Rydberg Hamiltonians. The understanding gained provides practical guidance for optimizing near-term Rydberg atom experiments by revealing the significant impact of detuning on blockade violations.
• Abstract（参考訳）: グラフ内の独立集合(IS)を見つけるための量子断熱アルゴリズム(QAA)の二次的高速化が解析的に証明されている。 古典的アルゴリズムのスケールが$O(n^2)$であるのに対し、我々の量子アルゴリズムは、大きなISを見つけるために$O(n^2)$の時間複雑性を達成し、サイズ2ISを特定するために$O(n)$に還元する。 我々が得られる複雑性境界は、$O(n^2)$量子アルゴリズムが古典的なグリーディアルゴリズムより優れており、$O(n^2)$で実行される特定のケースに対して数値的に確認される。 相互作用図(MEIP)のマグナス展開に基づく解析的枠組みから得られる二次量子スピードアップの決定的な解析的および数値的証拠は、従来のエネルギーギャップ分析で発生する基底状態の縮退に依存することを克服している。 さらに、この分析は、中央値グラフのスペクトル構造、ブリッジングアルゴリズムの複雑さ、グラフ理論、および実験的に実現可能なライドベルク・ハミルトニアンのスペクトル構造とQAAの性能を関連付ける。 得られた理解は、封鎖違反に対するデチューニングの重大な影響を明らかにすることで、Rydberg原子実験を短期的に最適化するための実践的なガイダンスを提供する。

関連論文リスト

• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
  NPにおける制約満足度問題の特徴は近似硬度であり、最悪の場合、十分な品質の近似解を見つけることは指数関数的に困難である。 ハミルトニアン時間進化に基づくアルゴリズムでは、原型的にハードなMAX-3-XORSAT問題クラスを通してこの問題を探索する。 近似系におけるランダムなハイパーグラフに対して、エネルギーを$E = N_mathrmunsat-N_mathrmsat$と定義すれば、スペクトルフィルタリングされた量子最適化は$E leq q_mで状態を返す。
  論文  参考訳（メタデータ） (2023-12-11T04:15:55Z)
• A quantum-classical performance separation in nonconvex optimization [7.427989325451079]
  我々は最近提案された量子ハミルトニアン(QHD)アルゴリズムが、このファミリーから$d$Dのクエリを解くことができることを証明した。 一方、総合的な実証研究により、最先端の古典的アルゴリズム/解法はそのような問合せを解決するのにスーパーポリノミカルな時間を必要とすることが示唆されている。
  論文  参考訳（メタデータ） (2023-11-01T19:51:00Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  量子Max-$d$-Cut問題(Quantum Max-$d$-Cut problem)は、プロジェクターに付随する期待エネルギーを、全ての局所相互作用上の2つの$d$-dimensional quditsの非対称部分空間に最大化する量子状態を見つけることである。 我々は,非自明な性能保証を実現するために,有界な純度を持つ混合状態の積状態解を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-09-19T22:53:17Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• The complexity of quantum support vector machines [1.7887848708497243]
  量子サポートベクトルマシンは、カーネル関数を定義するために量子回路を使用する。 二重問題は$O(M4.67/varepsilon2)$量子回路評価で解けることを示す。
  論文  参考訳（メタデータ） (2022-02-28T19:01:17Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  最大独立集合問題の解法として量子アルゴリズムを実験的に検討する。 問題の難易度は解の縮退と局所ミニマの数によって制御される。 最も難しいグラフでは、正確な解を見つける際に超線形量子スピードアップを観測する。
  論文  参考訳（メタデータ） (2022-02-18T19:00:01Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Quantum Algorithm for Approximating Maximum Independent Sets [0.0]
  量子非アベリア断熱混合に基づくグラフの最大独立集合を近似する量子アルゴリズムを提案する。 スパースグラフや密度グラフの場合、平均的な量子アルゴリズムは$alpha(G)$と非常に近い大きさの独立した集合を見つけることができる。
  論文  参考訳（メタデータ） (2020-05-26T23:55:49Z)

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

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