論文の概要: Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach
- arxiv url: http://arxiv.org/abs/2106.11672v3
- Date: Fri, 25 Mar 2022 14:06:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-25 21:02:23.649968
- Title: Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach
- Title（参考訳）: QAOAとRydberg quditシステムによる相関クラスタリングの解法:フルスタックアプローチ
- Authors: Jordi R. Weggemans, Alexander Urech, Alexander Rausch, Robert Spreeuw,
Richard Boucherie, Florian Schreck, Kareljan Schoutens, Ji\v{r}\'i
Min\'a\v{r} and Florian Speelman
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
- 参考スコア（独自算出の注目度）: 94.37521840642141
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the correlation clustering problem using the quantum approximate
optimization algorithm (QAOA) and qudits, which constitute a natural platform
for such non-binary problems. Specifically, we consider a neutral atom quantum
computer and propose a full stack approach for correlation clustering,
including Hamiltonian formulation of the algorithm, analysis of its
performance, identification of a suitable level structure for ${}^{87}{\rm Sr}$
and specific gate design. We show the qudit implementation is superior to the
qubit encoding as quantified by the gate count. For single layer QAOA, we also
prove (conjecture) a lower bound of $0.6367$ ($0.6699$) for the approximation
ratio on 3-regular graphs. Our numerical studies evaluate the algorithm's
performance by considering complete and Erd\H{o}s-R\'enyi graphs of up to 7
vertices and clusters. We find that in all cases the QAOA surpasses the Swamy
bound $0.7666$ for the approximation ratio for QAOA depths $p \geq 2$. Finally,
by analysing the effect of errors when solving complete graphs we find that
their inclusion severely limits the algorithm's performance.
- Abstract（参考訳）: 本研究では,量子近似最適化アルゴリズム (QAOA) とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを考察し、アルゴリズムのハミルトン定式化、その性能解析、${}^{87}{\rm Sr}$に適したレベル構造と特定のゲート設計を含む相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
単層 QAOA に対して、3つの正則グラフ上の近似比に対して、0.6367$$ (0.6699$) の下界を証明(導出)する。
本研究では,最大7頂点およびクラスタの完全および Erd\H{o}s-R\enyi グラフを考慮し,アルゴリズムの性能を評価する。
すべての場合において、QAOAは、QAOA深さの近似比$p \geq 2$に対して、スワミー境界の$0.7666$を超える。
最後に,完全グラフの解法における誤差の影響を解析した結果,アルゴリズムの性能が著しく制限されていることがわかった。
関連論文リスト
- Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、MAX-CUT問題などの最適化問題を概ね解くことを目的として提案された量子古典ハイブリッドアルゴリズムである。
まず、二部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。
第2に、再帰的QAOA(RQAOA)は、QAOAをサブルーチンとしてグラフサイズを削減し、レベル1のQAOAを上回る性能を示す。
最後に,制限パラメータを持つRQAOAが,これらの制約に完全に対処可能であることを示す。
論文 参考訳（メタデータ） (2024-08-23T16:35:47Z) - A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Performance and limitations of the QAOA at constant levels on large
sparse hypergraphs and spin glass models [15.857373057387669]
無限大極限におけるランダム最適化問題のアンサンブル上での任意の一定レベル(層数)における濃度特性を証明した。
我々の分析は、サドル点近似の和対パス積分によって理解することができる。
一定レベルにおけるQAOAの性能は、$qge 4$のときの純$q$-spinモデルの最適性から外れ、偶数であることを示す。
論文 参考訳（メタデータ） (2022-04-21T17:40:39Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - Impact of Graph Structures for QAOA on MaxCut [0.2609784101826761]
量子近似最適化アルゴリズム(QAOA)は、量子コンピューティングを用いて最適化問題を解くための有望な方法である。
我々は、すべての連結非同型グラフに対するMaxCut問題において、少なくとも3つの深さでのQAOAの性能を評価する。
構造と性能の関係を知ることで、量子的優位性を示す可能性のある問題のクラスを特定できる。
論文 参考訳（メタデータ） (2021-02-11T13:32:00Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - Generating Target Graph Couplings for QAOA from Native Quantum Hardware
Couplings [3.2622301272834524]
本稿では,Ising型量子スピン系における限定大域制御を用いた任意の対象結合グラフの構築手法を提案する。
本手法は、量子近似最適化アルゴリズム(QAOA)をトラップされたイオン量子ハードウェア上に実装することによるものである。
Max-Cut QAOAのノイズシミュレーションにより、我々の実装は標準ゲートベースのコンパイルよりもノイズの影響を受けにくいことが示された。
論文 参考訳（メタデータ） (2020-11-16T18:43:09Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。