論文の概要: Bounds on approximating Max $k$XOR with quantum and classical local
algorithms
- arxiv url: http://arxiv.org/abs/2109.10833v3
- Date: Thu, 30 Jun 2022 21:19:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-14 01:08:47.497228
- Title: Bounds on approximating Max $k$XOR with quantum and classical local
algorithms
- Title（参考訳）: 量子および古典的局所アルゴリズムによるMax $k$XORの近似に関するバウンド
- Authors: Kunal Marwaha, Stuart Hadfield
- Abstract要約: 我々は、Max $k$XORをおよそ解くための局所アルゴリズムのパワーを考える。
Max $k$XORでは、各制約は正確に$k$変数とパリティビットのXORである。
量子アルゴリズムがしきい値アルゴリズムを$k > 4$で上回ることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the power of local algorithms for approximately solving Max
$k$XOR, a generalization of two constraint satisfaction problems previously
studied with classical and quantum algorithms (MaxCut and Max E3LIN2). In Max
$k$XOR each constraint is the XOR of exactly $k$ variables and a parity bit. On
instances with either random signs (parities) or no overlapping clauses and
$D+1$ clauses per variable, we calculate the expected satisfying fraction of
the depth-1 QAOA from Farhi et al [arXiv:1411.4028] and compare with a
generalization of the local threshold algorithm from Hirvonen et al
[arXiv:1402.2543]. Notably, the quantum algorithm outperforms the threshold
algorithm for $k > 4$.
On the other hand, we highlight potential difficulties for the QAOA to
achieve computational quantum advantage on this problem. We first compute a
tight upper bound on the maximum satisfying fraction of nearly all large random
regular Max $k$XOR instances by numerically calculating the ground state energy
density $P(k)$ of a mean-field $k$-spin glass [arXiv:1606.02365]. The upper
bound grows with $k$ much faster than the performance of both one-local
algorithms. We also identify a new obstruction result for low-depth quantum
circuits (including the QAOA) when $k=3$, generalizing a result of Bravyi et al
[arXiv:1910.08980] when $k=2$. We conjecture that a similar obstruction exists
for all $k$.
- Abstract（参考訳）: 古典的および量子的アルゴリズム(maxcutおよびmax e3lin2)で研究された2つの制約満足度問題の一般化である、max $k$xorを概ね解くための局所アルゴリズムの力を考える。
Max $k$XOR では、各制約は正確に$k$変数とパリティビットの XOR である。
乱数符号(パリティ)または重複しない節と1変数当たり$d+1$節のいずれの場合でも、farhi et al [arxiv:1411.4028] から期待される深さ-1qaoaの分数を計算し、hirvonen et al [arxiv:1402.2543] からの局所しきい値アルゴリズムの一般化と比較する。
特に、量子アルゴリズムはしきい値アルゴリズムを$k > 4$で上回っている。
一方,QAOAがこの問題に対して量子的優位性を実現するための潜在的困難さを強調した。
まず、平均場$k$-spinガラス [arXiv:1606.02365] の基底状態エネルギー密度$P(k)$を数値計算することにより、ほぼ全ての大きなランダム正則Max$k$XORインスタンスの最大満足率の強い上限を計算する。
アッパーバウンドは、両方のローカルアルゴリズムのパフォーマンスよりもずっと高速な$k$で成長する。
また、k=3$のとき(qaoaを含む)、k=2$のときはbravyi et al [arxiv:1910.08980]の結果を一般化して、低深さの量子回路(qaoaを含む)に対する新たな妨害結果を特定する。
同様の障害がすべての$k$に対して存在すると推測する。
関連論文リスト
- Quantum Approximate $k$-Minimum Finding [2.810947654192424]
我々は、全ての$k geq 1$に対して近似値を扱う最適量子$k$-minimum探索アルゴリズムを提案する。
我々は、複数の観測可能量のうち、$k$最小の期待値を同定し、ハミルトンの最低基底状態エネルギーを$k$最小に決定するための効率的な量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-12-21T11:21:15Z) - 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) - 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) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
NPにおける制約満足度問題の特徴は近似硬度であり、最悪の場合、十分な品質の近似解を見つけることは指数関数的に困難である。
ハミルトニアン時間進化に基づくアルゴリズムでは、原型的にハードなMAX-3-XORSAT問題クラスを通してこの問題を探索する。
近似系におけるランダムなハイパーグラフに対して、エネルギーを$E = N_mathrmunsat-N_mathrmsat$と定義すれば、スペクトルフィルタリングされた量子最適化は$E leq q_mで状態を返す。
論文 参考訳（メタデータ） (2023-12-11T04:15:55Z) - 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) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond [1.8374319565577157]
満足度問題(CSP)のランダムインスタンスにおけるQAOAを含む一般局所アルゴリズムの限界を示す。
具体的には、制約への代入が$o(n)$他の頂点を持つ局所近傍のみに依存するような一般的な局所アルゴリズム(例えば、深さが$ilonlog(n)$未満のQAOAは、任意に近似CSPを適用できないことを示す。
論文 参考訳（メタデータ） (2021-08-13T03:55:22Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。