論文の概要: Hybrid quantum-classical algorithms for approximate graph coloring
- arxiv url: http://arxiv.org/abs/2011.13420v2
- Date: Mon, 28 Mar 2022 08:30:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-22 22:34:41.699293
- Title: Hybrid quantum-classical algorithms for approximate graph coloring
- Title(参考訳): 近似グラフ彩色のためのハイブリッド量子古典アルゴリズム
- Authors: Sergey Bravyi, Alexander Kliesch, Robert Koenig, Eugene Tang
- Abstract要約: 量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
- 参考スコア(独自算出の注目度): 65.62256987706128
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We show how to apply the recursive quantum approximate optimization algorithm
(RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex
coloring of a graph. We compare this proposal to the best known classical and
hybrid classical-quantum algorithms. First, we show that the standard
(non-recursive) QAOA fails to solve this optimization problem for most regular
bipartite graphs at any constant level $p$: the approximation ratio achieved by
QAOA is hardly better than assigning colors to vertices at random. Second, we
construct an efficient classical simulation algorithm which simulates level-$1$
QAOA and level-$1$ RQAOA for arbitrary graphs. In particular, these hybrid
algorithms give rise to efficient classical algorithms, and no benefit arising
from the use of quantum mechanics is to be expected. Nevertheless, they provide
a suitable testbed for assessing the potential benefit of hybrid algorithm: We
use the simulation algorithm to perform large-scale simulation of level-$1$
QAOA and RQAOA with up to $300$ qutrits applied to ensembles of randomly
generated $3$-colorable constant-degree graphs. We find that level-$1$ RQAOA is
surprisingly competitive: for the ensembles considered, its approximation
ratios are often higher than those achieved by the best known generic classical
algorithm based on rounding an SDP relaxation. This suggests the intriguing
possibility that higher-level RQAOA may be a potentially useful algorithm for
NISQ devices.
- Abstract(参考訳): 本稿では,再帰的量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
この提案を、最もよく知られた古典的およびハイブリッドな古典量子アルゴリズムと比較する。
まず、標準(再帰的でない)qaoaは、任意の一定レベルの任意の正規二部グラフに対してこの最適化問題を解こうとしないことを示す: qaoaによって達成された近似比は、ランダムに頂点に色を割り当てるよりも、ほとんど良いものではない。
第二に、任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートする効率的な古典的シミュレーションアルゴリズムを構築する。
特に、これらのハイブリッドアルゴリズムは効率的な古典的アルゴリズムを生み出し、量子力学の使用による利益は期待できない。
それにもかかわらず、ハイブリッドアルゴリズムの潜在的な利点を評価するための適切なテストベッドを提供する:我々はシミュレーションアルゴリズムを使用して、ランダムに生成された3ドルカラーのコンスタント次グラフのアンサンブルに適用された最大300ドルのクトリットでレベル-$qaoaとrqaoaの大規模シミュレーションを行う。
考慮されたアンサンブルに対して、その近似比は、sdp緩和を丸めることに基づく最もよく知られた古典的アルゴリズムによって達成されるものよりもしばしば高い。
これは、より高いレベルのRQAOAがNISQデバイスにとって潜在的に有用なアルゴリズムである可能性を示唆している。
関連論文リスト
- Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph
Classification [0.9935277311162707]
2つのグラフが互いに小さいかどうかを決定するNP完全問題に対するハイブリッド量子古典アルゴリズムを提案する。
ワンショット分類精度と入力スクイーズ量とのトレーディングが可能なグラフ埋め込みを見つける。
本稿では,グラフスペクトルに基づく新しい古典的アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-02-05T21:24:11Z) - An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。
QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。
この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
論文 参考訳(メタデータ) (2023-02-09T07:47:06Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳(メタデータ) (2022-06-14T08:14:14Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳(メタデータ) (2022-03-01T19:47:16Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳(メタデータ) (2021-06-22T11:07:38Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳(メタデータ) (2021-06-10T16:28:23Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Generating Target Graph Couplings for QAOA from Native Quantum Hardware
Couplings [3.2622301272834524]
本稿では,Ising型量子スピン系における限定大域制御を用いた任意の対象結合グラフの構築手法を提案する。
本手法は、量子近似最適化アルゴリズム(QAOA)をトラップされたイオン量子ハードウェア上に実装することによるものである。
Max-Cut QAOAのノイズシミュレーションにより、我々の実装は標準ゲートベースのコンパイルよりもノイズの影響を受けにくいことが示された。
論文 参考訳(メタデータ) (2020-11-16T18:43:09Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。