論文の概要: Classical algorithms and quantum limitations for maximum cut on
high-girth graphs
- arxiv url: http://arxiv.org/abs/2106.05900v1
- Date: Thu, 10 Jun 2021 16:28:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-27 01:51:57.909008
- Title: Classical algorithms and quantum limitations for maximum cut on
high-girth graphs
- Title（参考訳）: 高次グラフ上の最大カットに対する古典的アルゴリズムと量子制限
- Authors: Boaz Barak and Kunal Marwaha
- Abstract要約: すべての(量子または古典的な)一局所アルゴリズムが$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$,
- 参考スコア（独自算出の注目度）: 6.262125516926276
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the performance of local quantum algorithms such as the Quantum
Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and
their relationship to that of classical algorithms.
(1) We prove that every (quantum or classical) one-local algorithm achieves
on $D$-regular graphs of girth $> 5$ a maximum cut of at most $1/2 +
C/\sqrt{D}$ for $C=1/\sqrt{2} \approx 0.7071$. This is the first such result
showing that one-local algorithms achieve a value bounded away from the true
optimum for random graphs, which is $1/2 + P_*/\sqrt{D} + o(1/\sqrt{D})$ for
$P_* \approx 0.7632$. (2) We show that there is a classical $k$-local algorithm
that achieves a value of $1/2 + C/\sqrt{D} - O(1/\sqrt{k})$ for $D$-regular
graphs of girth $> 2k+1$, where $C = 2/\pi \approx 0.6366$. This is an
algorithmic version of the existential bound of Lyons and is related to the
algorithm of Aizenman, Lebowitz, and Ruelle (ALR) for the
Sherrington-Kirkpatrick model. This bound is better than that achieved by the
one-local and two-local versions of QAOA on high-girth graphs. (3) Through
computational experiments, we give evidence that the ALR algorithm achieves
better performance than constant-locality QAOA for random $D$-regular graphs,
as well as other natural instances, including graphs that do have short cycles.
Our experimental work suggests that it could be possible to extend beyond our
theoretical constraints. This points at the tantalizing possibility that
$O(1)$-local quantum maximum-cut algorithms might be *pointwise dominated* by
polynomial-time classical algorithms, in the sense that there is a classical
algorithm outputting cuts of equal or better quality *on every possible
instance*. This is in contrast to the evidence that polynomial-time algorithms
cannot simulate the probability distributions induced by local quantum
algorithms.
- Abstract（参考訳）: 本研究では,最大カット問題に対する量子近似最適化アルゴリズム (qaoa) などの局所量子アルゴリズムの性能と,それらの古典的アルゴリズムとの関係について検討する。
1)すべての(量子的あるいは古典的)一局所アルゴリズムが、最大カットが最大1/2 + c/\sqrt{d}$ for $c=1/\sqrt{2} \approx 0.7071$のd$-レギュラーグラフで達成できることを証明する。
これは、一局所アルゴリズムが乱グラフの真の最適値から有界な値を得る最初の結果であり、これは1/2 + P_*/\sqrt{D} + o(1/\sqrt{D})$ for $P_* \approx 0.7632$である。
2) 1/2 + c/\sqrt{d} - o(1/\sqrt{k})$ for $d$-regular graphs of girth $> 2k+1$, ここで$c = 2/\pi \approx 0.6366$である。
これはリヨンの存在境界のアルゴリズム版であり、シェリントン・カークパトリックモデルに対するアゼンマン、レボリッツ、ルエル(英語版)(ALR)のアルゴリズムと関連している。
この境界は、高次グラフ上のQAOAの一局所版と二局所版によって達成されるものよりも優れている。
3)計算実験により,alrアルゴリズムがランダムな$d$正規グラフに対する定局所性qaoaや,短いサイクルを持つグラフを含む他の自然な例よりも優れた性能が得られることを示す。
我々の実験的研究は、理論上の制約を超えて拡張できることを示唆している。
これは、o(1)$-local quantum maximum-cutアルゴリズムが多項式時間古典的アルゴリズムによって*点的に支配される可能性を示すものであり、すべてのインスタンス*に等質または良質のカットを出力する古典的アルゴリズムが存在するという意味である。
これは多項式時間アルゴリズムが局所量子アルゴリズムによって誘導される確率分布をシミュレートできないという証拠とは対照的である。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - 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) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - The Quantum Approximate Optimization Algorithm at High Depth for MaxCut
on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
量子近似最適化アルゴリズム (QAOA) は最適化問題の近似解を求める。
任意の深さで$D$に対して性能を評価するための反復式を任意の深さ$p$で与える。
我々は、QAOAが無限大の$p$でパリの価値を達成できるという楽観的な予想を立てる。
論文 参考訳（メタデータ） (2021-10-27T06:35:59Z) - Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth
regular graphs [0.0]
すべての次数$D ge 2$ of girth $> 5$に対して、QAOA$はQAOA$ on $G$よりも大きなカット率を持つことを示す。
任意の定数$p$に対して、すべてのグラフ上でQAOA$_p$と同様に動作する局所古典的MAX-CUTアルゴリズムが存在すると推測する。
論文 参考訳（メタデータ） (2021-01-14T09:17:20Z) - Low depth algorithms for quantum amplitude estimation [6.148105657815341]
振幅推定のための2つの新しい低深さアルゴリズムの設計と解析
これらのアルゴリズムはモンテカルロ法の量子スピードアップを実現に近づける。
論文 参考訳（メタデータ） (2020-12-06T18:39:20Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。