論文の概要: Local to Global: A Distributed Quantum Approximate Optimization
Algorithm for Pseudo-Boolean Optimization Problems
- arxiv url: http://arxiv.org/abs/2310.05062v2
- Date: Tue, 10 Oct 2023 02:11:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-12 12:55:47.140308
- Title: Local to Global: A Distributed Quantum Approximate Optimization
Algorithm for Pseudo-Boolean Optimization Problems
- Title（参考訳）: local to global:pseudo-boolean optimization problemのための分散量子近似最適化アルゴリズム
- Authors: Bo Yue, Shibei Xue, Yu Pan, Min Jiang, Daoyi Dong
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)は、量子超越性を実証するための有望な候補と考えられている。
量子ビットの可用性が制限され、コヒーレンス時間制限がQAOAに挑戦し、大規模な擬ブール問題を解く。
本稿では,これを単純化したIsingモデルに変換することで,一般の擬似ブール問題を解く分散QAOAを提案する。
- 参考スコア（独自算出の注目度）: 7.723735038335632
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: With the rapid advancement of quantum computing, Quantum Approximate
Optimization Algorithm (QAOA) is considered as a promising candidate to
demonstrate quantum supremacy, which exponentially solves a class of Quadratic
Unconstrained Binary Optimization (QUBO) problems. However, limited qubit
availability and restricted coherence time challenge QAOA to solve large-scale
pseudo-Boolean problems on currently available Near-term Intermediate Scale
Quantum (NISQ) devices. In this paper, we propose a distributed QAOA which can
solve a general pseudo-Boolean problem by converting it to a simplified Ising
model. Different from existing distributed QAOAs' assuming that local solutions
are part of a global one, which is not often the case, we introduce community
detection using Louvian algorithm to partition the graph where subgraphs are
further compressed by community representation and merged into a higher level
subgraph. Recursively and backwards, local solutions of lower level subgraphs
are updated by heuristics from solutions of higher level subgraphs. Compared
with existing methods, our algorithm incorporates global heuristics into local
solutions such that our algorithm is proven to achieve a higher approximation
ratio and outperforms across different graph configurations. Also, ablation
studies validate the effectiveness of each component in our method.
- Abstract（参考訳）: 量子コンピューティングの急速な進歩により、量子近似最適化アルゴリズム(qaoa)は量子超越性を示す有望な候補と見なされ、量子超越性(quantum supremacy)は二次的非拘束型二分最適化(quantum unconstrained binary optimization、qubo)問題のクラスを指数関数的に解く。
しかし、量子ビットの可用性が制限され、コヒーレンスタイムが制限されたQAOAは、現在利用可能なNear-term Intermediate Scale Quantum (NISQ)デバイスで大規模な擬ブール問題を解く。
本稿では,これを単純化したIsingモデルに変換することで,一般の擬似ブール問題を解く分散QAOAを提案する。
従来の分散QAOAsとは違い、局所解がグローバルな問題の一部であることを前提として、ルービアンアルゴリズムを用いてグラフを分割するコミュニティ検出を導入し、そこでグラフをコミュニティ表現によりさらに圧縮し、より高いレベルのサブグラフにマージする。
低レベル部分グラフの局所解は、再帰的かつ後向きに、高レベル部分グラフの解からのヒューリスティックによって更新される。
従来の手法と比較して,本アルゴリズムは局所解に大域的ヒューリスティックスを組み込んで,より高い近似比と異なるグラフ構成における性能を達成することを証明している。
また,本手法における各成分の有効性についても検討した。
関連論文リスト
- Energy Landscapes for the Quantum Approximate Optimisation Algorithm [0.0]
QAOA anszeのエネルギー景観を様々なグラフでナビゲートするために、流域ホットなグローバルな手法を用いています。
対応するランドスケープは一般的に単一のファンネル組織を持つため、Max-Cut ソリューションの確率がよい低いミニマを見つけることは比較的容易である。
論文 参考訳（メタデータ） (2024-01-09T19:17:01Z) - Quantization-Based Optimization: Alternative Stochastic Approximation of
Global Optimization [0.0]
NP-hard問題における目的関数のエネルギーレベルを定量化するための大域的最適化アルゴリズムを提案する。
数値実験により,提案アルゴリズムはNP-ハード最適化問題の解法において従来の学習法よりも優れていた。
論文 参考訳（メタデータ） (2022-11-08T03:01:45Z) - Ising formulation of integer optimization problems for utilizing quantum
annealing in iterative improvement strategy [1.14219428942199]
繰り返し改善戦略において量子アニーリングを利用するために,整数最適化問題のイジング定式化を提案する。
基底状態と候補解との重なりがしきい値を超えた場合, 完全に連結されたフェロポッツモデルに対して一階相転移を回避できることを解析的に示す。
論文 参考訳（メタデータ） (2022-11-08T02:12:49Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear
Programs [0.4925222726301578]
本稿では、整数線形プログラムの解を見つけることができる任意の量子アルゴリズムをブランチ・アンド・プライス・アルゴリズムに統合する手法を提案する。
量子アルゴリズムの役割は、ブランチ・アンド・プライスに現れるサブプロブレムに対する整数解を見つけることである。
論文 参考訳（メタデータ） (2021-03-29T08:59:26Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - Improving the Quantum Approximate Optimization Algorithm with
postselection [0.0]
組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は3つの正則グラフ上のMaxCut問題に適用される。
理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。
論文 参考訳（メタデータ） (2020-11-10T22:17:50Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳（メタデータ） (2020-06-11T18:49:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。