論文の概要: 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ゲート数の減少,回路エラーの確率が優れていることを示す。
関連論文リスト
- A two-circuit approach to reducing quantum resources for the quantum
lattice Boltzmann method [44.144964115275]
CFD問題を解決するための現在の量子アルゴリズムは、単一の量子回路と、場合によっては格子ベースの方法を用いる。
量子格子ボルツマン法(QLBM)を用いた新しい多重回路アルゴリズムを提案する。
この問題は2次元ナビエ・ストークス方程式の流動関数-渦性定式化として鋳造され、2次元蓋駆動キャビティフローで検証および試験された。
論文 参考訳(メタデータ) (2024-01-20T15:32:01Z) - A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical
Initialization [107.07093621337084]
正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。
1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。
有名な座標降下法に基づく新しいN-Cut解法を提案する。
論文 参考訳(メタデータ) (2023-11-26T07:11:58Z) - Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.22559617939136506]
我々は、我々の分割と形式主義の征服を通じて、大きな$Lambda$の量子化よりも優れたスケーリングと量子化を得られることを示す。
また,マルチコントロールされたXゲート群を実装する新しい方法を含む,ゲート最適化のための新しいアルゴリズムおよび回路レベル技術も提供する。
論文 参考訳(メタデータ) (2023-06-19T23:20:30Z) - 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) - On Actual Preparation of Dicke State on a Quantum Computer [4.098348230722067]
回路構成を改善するために,部分的に定義されたユニタリ変換の簡潔な実現の重要性について検討する。
我々は、CNOTおよび単一キュービットゲート数の観点から、最も効率的な決定論的ディック状態準備回路を提供する。
我々は、回路内のCNOTゲートの分配方法と、誘導誤差への影響について分析する。
論文 参考訳(メタデータ) (2020-07-03T13:40:32Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。