論文の概要: Solving the Perfect Domination Problem by Quantum Approximate Optimization Algorithm with Small Layers

• arxiv url: http://arxiv.org/abs/2411.12608v1
• Date: Tue, 19 Nov 2024 16:12:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-20 13:36:18.966980
• Title: Solving the Perfect Domination Problem by Quantum Approximate Optimization Algorithm with Small Layers
• Title（参考訳）: 最小層を用いた量子近似最適化アルゴリズムによる完全支配問題の解法
• Authors: Haoqian Pan, Changhong Lu, Yuqing Zheng,
• Abstract要約: 完全支配問題(PDP)は、無線やソーシャルネットワークといった現実のシナリオにおいて重要な応用がある。 量子コンピューティングの最近の進歩により、NP完全問題に対処する量子アルゴリズムの開発が急増した。 この研究は、量子アルゴリズムをPDPに適用する先駆的な取り組みであり、それを解決するための有効性を示している。
• 参考スコア（独自算出の注目度）: 1.345977710890196
• License:
• Abstract: The Perfect Domination Problem (PDP), a classical challenge in combinatorial optimization, has significant applications in real-world scenarios, such as wireless and social networks. Over several decades of research, the problem has been demonstrated to be NP-complete across numerous graph classes. With the recent advancements in quantum computing, there has been a surge in the development of quantum algorithms aimed at addressing NP-complete problems, including the Quantum Approximate Optimization Algorithm (QAOA). However, the applicability of quantum algorithms to the PDP, as well as their efficacy in solving it, remains largely unexplored. This study represents a pioneering effort to apply QAOA, with a limited number of layers, to address the PDP. Comprehensive testing and analysis were conducted across 420 distinct parameter combinations. Experimental results indicate that QAOA successfully identified the correct Perfect Dominating Set (PDS) in 82 cases, including 17 instances where the optimal PDS was computed. Furthermore, it was observed that with appropriate parameter settings, the approximation ratio could achieve a value close to 0.9. These findings underscore the potential of QAOA as a viable approach for solving the PDP, signifying an important milestone that introduces this problem into the realm of quantum computing.
• Abstract（参考訳）: 組合せ最適化における古典的な課題である完全支配問題(PDP)は、無線やソーシャルネットワークのような現実のシナリオにおいて重要な応用がある。 何十年もの間、この問題は多くのグラフクラスでNP完全であることが証明されてきた。 近年の量子コンピューティングの発展に伴い、量子近似最適化アルゴリズム(QAOA)を含むNP完全問題に対処する量子アルゴリズムの開発が急増している。 しかし、PDPへの量子アルゴリズムの適用性や、その解法の有効性は、まだ明らかにされていない。 本研究は,QAOAを限られた層数で適用し,PDPに対処するための先駆的な取り組みである。 総合的な試験と分析は420種類のパラメータの組み合わせで行われた。 実験の結果, 最適PSDが計算された17例を含む82例において, QAOAは正しいPDS(Perfect Domination Set)を同定できた。 さらに,パラメータ設定が適切であれば,近似比が0.9に近い値が得られることがわかった。 これらの発見は、QAOAがPDPを解くための実行可能なアプローチである可能性を強調しており、量子コンピューティングの領域にこの問題をもたらす重要なマイルストーンを示している。

関連論文リスト

• 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)
• 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)

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

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