論文の概要: Twisted hybrid algorithms for combinatorial optimization
- arxiv url: http://arxiv.org/abs/2203.00717v1
- Date: Tue, 1 Mar 2022 19:47:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-23 10:06:22.394822
- Title: Twisted hybrid algorithms for combinatorial optimization
- Title（参考訳）: 組合せ最適化のためのツイストハイブリッドアルゴリズム
- Authors: Libor Caha, Alexander Kliesch, Robert Koenig
- Abstract要約: 提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
- 参考スコア（独自算出の注目度）: 68.8204255655161
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Proposed hybrid algorithms encode a combinatorial cost function into a
problem Hamiltonian and optimize its energy by varying over a set of states
with low circuit complexity. Classical processing is typically only used for
the choice of variational parameters following gradient descent. As a
consequence, these approaches are limited by the descriptive power of the
associated states.
We argue that for certain combinatorial optimization problems, such
algorithms can be hybridized further, thus harnessing the power of efficient
non-local classical processing. Specifically, we consider combining a quantum
variational ansatz with a greedy classical post-processing procedure for the
MaxCut-problem on $3$-regular graphs. We show that the average cut-size
produced by this method can be quantified in terms of the energy of a modified
problem Hamiltonian. This motivates the consideration of an improved algorithm
which variationally optimizes the energy of the modified Hamiltonian. We call
this a twisted hybrid algorithm since the additional classical processing step
is combined with a different choice of variational parameters. We exemplify the
viability of this method using the quantum approximate optimization algorithm
(QAOA), giving analytic lower bounds on the expected approximation ratios
achieved by twisted QAOA. These show that the necessary non-locality of the
quantum ansatz can be reduced compared to the original QAOA: We find that for
levels $p=2,\ldots, 6$, the level $p$ can be reduced by one while roughly
maintaining the expected approximation ratio. This reduces the circuit depth by
$4$ and the number of variational parameters by $2$.
- Abstract（参考訳）: 提案するハイブリッドアルゴリズムは、組合せコスト関数を問題ハミルトニアンにエンコードし、回路の複雑さの低い一連の状態を変化させることでエネルギーを最適化する。
古典処理は通常、勾配降下後の変分パラメータの選択にのみ使用される。
その結果、これらのアプローチは関連する状態の記述力によって制限される。
我々は、ある種の組合せ最適化問題に対して、そのようなアルゴリズムをさらにハイブリダイズし、効率的な非局所的古典処理のパワーを利用することができると論じる。
具体的には、量子変分アンサッツと3ドル規則グラフ上のMaxCut-problemのグリーディーな古典的な後処理手順を組み合わせることを検討する。
この方法によって生成される平均カットサイズは、修正されたハミルトニアン問題のエネルギーの観点から定量化できることを示す。
これにより、改良されたハミルトニアンのエネルギーを変動的に最適化する改良アルゴリズムの考察が動機となる。
我々はこれをツイストハイブリッドアルゴリズムと呼ぶ。なぜなら、古典的な処理ステップと変分パラメータの異なる選択が組み合わされるからである。
本稿では,量子近似最適化アルゴリズム(QAOA)を用いて,この手法の有効性を実証する。
これらの結果から、量子アンサッツの必要な非局所性は、元のqaoaと比較して小さくできる: 期待近似比を概ね保ちながら、$p=2,\ldots, 6$のレベルでは、レベル$p$を1つ減らすことができる。
これにより回路深さが4ドル、変分パラメータの数が2ドル削減される。
関連論文リスト
- Probabilistic tensor optimization of quantum circuits for the
max-$k$-cut problem [0.0]
本稿では,変分量子アルゴリズムにおけるパラメータ化回路の最適化手法を提案する。
本稿では,量子近似最適化アルゴリズム (QAOA) を最大$k$-cut問題に適用した例について述べる。
論文 参考訳（メタデータ） (2023-10-16T12:56:22Z) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。
これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
論文 参考訳（メタデータ） (2022-05-11T14:29:39Z) - Parameters Fixing Strategy for Quantum Approximate Optimization
Algorithm [0.0]
そこで本稿では,QAOAをパラメータとして初期化することで,回路深度が大きければ平均で高い近似比を与える手法を提案する。
我々は3つの正則グラフやエルド・オス=ルネニグラフのようなグラフのある種のクラスにおけるマックスカット問題に対する我々の戦略をテストする。
論文 参考訳（メタデータ） (2021-08-11T15:44:16Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - An adaptive quantum approximate optimization algorithm for solving
combinatorial problems on a quantum computer [0.0]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くハイブリッド変分量子古典アルゴリズムである。
我々は,QAOAの反復バージョンを開発し,特定のハードウェア制約に適応することができる。
アルゴリズムをMax-Cutグラフのクラス上でシミュレートし、標準QAOAよりもはるかに高速に収束することを示す。
論文 参考訳（メタデータ） (2020-05-20T18:00:01Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z) - Accelerating Quantum Approximate Optimization Algorithm using Machine
Learning [6.735657356113614]
本稿では,量子近似最適化アルゴリズム(QAOA)の実装を高速化する機械学習手法を提案する。
QAOAは、いわゆる量子超越性を証明する量子古典ハイブリッドアルゴリズムである。
提案手法は,264種類のグラフを用いて行った解析から,最適化の繰り返し回数を最大65.7%削減できることを示す。
論文 参考訳（メタデータ） (2020-02-04T02:21:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。