論文の概要: Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries

• arxiv url: http://arxiv.org/abs/2411.08824v1
• Date: Wed, 13 Nov 2024 18:04:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-14 16:10:54.636049
• Title: Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries
• Title（参考訳）: 半対称性の分解によるQAOA回路深さの低減
• Authors: Jonas Nüßlein, Leo Sünkel, Jonas Stein, Tobias Rohe, Daniëlle Schuman, Claudia Linnhoff-Popien, Sebastian Feld,
• Abstract要約: 修正 QUBO 行列 $Q_Hamilton$ が元の $Q$ と同じエネルギースペクトルを記述することを示す。 提案アルゴリズムは結合数を最大49%$、回路深さを最大41%$に削減した。
• 参考スコア（独自算出の注目度）: 4.958204128486634
• License:
• Abstract: QAOA is a quantum algorithm for solving combinatorial optimization problems. It is capable of searching for the minimizing solution vector $x$ of a QUBO problem $x^TQx$. The number of two-qubit CNOT gates in the QAOA circuit scales linearly in the number of non-zero couplings of $Q$ and the depth of the circuit scales accordingly. Since CNOT operations have high error rates it is crucial to develop algorithms for reducing their number. We, therefore, present the concept of \textit{semi-symmetries} in QUBO matrices and an algorithm for identifying and factoring them out into ancilla qubits. \textit{Semi-symmetries} are prevalent in QUBO matrices of many well-known optimization problems like \textit{Maximum Clique}, \textit{Hamilton Cycles}, \textit{Graph Coloring}, \textit{Vertex Cover} and \textit{Graph Isomorphism}, among others. We theoretically show that our modified QUBO matrix $Q_{mod}$ describes the same energy spectrum as the original $Q$. Experiments conducted on the five optimization problems mentioned above demonstrate that our algorithm achieved reductions in the number of couplings by up to $49\%$ and in circuit depth by up to $41\%$.
• Abstract（参考訳）: QAOAは組合せ最適化問題を解決する量子アルゴリズムである。 QUBO問題の最小化解ベクトル$x$を$x^TQx$で探索することができる。 QAOA回路における2量子CNOTゲートの数は、Q$の非ゼロカップリング数と回路深さとで線形にスケールする。 CNOT演算は高いエラー率を持つため、その数を減らすアルゴリズムを開発することが重要である。 したがって、QUBO行列における「textit{semi-symmetries}」の概念と、それらをアンシラ量子ビットに識別・分解するアルゴリズムを提示する。 \textit{Semi-symmetries} は QUBO 行列でよく知られた最適化問題、例えば \textit{Maximum Clique} 、 \textit{Hamilton Cycles} 、 \textit{Graph Coloring} 、 \textit{Vertex Cover} 、 \textit{Graph Isomorphism} などによく見られる。 理論的には、我々の修正 QUBO 行列 $Q_{mod}$ は元の $Q$ と同じエネルギースペクトルを記述する。 上述の5つの最適化問題に対して行った実験により,本アルゴリズムは結合数を最大49 %$、回路深さを最大41 %$に削減することに成功した。

関連論文リスト

• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
  ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。 第一のアルゴリズムは真の解に線形に収束する。 第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
  論文  参考訳（メタデータ） (2024-10-08T21:19:22Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• 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)
• An entanglement perspective on the quantum approximate optimization algorithm [0.0]
  ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討する。 また、ランダム行列理論に関連する絡み合いスペクトルについても検討する。
  論文  参考訳（メタデータ） (2022-06-14T17:37:44Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Multiplicative updates for symmetric-cone factorizations [0.0]
  コーンの分解を計算するための対称錐乗算更新(SCMU)アルゴリズムを導入,解析する。 SCMUアルゴリズムの軌道に沿って2乗損失目標が非減少していることを示す。
  論文  参考訳（メタデータ） (2021-08-02T09:23:39Z)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
  論文  参考訳（メタデータ） (2021-06-27T17:25:24Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)

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

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