論文の概要: Depth Optimized Ansatz Circuit in QAOA for Max-Cut
- arxiv url: http://arxiv.org/abs/2110.04637v1
- Date: Sat, 9 Oct 2021 19:45:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-11 23:08:45.100660
- Title: Depth Optimized Ansatz Circuit in QAOA for Max-Cut
- Title（参考訳）: 最大カット用qaoaの深さ最適化アンサッツ回路
- Authors: Ritajit Majumdar, Debasmita Bhoumik, Dhiraj Madan, Dhinakaran
Vinayagamurthy, Shesha Raghunathan, Susmita Sur-Kolay
- Abstract要約: 我々は$O(Delta cdot n2)$ greedyアルゴリズムを提案する。
このアルゴリズムは,Max-Cut に対する QAOA の各イテレーションにおける成功確率が 10 倍近いことを数値的に示す。
- 参考スコア（独自算出の注目度）: 0.9670182163018803
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While a Quantum Approximate Optimization Algorithm (QAOA) is intended to
provide a quantum advantage in finding approximate solutions to combinatorial
optimization problems, noise in the system is a hurdle in exploiting its full
potential. Several error mitigation techniques have been studied to lessen the
effect of noise on this algorithm. Recently, Majumdar et al. proposed a Depth
First Search (DFS) based method to reduce $n-1$ CNOT gates in the ansatz design
of QAOA for finding Max-Cut in a graph G = (V, E), |V| = n. However, this
method tends to increase the depth of the circuit, making it more prone to
relaxation error. The depth of the circuit is proportional to the height of the
DFS tree, which can be $n-1$ in the worst case. In this paper, we propose an
$O(\Delta \cdot n^2)$ greedy heuristic algorithm, where $\Delta$ is the maximum
degree of the graph, that finds a spanning tree of lower height, thus reducing
the overall depth of the circuit while still retaining the $n-1$ reduction in
the number of CNOT gates needed in the ansatz. We numerically show that this
algorithm achieves nearly 10 times increase in the probability of success for
each iteration of QAOA for Max-Cut. We further show that although the average
depth of the circuit produced by this heuristic algorithm still grows linearly
with n, our algorithm reduces the slope of the linear increase from 1 to 0.11.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は組合せ最適化問題の近似解を見つけるための量子優位性を提供するが、システム内のノイズはその潜在能力を最大限活用するためのハードルである。
このアルゴリズムに対するノイズの影響を減らすために、いくつかの誤り緩和手法が研究されている。
最近、Mageumdarらは、グラフ G = (V, E), |V| = n で Max-Cut を見つけるための QAOA のアンザッツ設計において、$n-1$ CNOT ゲートを減じるためのDepth First Search (DFS) ベースの手法を提案した。
しかし、この方法は回路の深さを増加させる傾向があり、リラクゼーションエラーを起こしやすい。
回路の深さはDFS木の高さに比例し、最悪の場合、n-1$となる。
本稿では,$O(\Delta \cdot n^2)$ greedy Heuristic Algorithmを提案し,$\Delta$はグラフの最大次数であり,低高さのスパンニングツリーを見出すことにより,アンサッツに必要なCNOTゲート数に対する$n-1$の削減を維持しつつ,回路全体の深さを小さくする。
このアルゴリズムは,Max-Cut に対する QAOA の各イテレーションにおける成功確率が 10 倍近いことを数値的に示す。
さらに、このヒューリスティックアルゴリズムによって生成された回路の平均深さは、nと線形に成長するが、このアルゴリズムは線形増加の勾配を1から0.11に減少させる。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文 参考訳（メタデータ） (2023-11-07T13:26:20Z) - Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary
Matrices with Asymptotically Optimal Gate Count [9.194399933498323]
特定のタスクのために量子回路を設計する際には、深さ/ゲート数を最適化することが非常に重要である。
本稿では,任意の対角ユニタリ行列に対する量子回路を自動生成する深度最適化合成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-12-02T06:58:26Z) - Even shorter quantum circuit for phase estimation on early
fault-tolerant quantum computers with applications to ground-state energy
estimation [5.746732081406236]
異なる特徴を持つ位相推定法を開発した。
アルゴリズムの総コストは、ハイゼンベルク制限スケーリング$widetildemathcalO(epsilon-1)$を満たす。
我々のアルゴリズムは、初期のフォールトトレラント量子コンピュータで位相推定タスクを行う際の回路深さを著しく削減することができる。
論文 参考訳（メタデータ） (2022-11-22T03:15:40Z) - An entanglement perspective on the quantum approximate optimization
algorithm [0.0]
ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討する。
また、ランダム行列理論に関連する絡み合いスペクトルについても検討する。
論文 参考訳（メタデータ） (2022-06-14T17:37:44Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Optimizing Ansatz Design in QAOA for Max-cut [0.9126120966154119]
CNOTは現代の量子コンピュータの主要なエラー源の1つである。
本稿では,回路内のCNOTゲート数を削減するための2つのハードウェア独立手法を提案する。
論文 参考訳（メタデータ） (2021-06-05T06:43:48Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。