論文の概要: 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に生存可能であることを裏付けるものであり、量子計算パラダイムの中でこの古典的な問題をシチュエーションするための第一歩である。

関連論文リスト

• Quantum optimisation applied to the Quadratic Assignment Problem [4.483208369550461]
  本稿では,量子ウォークに基づく最適化アルゴリズム (NV-QWOA) を用いて,2次アサインメント問題 (QAP) の小型解法の性能について検討する。 目的関数評価の回数と、5から10の施設を持つQAPインスタンス全体にわたる最適あるいはほぼ最適のソリューションに一貫して到達するのに必要となるアルゴリズムの反復数という2つの指標を用いて性能を評価する。 我々の研究は、複雑な量子問題に対する量子ウォークの実用性を強調し、将来の量子最適化アルゴリズムの基礎を確立した。
  論文  参考訳（メタデータ） (2026-01-03T07:50:03Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  多重入力多重出力(MIMO)は6G通信において重要であり、スペクトル効率と信頼性の向上を提供する。 本稿では、送信機と受信機の両方でbビット量子化位相シフト器の問題に対処するために、量子近似最適化アルゴリズム(QAOA)と交互最適化を適用することを検討する。 この量子化ビームフォーミング問題の構造はQAOAのようなハイブリッド古典的手法と自然に一致し、ビームフォーミングで使われる位相シフトは量子回路の回転ゲートに直接マッピングできる。
  論文  参考訳（メタデータ） (2025-10-07T17:53:02Z)
• Evidence of scaling advantage on an NP-Complete problem with enhanced quantum solvers [17.90947220974444]
  NP完全1対3のブール充足性問題に対する拡張量子解法を開発した。 13量子ビットの超伝導量子プロセッサ上で,拡張型ソルバを実験的に実装した。 その結果,NP完全問題に対する量子スピードアップの実証的証拠が得られた。
  論文  参考訳（メタデータ） (2025-08-12T11:52:24Z)
• 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)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  我々はこのプロトコルをバイアス場デジタルダイアバティック量子最適化(BF-DCQO)と呼ぶ。 私たちの純粋に量子的なアプローチは、古典的な変分量子アルゴリズムへの依存を排除します。 基底状態の成功確率のスケーリング改善を実現し、最大2桁まで増大する。
  論文  参考訳（メタデータ） (2024-05-22T18:11:42Z)
• 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)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• 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)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。 本稿では,QAOAの回路深度依存性能について実験的に検討する。 この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
  論文  参考訳（メタデータ） (2020-05-11T17:20:51Z)

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

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