論文の概要: Analytical results for the Quantum Alternating Operator Ansatz with
Grover Mixer
- arxiv url: http://arxiv.org/abs/2401.11056v1
- Date: Fri, 19 Jan 2024 23:17:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-23 18:20:09.388626
- Title: Analytical results for the Quantum Alternating Operator Ansatz with
Grover Mixer
- Title(参考訳): グローバーミキサーを用いた量子交互作用素 ansatz の解析結果
- Authors: Guilherme Adamatti Bridi, Franklin de Lima Marquezino
- Abstract要約: 本稿では,問題ハミルトニアンスペクトルに付随する確率分布に依存する予測値の解析式として,GM-QAOAを統計的に解析する手法を提案する。
本研究では,Grover Threshold QAOA (GM-Th-QAOA) のより単純な文脈に解析を拡張し,GM-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 expected 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 a contradiction argument with
the optimality of Grover's algorithm on the unstructured search problem. The
main result is an asymptotic tight bound on the quantile achieved by the
expectation value that formalizes the notion that the Grover mixer reflected a
quadratic Grover-style speed-up over brute force. We apply that bound on the
Max-Cut problem to the particular class of complete bipartite graphs.
- Abstract(参考訳): グロバー混合器によるQAOAの重要な性質は、その期待値は状態の任意の置換に対して不変であることである。
その結果、アルゴリズムは問題の構造とは無関係である。
一方、この特徴が非構造化探索問題の限界を克服するアルゴリズムの能力に深刻な疑問を提起する一方で、分析研究への道を開くことができる。
この意味で、先行研究は、問題ハミルトニアンスペクトルに関連する確率分布に依存する期待値の解析的表現をもたらすGM-QAOAを分析する統計的アプローチを導入した。
この手法は計算において驚くべき単純化をもたらすが、その表現は層数に指数関数的に依存し、直接分析処理は不可能である。
本研究では,Grover Mixer Threshold QAOA(Grover Mixer Threshold QAOA, GM-Th-QAOA, GM-QAOAの位相分離演算子を置き換えてしきい関数を符号化する変種)のより単純な文脈に解析を拡張する。
その結果、レイヤ数に依存しない期待値の式が得られ、それに伴い、異なるパフォーマンス指標のバウンダリを提供する。
さらに、Grover-based QAOAと呼ぶGrovermixerを用いて、より一般的なQAOAの文脈まで分析を拡張した。
位相分離演算子がコスト関数の任意のコンパイルをエンコードできるようにするこのフレームワークでは、非構造化探索問題に対するグローバーのアルゴリズムの最適性と矛盾する引数を用いて、すべての境界を一般化する。
主な結果は、グロバーミキサーがブリュート力に対して二次グローバースタイルのスピードアップを反映するという考えを定式化した期待値によって達成された分位数の漸近的なタイトバウンドである。
我々は、マックス・カット問題にその境界を完備二部グラフの特定のクラスに適用する。
関連論文リスト
- Open-loop quantum control of small-size networks for high-order
cumulants and cross-correlations sensing [0.0]
本稿では,Ising-xx相互作用に基づく2量子ゲートの絡み合った処理における動的デカップリングについて検討する。
選択したパルス列の特性を利用して、2次統計を抽出できることを示す。
固体プラットフォームに基づく最先端の小型ネットワークに適用可能性について論じる。
論文 参考訳(メタデータ) (2024-01-11T09:17:34Z) - Quantum Alternating Operator Ansatz (QAOA) beyond low depth with
gradually changing unitaries [0.0]
本稿では,量子交互演算子アンザッツ回路の動作を制御する機構について検討する。
離散的断熱定理を用いて、連続時間断熱定理から得られる洞察を補完し一般化する。
分析では,最近導入されたQAOAパフォーマンス図で顕著に示されているいくつかの一般的な特性について説明する。
論文 参考訳(メタデータ) (2023-05-08T04:21:42Z) - Problem-Size Independent Angles for a Grover-Driven Quantum Approximate
Optimization Algorithm [0.0]
本稿では,Grover-driven,QAOA-prepared状態下でのハミルトニアンの期待値の計算をシステムサイズとは無関係に行うことができることを示す。
このような計算は、大きな問題の大きさの限界において、QAOAにおける角度のパフォーマンスと予測可能性に関する洞察を与えるのに役立つ。
論文 参考訳(メタデータ) (2022-08-22T17:18:25Z) - 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) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳(メタデータ) (2021-06-22T11:07:38Z) - Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。
精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
論文 参考訳(メタデータ) (2021-05-11T03:39:08Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳(メタデータ) (2021-05-03T16:36:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。