論文の概要: Low-depth Clifford circuits approximately solve MaxCut

• arxiv url: http://arxiv.org/abs/2310.15022v2
• Date: Wed, 28 Feb 2024 23:08:24 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-01 18:21:04.410440
• Title: Low-depth Clifford circuits approximately solve MaxCut
• Title（参考訳）: 低深さクリフォード回路はMaxCutをほぼ解く
• Authors: Manuel H. Mu\~noz-Arias, Stefanos Kourtis, Alexandre Blais
• Abstract要約: 低深さクリフォード回路に基づくMaxCutの量子インスピレーション近似アルゴリズムを提案する。 提案アルゴリズムは,深さクリフォード回路を構築することにより,$N$-vertexグラフ上のMaxCutの近似解を求める。
• 参考スコア（独自算出の注目度）: 49.1574468325115
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a quantum-inspired approximation algorithm for MaxCut based on low-depth Clifford circuits. We start by showing that the solution unitaries found by the adaptive quantum approximation optimization algorithm (ADAPT-QAOA) for the MaxCut problem on weighted fully connected graphs are (almost) Clifford circuits. Motivated by this observation, we devise an approximation algorithm for MaxCut, \emph{ADAPT-Clifford}, that searches through the Clifford manifold by combining a minimal set of generating elements of the Clifford group. Our algorithm finds an approximate solution of MaxCut on an $N$-vertex graph by building a depth $O(N)$ Clifford circuit. The algorithm has runtime complexity $O(N^2)$ and $O(N^3)$ for sparse and dense graphs, respectively, and space complexity $O(N^2)$, with improved solution quality achieved at the expense of more demanding runtimes. We implement ADAPT-Clifford and characterize its performance on graphs with positive and signed weights. The case of signed weights is illustrated with the paradigmatic Sherrington-Kirkpatrick model, for which our algorithm finds solutions with ground-state mean energy density corresponding to $\sim94\%$ of the Parisi value in the thermodynamic limit. The case of positive weights is investigated by comparing the cut found by ADAPT-Clifford with the cut found with the Goemans-Williamson (GW) algorithm. For both sparse and dense instances we provide copious evidence that, up to hundreds of nodes, ADAPT-Clifford finds cuts of lower energy than GW. Since good approximate solutions to MaxCut can be efficiently found within the Clifford manifold, we hope our results will motivate to rethink the approach so far used to search for quantum speedup in combinatorial optimization problems.
• Abstract（参考訳）: 低深さクリフォード回路に基づくMaxCutの量子インスピレーション近似アルゴリズムを提案する。 まず、重み付き完全連結グラフ上のMaxCut問題に対する適応量子近似最適化アルゴリズム(ADAPT-QAOA)の解ユニタリが(ほぼ)クリフォード回路であることを示す。 この観測により、我々は、クリフォード群の生成要素の最小セットを組み合わせてクリフォード多様体を探索するMaxCut, \emph{ADAPT-Clifford} の近似アルゴリズムを考案した。 我々のアルゴリズムは、深さ$O(N)$ Clifford回路を構築することにより、$N$頂点グラフ上のMaxCutの近似解を求める。 このアルゴリズムは、スパースグラフと高密度グラフに対してそれぞれ$O(N^2)$と$O(N^3)$と、より要求の高いランタイムを犠牲にしてソリューション品質が改善された空間複雑性$O(N^2)$を有する。 我々はADAPT-Cliffordを実装し、正の重みと符号付き重みを持つグラフ上での性能を特徴付ける。 符号付き重みの場合には、熱力学的極限におけるパリス値の$\sim94\%$に対応する基底状態平均エネルギー密度の解を求めるパラダイム的シェリントン=カークパトリックモデルで示される。 ADAPT-Clifford によるカットと Goemans-Williamson (GW) アルゴリズムによるカットを比較して, 正重みの場合について検討した。 スパースと高密度の両方の場合、数百のノードで、ADAPT-Clifford は GW よりも低いエネルギーをカットする。 MaxCut に対する良い近似解はクリフォード多様体内で効率よく発見できるので、我々の結果は組合せ最適化問題における量子スピードアップの探索にこれまで用いられてきたアプローチを再考する動機となることを願っている。

関連論文リスト

• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• Computing Star Discrepancies with Numerical Black-Box Optimization Algorithms [56.08144272945755]
  我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。 使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。 我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
  論文  参考訳（メタデータ） (2023-06-29T14:57:56Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• 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)
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
  量子近似最適化アルゴリズム (QAOA) は最適化問題の近似解を求める。 任意の深さで$D$に対して性能を評価するための反復式を任意の深さ$p$で与える。 我々は、QAOAが無限大の$p$でパリの価値を達成できるという楽観的な予想を立てる。
  論文  参考訳（メタデータ） (2021-10-27T06:35:59Z)
• 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)
• 6-qubit Optimal Clifford Circuits [8.024778381207128]
  クリフォード群要素は魔法の状態蒸留やランダム化されたベンチマークプロトコルを形成するのに使うことができる。 短い回路を見つけることは難しい問題であり、クリフォード群は有限であるにもかかわらず、そのサイズは量子ビットの数とともに急速に増加する。 消費者と企業レベルのコンピュータを用いて、任意の最適6ビットクリフォード回路を0.0009358$と0.0006274$秒で抽出する方法を示す。
  論文  参考訳（メタデータ） (2020-12-11T01:33:17Z)
• Generating Target Graph Couplings for QAOA from Native Quantum Hardware Couplings [3.2622301272834524]
  本稿では,Ising型量子スピン系における限定大域制御を用いた任意の対象結合グラフの構築手法を提案する。 本手法は、量子近似最適化アルゴリズム(QAOA)をトラップされたイオン量子ハードウェア上に実装することによるものである。 Max-Cut QAOAのノイズシミュレーションにより、我々の実装は標準ゲートベースのコンパイルよりもノイズの影響を受けにくいことが示された。
  論文  参考訳（メタデータ） (2020-11-16T18:43:09Z)
• Hadamard-free circuits expose the structure of the Clifford group [9.480212602202517]
  クリフォード群は量子ランダム化ベンチマーク、量子トモグラフィ、誤り訂正プロトコルにおいて中心的な役割を果たす。 任意のクリフォード作用素が標準形式$F_HSF$で一意に書けることを示す。 ランダムな一様クリフォード作用素と対称群上のマロース分布の間の驚くべき接続が強調される。
  論文  参考訳（メタデータ） (2020-03-20T17:51:36Z)

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

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