論文の概要: Optimizing Ansatz Design in QAOA for Max-cut
- arxiv url: http://arxiv.org/abs/2106.02812v4
- Date: Mon, 28 Jun 2021 11:59:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-27 19:07:14.020548
- Title: Optimizing Ansatz Design in QAOA for Max-cut
- Title（参考訳）: 最大カットのためのQAOAにおけるアンザッツ設計の最適化
- Authors: Ritajit Majumdar, Dhiraj Madan, Debasmita Bhoumik, Dhinakaran
Vinayagamurthy, Shesha Raghunathan, and Susmita Sur-Kolay
- Abstract要約: CNOTは現代の量子コンピュータの主要なエラー源の1つである。
本稿では,回路内のCNOTゲート数を削減するための2つのハードウェア独立手法を提案する。
- 参考スコア（独自算出の注目度）: 0.9126120966154119
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum Approximate Optimization Algorithm (QAOA) is studied primarily to
find approximate solutions to combinatorial optimization problems. For a graph
with $n$ vertices and $m$ edges, a depth $p$ QAOA for the Max-cut problem
requires $2\cdot m \cdot p$ CNOT gates. CNOT is one of the primary sources of
error in modern quantum computers. In this paper, we propose two hardware
independent methods to reduce the number of CNOT gates in the circuit. First,
we present a method based on Edge Coloring of the input graph that minimizes
the the number of cycles (termed as depth of the circuit), and reduces upto
$\lfloor \frac{n}{2} \rfloor$ CNOT gates. Next, we depict another method based
on Depth First Search (DFS) on the input graph that reduces $n-1$ CNOT gates,
but increases depth of the circuit moderately. We analytically derive the
condition for which the reduction in CNOT gates overshadows this increase in
depth, and the error probability of the circuit is still lowered. We show that
all IBM Quantum Hardware satisfy this condition. We simulate these two methods
for graphs of various sparsity with the \textit{ibmq\_manhattan} noise model,
and show that the DFS based method outperforms the edge coloring based method,
which in turn, outperforms the traditional QAOA circuit in terms of reduction
in the number of CNOT gates, and hence the probability of error of the circuit.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(qaoa)は主に組合せ最適化問題の近似解を見つけるために研究されている。
n$頂点と$m$エッジを持つグラフの場合、マックスカット問題に対する深さ$p$ QAOA は 2 つの m \cdot p$ CNOT ゲートを必要とする。
CNOTは現代の量子コンピュータの主要なエラー源の1つである。
本稿では,回路内のCNOTゲート数を削減するための2つのハードウェア独立手法を提案する。
まず,入力グラフのエッジカラー化に基づいて回路の深さを最小化し,最大で$\lfloor \frac{n}{2} \rfloor$CNOTゲートまで低減する手法を提案する。
次に、入力グラフ上の深さ優先探索(dfs)に基づく別の方法を示し、n-1$ cnotゲートを減少させるが、回路の深さを適度に増加させる。
我々は、cnotゲートの低減がこの深さの増大を覆う条件を解析的に導出し、回路の誤差確率をまだ低下させる。
すべてのIBM量子ハードウェアがこの条件を満たすことを示す。
これら2つの多彩なグラフ法を, \textit{ibmq\_manhattan} ノイズモデルを用いてシミュレートし,dfsに基づく手法がエッジカラー化方式よりも優れており,従来のqaoa回路よりもcnotゲート数の減少,回路エラーの確率が優れていることを示す。
関連論文リスト
- Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries [4.958204128486634]
修正 QUBO 行列 $Q_Hamilton$ が元の $Q$ と同じエネルギースペクトルを記述することを示す。
提案アルゴリズムは結合数を最大49%$、回路深さを最大41%$に削減した。
論文 参考訳（メタデータ） (2024-11-13T18:04:01Z) - Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA [0.0]
本稿では,新しいQAOAアンサッツについて述べる。
我々は、新しいアンザッツの一般式を$p=1$で導き、サイクルグラフの近似比の改善を解析的に示す。
論文 参考訳（メタデータ） (2024-11-07T22:20:01Z) - Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations [5.451583832235867]
我々は Max-Cut 問題を解くための近似コンパイル手法を開発した。
結果はグラフスカラー化と分解の原則に基づいている。
新たなコンパイル手法では,ノイズの顕著な低減が示される。
論文 参考訳（メタデータ） (2024-06-20T14:00:09Z) - AltGraph: Redesigning Quantum Circuits Using Generative Graph Models for Efficient Optimization [2.089191490381739]
AltGraphはサーチベースのサーキットトランスフォーメーションアプローチである。
既存の生成グラフモデルを用いて等価量子回路を生成する。
ゲート数の平均は37.55%減少し、回路深度は37.75%減少する。
論文 参考訳（メタデータ） (2024-02-23T19:01:47Z) - Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。
この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。
グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文 参考訳（メタデータ） (2022-07-13T18:12:36Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Depth Optimized Ansatz Circuit in QAOA for Max-Cut [0.9670182163018803]
我々は$O(Delta cdot n2)$ greedyアルゴリズムを提案する。
このアルゴリズムは,Max-Cut に対する QAOA の各イテレーションにおける成功確率が 10 倍近いことを数値的に示す。
論文 参考訳（メタデータ） (2021-10-09T19:45:12Z) - Graph Signal Restoration Using Nested Deep Algorithm Unrolling [85.53158261016331]
グラフ信号処理は、センサー、社会交通脳ネットワーク、ポイントクラウド処理、グラフネットワークなど、多くのアプリケーションにおいてユビキタスなタスクである。
凸非依存型深部ADMM(ADMM)に基づく2つの復元手法を提案する。
提案手法のパラメータはエンドツーエンドでトレーニング可能である。
論文 参考訳（メタデータ） (2021-06-30T08:57:01Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。