論文の概要: A scalable quantum-enhanced greedy algorithm for maximum independent set problems

• arxiv url: http://arxiv.org/abs/2601.21923v1
• Date: Thu, 29 Jan 2026 16:14:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-30 16:22:49.978767
• Title: A scalable quantum-enhanced greedy algorithm for maximum independent set problems
• Title（参考訳）: 最大独立集合問題に対するスケーラブルな量子強化グリードアルゴリズム
• Authors: Elisabeth Wybo, Jami Rönkkö, Olli Hirviniemi, Jernej Rudi Finžgar, Martin Leib,
• Abstract要約: 正規グラフ上の最大独立集合問題を解くためのハイブリッド量子古典アルゴリズムについて検討する。 このアルゴリズムを20kbitのIQM超伝導デバイス上に実装し,数千ノードのグラフに独立した集合を求める。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate a hybrid quantum-classical algorithm for solving the Maximum Independent Set (MIS) problem on regular graphs, combining the Quantum Approximate Optimization Algorithm (QAOA) with a minimal degree classical greedy algorithm. The method leverages pre-computed QAOA angles, derived from depth-$p$ QAOA circuits on regular trees, to compute local expectation values and inform sequential greedy decisions that progressively build an independent set. This hybrid approach maintains shallow quantum circuit and avoids instance-specific parameter training, making it well-suited for implementation on current quantum hardware: we have implemented the algorithm on a 20 qubit IQM superconducting device to find independent sets in graphs with thousands of nodes. We perform tensor network simulations to evaluate the performance of the algorithm beyond the reach of current quantum hardware and compare to established classical heuristics. Our results show that even at low depth ($p=4$), the quantum-enhanced greedy method significantly outperforms purely classical greedy baselines as well as more sophisticated approximation algorithms. The modular structure of the algorithm and relatively low quantum resource requirements make it a compelling candidate for scalable, hybrid optimization in the NISQ era and beyond.
• Abstract（参考訳）: 本稿では,量子近似最適化アルゴリズム(QAOA)と最小次古典的欲求アルゴリズムを組み合わせた,正規グラフ上の最大独立集合(MIS)問題を解くためのハイブリッド量子古典アルゴリズムについて検討する。 この方法は、通常の木の深さ$p$QAOA回路から導かれる事前計算されたQAOA角を利用して、局所的な期待値を計算し、段階的に独立した集合を構築するための逐次的な欲求決定を通知する。 このハイブリッドアプローチは、浅い量子回路を維持し、インスタンス固有のパラメータトレーニングを回避し、現在の量子ハードウェアの実装に適している。 テンソルネットワークシミュレーションを行い、現在の量子ハードウェアの範囲を超えてアルゴリズムの性能を評価し、確立された古典的ヒューリスティックスと比較する。 その結果、低深さ(p=4$)でも、量子強化グリード法は、より洗練された近似アルゴリズムと同様に、純粋に古典的なグリード法よりも著しく優れていた。 アルゴリズムのモジュラ構造と比較的低い量子リソース要求により、NISQ時代以降のスケーラブルでハイブリッドな最適化の候補となる。

関連論文リスト

• RhoDARTS: Differentiable Quantum Architecture Search with Density Matrix Simulations [44.13836547616739]
  変分量子アルゴリズム(VQA)は、ノイズ中間スケール量子(NISQ)コンピュータを活用するための有望なアプローチである。 与えられたVQA問題を効率的に解く最適な量子回路を選択することは、非自明な作業である。 量子アーキテクチャ探索(QAS)アルゴリズムは、与えられた問題に合わせた量子回路の自動生成を可能にする。
  論文  参考訳（メタデータ） (2025-06-04T08:30:35Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。 本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
  論文  参考訳（メタデータ） (2025-04-21T18:19:19Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  変分量子アルゴリズムは, 近い将来, 古典的アルゴリズムの代替となる可能性が示唆された。 特に、2つのアルゴリズム、すなわち量子近似最適化アルゴリズム(QAOA)と変分量子固有解器(VQE)の性能を比較した。 シミュレーション実験は、クラウドと2つのエッジノードを含む %CM230124 の単純な問題に対して実施され、VQE アルゴリズムは、検索空間を制限できる適切な回路テクスタイタンサッチを備えている場合に、より良い性能を保証することを示す。
  論文  参考訳（メタデータ） (2024-01-25T17:37:40Z)
• Quantum Architecture Search with Unsupervised Representation Learning [24.698519892763283]
  教師なし表現学習は量子アーキテクチャ探索(QAS)を前進させる新しい機会を提供する QASは変分量子アルゴリズム(VQA)のための量子回路を最適化するように設計されている
  論文  参考訳（メタデータ） (2024-01-21T19:53:17Z)
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms [0.0]
  我々は、反復最大量子アルゴリズム(Iterative Maximum Quantum Algorithms)と呼ばれる、量子最適化のための新しいハイブリッドアプローチのクラスについて研究する。 深度$p=1$のQAOAの場合、このアルゴリズムはMISの古典的欲求アルゴリズムと全く同じ操作と選択を行う。
  論文  参考訳（メタデータ） (2023-09-22T18:00:03Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  本稿では,デジタルカウンセバティック量子最適化(DCQO)パラダイムを用いて,ポートフォリオ最適化のための高速なディジタル量子アルゴリズムを提案する。 提案手法は,アルゴリズムの回路深度要件を特に低減し,解の精度を向上し,現在の量子プロセッサに適している。 我々は,IonQトラップイオン量子コンピュータ上で最大20量子ビットを使用するプロトコルの利点を実験的に実証した。
  論文  参考訳（メタデータ） (2023-08-29T17:53:08Z)
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization [0.0]
  本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。 目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
  論文  参考訳（メタデータ） (2023-05-23T16:17:57Z)
• Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
  古典的に容易に生成できる理想的な状態準備プロトコルを特徴付けることができる。 繰り返し量子ビット結合クラスタ(iQCC)の変種を導入して,これらの要件を満たす手法を提案する。 本研究では, チタン系化合物Ti(C5H5)(CH3)3と (20, 20) 活性空間の複雑な系に研究を拡張した。
  論文  参考訳（メタデータ） (2022-11-18T20:31:10Z)

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

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