論文の概要: Constrained-optimization Approach Delivers Superior Classical
Performance for Graph Partitioning via Quantum-ready Method
- arxiv url: http://arxiv.org/abs/2006.15067v1
- Date: Fri, 26 Jun 2020 15:55:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-12 11:43:10.635614
- Title: Constrained-optimization Approach Delivers Superior Classical
Performance for Graph Partitioning via Quantum-ready Method
- Title（参考訳）: 量子可読法によるグラフ分割における超古典的性能を実現する制約最適化手法
- Authors: Uchenna Chukwu, Raouf Dridi, Jesse Berwald, Michael Booth, John
Dawson, DeYung Le, Mark Wainger, Steven P. Reinhardt
- Abstract要約: グラフ分割は計算インテリジェンス(NP-hard)グラフ問題の重要な集合である。
我々は2つの異なる量子可読法を用いて問題の解をサンプリングした。
どちらのアプローチも、目的的に構築された古典的なグラフパーティショナよりも優れたパーティショナを提供することがよくあります。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph partitioning is one of an important set of well-known compute-intense
(NP-hard) graph problems that devolve to discrete constrained optimization. We
sampled solutions to the problem via two different quantum-ready methods to
understand the pros and cons of each method. First we formulated and sampled
the problem as a quadratic unconstrained binary optimization (QUBO) problem,
via the best known QUBO formulation, using a best-in-class QUBO sampler running
purely classically. Second, we formulated the problem at a higher level, as a
set of constraints and an objective function, and sampled it with a
constrained-optimization sampler (which internally samples the problem via
QUBOs also sampled classically). We find that both approaches often deliver
better partitions than the purpose-built classical graph partitioners. Further,
we find that the constrained-optimization approach is often able to deliver
better partitions in less time than the bespoke-QUBO approach, without
knowledge of the graph-partitioning problem.
Stepping back from graph partitioning itself, one key controversial question
is whether bespoke algorithms or general tools are more likely to deliver the
power of QCs to real-world users. These results bear on that question, though
they require confirmation on other problems and instances as well as
replacement of the low-level sampler by a QC. Still, this early evidence
supports the proposition that general tools will contribute significantly to a
range of problems, expanding the impact of QCs. This benefit is independent of
the low-level sampler employed, whether software or QC, so reinforces the need
for more work on high-level optimization. An early version of such software is
commercially available in the cloud today, delivering superior classical
performance for some problems, enables quantum-forward organizations to migrate
to quantum-ready methods now.
- Abstract（参考訳）: グラフパーティショニング(Graph partitioning)は、離散的な制約付き最適化に発展するよく知られた計算インセンス(NP-hard)グラフ問題の1つである。
各手法の長所と短所を理解するために、2つの異なる量子対応法を用いてこの問題の解をサンプリングした。
まず,QUBOの定式化による2次非制約バイナリ最適化(QUBO)問題として,クラス内QUBOサンプリング器を純粋に古典的に動作させることにより,問題を定式化し,サンプル化した。
第2に,制約と目的関数のセットとして,より高いレベルで問題を定式化し,制約最適化サンプリング器(QUBOによる内部サンプリングも古典的に行われている)でサンプリングした。
どちらのアプローチも、目的に作られた古典的なグラフパーティショナよりも優れたパーティションを提供することが多いことが分かりました。
さらに, 制約最適化手法は, グラフ分割問題の知識を必要とせず, より少ない時間で, より良い分割を実現できることが判明した。
グラフのパーティショニングそのものから戻ると、重要な議論を巻き起こす問題のひとつは、アルゴリズムや一般的なツールがQCのパワーを現実世界のユーザーに提供できるかどうかだ。
これらの結果は、他の問題や事例の確認や、QCによる低レベルのサンプルの交換が必要であるにもかかわらず、この疑問に当てはまる。
しかし、この初期の証拠は、一般的なツールが様々な問題に大きく貢献し、QCの影響を拡大するという提案を支持している。
この利点は、ソフトウェアであれQCであれ、採用されている低レベルのサンプルとは独立しているため、高レベルの最適化に関するさらなる作業の必要性が強化される。
このようなソフトウェアの初期バージョンは、今日、クラウドで商用提供され、いくつかの問題に対して優れた古典的なパフォーマンスを提供し、量子フォワード組織が現在量子対応の方法に移行することを可能にする。
関連論文リスト
- Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
量子計算カラーブルーを用いて解くのに適した二次非拘束バイナリ最適化(QUBO)問題を定式化する。
この定式化は、最大自己充足力とそれらの間を流れる最小限のパワーを持つコミュニティを見つけることを目的としている。
D-Waveのハイブリッド量子古典解法、古典解法、分枝結合解法などである。
論文 参考訳（メタデータ） (2024-07-09T11:44:58Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - A Hybrid Quantum-Classical Approach to the Electric Mobility Problem [0.8796261172196743]
NP-hard Electric Vehicle Fleet Charging and Allocation Problemのためのハイブリッド量子古典ルーチンを提案する。
分解法の性能を古典的・量子的メタヒューリスティックスで評価する。
提案手法の主な利点は、多くの不等式制約のある現実的な問題に対して量子ベースの方法を可能にすることである。
論文 参考訳（メタデータ） (2023-10-04T12:14:56Z) - Evidence that PUBO outperforms QUBO when solving continuous optimization
problems with the QAOA [4.670374869377859]
量子アルゴリズムによる最適化問題の解決における中核的なステップは、問題の定式化である。
近年の研究では、多くの問題を自然の多項式非制約最適化形式でより効率的に解けることが示されている。
適切なベンチマーク関数の評価では、PUBOの定式化は一般により良い結果をもたらすが、キュービットは少ない。
論文 参考訳（メタデータ） (2023-05-05T09:37:48Z) - QuAnt: Quantum Annealing with Learnt Couplings [18.40480332882025]
我々はデータからQUBOフォームを導出するのではなく、勾配のバックプロパゲーションを通して学習する。
本稿では,グラフマッチングや2次元点雲のアライメント,3次元回転推定といった多種多様な問題に対する学習QUBOの利点を示す。
論文 参考訳（メタデータ） (2022-10-13T17:59:46Z) - Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem [0.8434687648198277]
Bin Packing Problem (BPP) は、ロジスティクスにおけるパラダイム最適化問題として際立っている。
我々は最近,一次元BPPに対するハイブリッドアプローチを提案している。
他の古典的手法と比較する。
論文 参考訳（メタデータ） (2022-07-15T13:09:12Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - Accelerating variational quantum algorithms with multiple quantum
processors [78.36566711543476]
変分量子アルゴリズム(VQA)は、特定の計算上の利点を得るために、短期量子マシンを利用する可能性がある。
現代のVQAは、巨大なデータを扱うために単独の量子プロセッサを使用するという伝統によって妨げられている、計算上のオーバーヘッドに悩まされている。
ここでは、この問題に対処するため、効率的な分散最適化手法であるQUDIOを考案する。
論文 参考訳（メタデータ） (2021-06-24T08:18:42Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。