論文の概要: Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond
- arxiv url: http://arxiv.org/abs/2108.06049v3
- Date: Mon, 21 Feb 2022 21:49:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-18 15:05:25.669537
- Title: Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond
- Title（参考訳）: ランダムMax-k-XORにおける局所量子アルゴリズムの限界
- Authors: Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, Jonathan Shi
- Abstract要約: 満足度問題(CSP)のランダムインスタンスにおけるQAOAを含む一般局所アルゴリズムの限界を示す。
具体的には、制約への代入が$o(n)$他の頂点を持つ局所近傍のみに依存するような一般的な局所アルゴリズム(例えば、深さが$ilonlog(n)$未満のQAOAは、任意に近似CSPを適用できないことを示す。
- 参考スコア（独自算出の注目度）: 1.8374319565577157
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a notion of \emph{generic local algorithm} which strictly
generalizes existing frameworks of local algorithms such as \emph{factors of
i.i.d.} by capturing local \emph{quantum} algorithms such as the Quantum
Approximate Optimization Algorithm (QAOA).
Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019] we then show
limitations of generic local algorithms including QAOA on random instances of
constraint satisfaction problems (CSPs). Specifically, we show that any generic
local algorithm whose assignment to a vertex depends only on a local
neighborhood with $o(n)$ other vertices (such as the QAOA at depth less than
$\epsilon\log(n)$) cannot arbitrarily-well approximate boolean CSPs if the
problem satisfies a geometric property from statistical physics called the
coupled overlap-gap property (OGP) [Chen et al., Annals of Probability, 47(3),
2019]. We show that the random MAX-k-XOR problem has this property when
$k\geq4$ is even by extending the corresponding result for diluted $k$-spin
glasses.
Our concentration lemmas confirm a conjecture of Brandao et al.
[arXiv:1812.04170, 2018] asserting that the landscape independence of QAOA
extends to logarithmic depth -- in other words, for every fixed choice of QAOA
angle parameters, the algorithm at logarithmic depth performs almost equally
well on almost all instances. One of these concentration lemmas is a
strengthening of McDiarmid's inequality, applicable when the random variables
have a highly biased distribution, and may be of independent interest.
- Abstract（参考訳）: 本稿では,量子近似最適化アルゴリズム (qaoa) のような局所的 \emph{quantum} アルゴリズムを捉えることにより,局所アルゴリズムの既存フレームワークを厳密に一般化する, \emph{generic local algorithm} の概念を導入する。
farhi et alの質問に動機づけられた。
[arXiv:1910.08187, 2019] では,制約満足度問題(CSP)のランダムなインスタンスに対するQAOAを含む一般局所アルゴリズムの制限を示す。
具体的には、頂点に代入するすべてのジェネリック局所アルゴリズムは、o(n)$ の他の頂点を持つ局所近傍(例えば、$\epsilon\log(n)$ 未満のqaoa など)にのみ依存し、問題が結合重なりガップ特性 (ogp) [chen et al., annals of probability, 47(3), 2019] と呼ばれる統計物理学の幾何学的性質を満たす場合、任意に近似ブールcspsを拡張できないことを示す。
ランダムな max-k-xor 問題は、$k\geq4$ が、希薄な $k$-spin グラスの対応する結果を拡張することでさえも、この性質を持つ。
われわれの集中補題はbrandao et alの予想を裏付けている。
[arxiv:1812.04170, 2018] qaoaのランドスケープ独立性は対数深度にまで及んでいる、つまり、qaoa角パラメータの固定された選択ごとに、対数深さのアルゴリズムは、ほぼすべてのインスタンスでほぼ等しく機能する。
これらの濃度補題の1つは、確率変数が非常に偏った分布を持ち、独立した興味を持つ場合に適用される、マクディアーミーの不等式強化である。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
ランダム正則グラフ上での最大カットと最大独立集合問題を考える。
高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。
両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
論文 参考訳（メタデータ） (2024-06-20T18:00:02Z) - Local algorithms and the failure of log-depth quantum advantage on
sparse random CSPs [0.39901365062418315]
本研究では, ランダム制約満足度問題 (CSP) に対するメッセージパッシングアルゴリズムの構築と解析を行う。
偶数述語を持つ CSP に対して、アルゴリズムはパリの変分原理の拡張に双対する最適制御問題を解く。
これにより、Huang と Sellke の分岐オーバーラップギャップ特性によって妨げられるアルゴリズム間の満足度制約の最適分数が得られる。
論文 参考訳（メタデータ） (2023-10-02T18:55:26Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Performance and limitations of the QAOA at constant levels on large
sparse hypergraphs and spin glass models [15.857373057387669]
無限大極限におけるランダム最適化問題のアンサンブル上での任意の一定レベル(層数)における濃度特性を証明した。
我々の分析は、サドル点近似の和対パス積分によって理解することができる。
一定レベルにおけるQAOAの性能は、$qge 4$のときの純$q$-spinモデルの最適性から外れ、偶数であることを示す。
論文 参考訳（メタデータ） (2022-04-21T17:40:39Z) - Bounds on approximating Max $k$XOR with quantum and classical local
algorithms [0.0]
我々は、Max $k$XORをおよそ解くための局所アルゴリズムのパワーを考える。
Max $k$XORでは、各制約は正確に$k$変数とパリティビットのXORである。
量子アルゴリズムがしきい値アルゴリズムを$k > 4$で上回ることを示す。
論文 参考訳（メタデータ） (2021-09-22T16:50:45Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。