論文の概要: Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
- arxiv url: http://arxiv.org/abs/2401.11056v3
- Date: Mon, 12 Aug 2024 18:01:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-14 23:04:59.200646
- Title: Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
- Title(参考訳): グラバーミキサーを用いた量子交互演算子アンザッツの解析結果
- Authors: Guilherme Adamatti Bridi, Franklin de Lima Marquezino,
- Abstract要約: 本稿では,問題ハミルトニアンスペクトルに付随する確率分布に依存する予測値の解析式として,GM-QAOAを統計的に解析する手法を提案する。
我々はこの分析を、Grover-based QAOAと呼ぶGrovermixerを用いて、より一般的なQAOAの文脈に拡張する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: An important property of QAOA with Grover mixer is that its expectation value is invariant over any permutation of states. As a consequence, the algorithm is independent of the structure of the problem. If, on the one hand, this characteristic raises serious doubts about the capacity of the algorithm to overcome the bound of the unstructured search problem, on the other hand, it can pave the way to its analytical study. In this sense, a prior work introduced a statistical approach to analyze GM-QAOA that results in an analytical expression for the expectation value depending on the probability distribution associated with the problem Hamiltonian spectrum. Although the method provides surprising simplifications in calculations, the expression depends exponentially on the number of layers, which makes direct analytical treatment unfeasible. In this work, we extend the analysis to the more simple context of Grover Mixer Threshold QAOA (GM-Th-QAOA), a variant that replaces the phase separation operator of GM-QAOA to encode a threshold function. As a result, we obtain an expression for the expectation value independent of the number of layers and, with it, we provide bounds for different performance metrics. Furthermore, we extend the analysis to a more general context of QAOA with Grover mixer, which we called Grover-based QAOA. In that framework, which allows the phase separation operator to encode any compilation of the cost function, we generalize all the bounds by using an argument by contradiction with the optimality of Grover's algorithm on the unstructured search problem. As a result, we get the main contribution of this work, an asymptotic lower bound on the quantile achieved by the expectation value that formalizes the notion that the Grover mixer, at most, reflects a quadratic Grover-style speed-up over classical brute force.
- Abstract(参考訳): グロバー混合器によるQAOAの重要な性質は、その期待値は状態の任意の置換に対して不変であることである。
その結果、アルゴリズムは問題の構造とは無関係である。
この特徴が、非構造化探索問題の限界を克服するアルゴリズムの能力に深刻な疑問を呈する一方で、解析的研究への道を開くことができる。
この意味で、先行研究は、問題ハミルトニアンスペクトルに関連する確率分布に依存する期待値の解析的表現をもたらすGM-QAOAを分析する統計的アプローチを導入した。
この手法は計算における驚くほどの単純化を提供するが、式は指数関数的に層数に依存するため、直接解析処理は不可能である。
本研究では,Grover Mixer Threshold QAOA(Grover Mixer Threshold QAOA, GM-Th-QAOA, GM-QAOAの位相分離演算子を置換してしきい値関数を符号化する変種)のより単純な文脈に解析を拡張した。
その結果,レイヤ数に依存しない期待値の式が得られ,その結果,異なるパフォーマンス指標のバウンダリが提供される。
さらに、Grover-based QAOAと呼ぶGrovermixerを用いて、より一般的なQAOAの文脈まで分析を拡張した。
このフレームワークでは、位相分離演算子がコスト関数の任意のコンパイルを符号化できるので、非構造化探索問題上でのGroverのアルゴリズムの最適性と矛盾する引数を用いて、すべての境界を一般化する。
その結果、この研究の主な貢献は、古典的なブライト力に対してグロバーミキサーが二次的なグロバースタイルのスピードアップを反映するという考えを形式化する期待値によって達成された量子化の漸近的な下界である。
関連論文リスト
- Performance Upper Bound of Grover-Mixer Quantum Alternating Operator Ansatz [3.5023108034606256]
QAOA(Quantum Alternating Operator Ansatz)は最適化問題を解くための量子アルゴリズムの一分野である。
特定の変種であるGrover-Mixer Quantum Alternating Operator Ansatz (GM-QAOA)は、等価な目的値を共有する状態間で均一な振幅を保証する。
GM-QAOAはサンプリング確率を2次的に向上させ,一貫した性能を維持するために,問題サイズと指数関数的にスケールする回路深度を必要とすることを示す。
論文 参考訳(メタデータ) (2024-05-06T05:47:27Z) - Quantum Alternating Operator Ansatz (QAOA) beyond low depth with
gradually changing unitaries [0.0]
本稿では,量子交互演算子アンザッツ回路の動作を制御する機構について検討する。
離散的断熱定理を用いて、連続時間断熱定理から得られる洞察を補完し一般化する。
分析では,最近導入されたQAOAパフォーマンス図で顕著に示されているいくつかの一般的な特性について説明する。
論文 参考訳(メタデータ) (2023-05-08T04:21:42Z) - Quasi-parametric rates for Sparse Multivariate Functional Principal
Components Analysis [0.0]
最適化問題の解として固有値が表現可能であることを示す。
固有要素の平均2乗再構成誤差に基づいてミニマックス下限を定め、この手順がミニマックス感覚に最適な分散を有することを証明した。
論文 参考訳(メタデータ) (2022-12-19T13:17:57Z) - Equivariant Transduction through Invariant Alignment [71.45263447328374]
グループ内ハードアライメント機構を組み込んだ,新しいグループ同変アーキテクチャを提案する。
我々のネットワーク構造は、既存のグループ同変アプローチよりも強い同変特性を発達させることができる。
また、SCANタスクにおいて、従来のグループ同変ネットワークよりも経験的に優れていたことが判明した。
論文 参考訳(メタデータ) (2022-09-22T11:19:45Z) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳(メタデータ) (2022-06-02T15:21:55Z) - General Hamiltonian Representation of ML Detection Relying on the
Quantum Approximate Optimization Algorithm [74.6114458993128]
最適化問題を解くために考案された量子近似最適化アルゴリズム(QAOA)は、既存のノイズのある中間スケール量子(NISQ)デバイス上で実行することができる。
我々は、QAOAを適切に適応させることにより、一般星座の最大可能性(ML)検出問題を解く。
特に、M-ary Gray-mapped Quarature amplitude modulation (MQAM) 星座では、同相成分をコードする特定の量子ビットと二次成分をコードする量子ビットが、興味のある量子系において独立であることを示す。
論文 参考訳(メタデータ) (2022-04-11T14:11:24Z) - Numerical Evidence for Exponential Speed-up of QAOA over Unstructured
Search for Approximate Constrained Optimization [0.0]
本稿では,Grover-style unstructured searchによるQAOAの指数的高速化の証拠を示す。
以上の結果から,QAOA性能の最大化にはミキサーと位相分離器の選択が必要であることが示唆された。
論文 参考訳(メタデータ) (2022-02-01T18:39:52Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Threshold-Based Quantum Optimization [0.0]
Th-QAOA(Threshold QAOA)は、量子交互演算子Ansatz(QAOA)の変種である。
GM-Th-QAOAをGroverの量子探索アルゴリズムの一般化と見なすことができる。
論文 参考訳(メタデータ) (2021-06-25T19:36:49Z) - VAE Approximation Error: ELBO and Conditional Independence [78.72292013299868]
本稿では,ELBO目標とエンコーダ確率系列の選択の組み合わせによるVAE近似誤差を解析する。
より深いエンコーダネットワークを考慮すれば,ELBOサブセットを拡大することができず,各エラーを低減できないことを示す。
論文 参考訳(メタデータ) (2021-02-18T12:54:42Z) - Total Deep Variation: A Stable Regularizer for Inverse Problems [71.90933869570914]
本稿では,データ駆動型汎用全深度変動正規化器について紹介する。
コアでは、畳み込みニューラルネットワークが複数のスケールや連続したブロックで局所的な特徴を抽出する。
我々は多数の画像処理タスクに対して最先端の結果を得る。
論文 参考訳(メタデータ) (2020-06-15T21:54:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。