論文の概要: Exploring the Potential of Quantum Approximate Optimization Algorithm in Tackling the Perfect Domination Problem

• arxiv url: http://arxiv.org/abs/2411.12608v4
• Date: Wed, 17 Sep 2025 16:20:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-18 14:28:51.199106
• Title: Exploring the Potential of Quantum Approximate Optimization Algorithm in Tackling the Perfect Domination Problem
• Title（参考訳）: 完全支配問題に対処する量子近似最適化アルゴリズムの可能性を探る
• Authors: Haoqian Pan, Changhong Lu, Yuqing Zheng, Chunxing Yan,
• Abstract要約: Perfect Domination Problem (PDP) は、エラー訂正コード、無線通信ネットワーク、ソーシャルネットワークなどの現実世界のシステムにおける応用を見つける。 本稿では,量子近似最適化アルゴリズム(QAOA)によるPDPのシステマティック調査を開始する。 量子シミュレータ上での15-18キュービットを用いて,6,7,8の3つのベンチマークインスタンス上での解の質を評価し,400以上の異なるパラメータ構成について検討した。
• 参考スコア（独自算出の注目度）: 3.0560534954556764
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Perfect Domination Problem (PDP), a canonical challenge in combinatorial optimization, finds critical applications in real-world systems such as error-correcting codes, wireless communication networks, and social networks. Decades of research have firmly established its NP-completeness across numerous graph classes. Motivated by rapid advances in quantum computing, significant effort has recently been directed toward quantum algorithms for NP-complete problems, most notably the Quantum Approximate Optimization Algorithm (QAOA). Nonetheless, the applicability and efficacy of quantum approaches to the PDP remain entirely unexplored. This paper initiates the first systematic investigation of the PDP via QAOA. We evaluate solution quality on three benchmark instances of 6, 7, and 8 vertices using 15-18 qubits on a quantum simulator, examining more than 400 distinct parameter configurations. Experimental results confirm the algorithm's effectiveness and expose discernible trends in parameter selection. These outcomes substantiate QAOA's viability for the PDP and mark a seminal step toward situating this classical problem within the quantum-computing paradigm.
• Abstract（参考訳）: 組合せ最適化における標準的な課題である完全支配問題(PDP)は、エラー訂正コード、無線通信ネットワーク、ソーシャルネットワークなどの現実のシステムにおいて重要な応用を見出す。 研究の数十年は、多くのグラフクラスでNP完全性を確立してきた。 量子コンピューティングの急速な進歩により、近年、NP完全問題に対する量子アルゴリズム(特に量子近似最適化アルゴリズム(QAOA))への大きな取り組みが進められている。 それでも、PDPに対する量子アプローチの適用性と有効性は、まだ完全に解明されていない。 本稿では,QAOAによるPDPの体系的調査を初めて開始する。 量子シミュレータの15-18キュービットを用いて,6,7,8頂点の3つのベンチマークインスタンス上での解の質を評価し,400以上の異なるパラメータ構成について検討した。 実験により,アルゴリズムの有効性を確認し,パラメータ選択における識別可能な傾向を明らかにする。 これらの結果は、QAOAがPDPに生存可能であることを裏付けるものであり、量子計算パラダイムの中でこの古典的な問題をシチュエーションするための第一歩である。

関連論文リスト

• A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems [4.266376725904727]
  本稿では,NP-hard問題に対する量子最適化手法の評価を目的とした,包括的なベンチマークフレームワークを提案する。 本フレームワークは,多次元クナップサック問題(MDKP),最大独立集合(MIS),二次割当問題(QAP),市場シェア問題(MSP)など,主要な課題に重点を置いている。
  論文  参考訳（メタデータ） (2025-03-15T13:02:22Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
  論文  参考訳（メタデータ） (2025-01-02T05:06:16Z)
• Application of Quantum Approximate Optimization Algorithm in Solving the Total Domination Problem [0.5266869303483376]
  総合支配問題(TDP)はこの分野における古典的かつ批判的な事例である。 量子コンピューティングの最近の進歩は、最適化問題に量子アルゴリズムを適用することに大きな研究をもたらした。 本稿では,量子近似最適化アルゴリズム(QAOA)の先駆的応用について述べる。
  論文  参考訳（メタデータ） (2024-11-01T05:05:14Z)
• Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm [0.5919433278490629]
  独立支配問題(IDP)は、様々な現実のシナリオにおいて実践的な意味を持つ。 IDPの既存の古典的アルゴリズムは計算の複雑さに悩まされている。 本稿では、IDPに対処するための量子近似最適化(QAOA)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-10-22T17:49:00Z)
• Distributed Quantum Approximate Optimization Algorithm on Integrated High-Performance Computing and Quantum Computing Systems for Large-Scale Optimization [1.7099366779394252]
  量子近似最適化アルゴリズム(QAOA)は、ゲートベースの量子コンピューティングシステムに量子スピードアップを提供することで最適化問題を解決することを約束している。 本稿では,分散QAOA(DQAOA)を提案する。 我々はAL-DQAOAを用いてフォトニック構造を最適化することに成功し、ゲートベースの量子コンピューティングを用いた実世界の最適化問題を解くことは我々の戦略で実現可能であることを示唆した。
  論文  参考訳（メタデータ） (2024-07-29T17:42:25Z)
• PO-QA: A Framework for Portfolio Optimization using Quantum Algorithms [4.2435928520499635]
  ポートフォリオ最適化(PO)は、投資ポートフォリオのリスクを最小限に抑えつつ、純利益を最大化することを目的とした金融問題である。 本稿では,量子パラメータの変動を調べるために,新しいスケーラブルなフレームワークPO-QAを提案する。 本結果は,量子機械学習のレンズからPOを理解する上で有効な知見を提供する。
  論文  参考訳（メタデータ） (2024-07-29T10:26:28Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。 本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。 また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
  論文  参考訳（メタデータ） (2024-04-17T11:00:12Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。 本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。 最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。 これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
  論文  参考訳（メタデータ） (2023-10-18T17:59:45Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。 この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。 我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
  論文  参考訳（メタデータ） (2023-06-15T15:28:12Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。 アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
  論文  参考訳（メタデータ） (2022-11-22T18:54:48Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  テンソルネットワーク(TN)アルゴリズムは、パラメタライズド量子回路(PQC)にマッピングできる 本稿では,現実的な量子回路を用いてTN状態を近似する新しいプロトコルを提案する。 その結果、量子回路の逐次的な成長と最適化を含む1つの特定のプロトコルが、他の全ての手法より優れていることが明らかとなった。
  論文  参考訳（メタデータ） (2022-09-01T17:08:41Z)
• Analyzing the behaviour of D'WAVE quantum annealer: fine-tuning parameterization and tests with restrictive Hamiltonian formulations [1.035593890158457]
  D'WAVE Systemsの量子アニールは、最適化問題をエネルギー最小化問題に変換することで解決することができる。 本研究は,実世界の最適化問題に対処する際の量子アニールの挙動に関する有用な洞察と情報を提供することに重点を置いている。
  論文  参考訳（メタデータ） (2022-07-01T07:54:26Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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