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

• arxiv url: http://arxiv.org/abs/2411.12608v2
• Date: Sun, 29 Dec 2024 07:53:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-31 16:16:53.589891
• 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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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を解くための実行可能なアプローチである可能性を強調しており、量子コンピューティングの領域にこの問題をもたらす重要なマイルストーンを示している。

関連論文リスト

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

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

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