論文の概要: Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs

• arxiv url: http://arxiv.org/abs/2310.01563v1
• Date: Mon, 2 Oct 2023 18:55:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-04 19:18:02.568625
• Title: Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs
• Title（参考訳）: スパースランダムCSPにおける局所アルゴリズムと対数深さ量子優位性の失敗
• Authors: Antares Chen, Neng Huang, Kunal Marwaha
• Abstract要約: 本研究では, ランダム制約満足度問題 (CSP) に対するメッセージパッシングアルゴリズムの構築と解析を行う。 偶数述語を持つ CSP に対して、アルゴリズムはパリの変分原理の拡張に双対する最適制御問題を解く。 これにより、Huang と Sellke の分岐オーバーラップギャップ特性によって妨げられるアルゴリズム間の満足度制約の最適分数が得られる。
• 参考スコア（独自算出の注目度）: 0.39901365062418315
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We construct and analyze a message-passing algorithm for random constraint satisfaction problems (CSPs) at large clause density, generalizing work of El Alaoui, Montanari, and Sellke for Maximum Cut [arXiv:2111.06813] through a connection between random CSPs and mean-field Ising spin glasses. For CSPs with even predicates, the algorithm asymptotically solves a stochastic optimal control problem dual to an extended Parisi variational principle. This gives an optimal fraction of satisfied constraints among algorithms obstructed by the branching overlap gap property of Huang and Sellke [arXiv:2110.07847], notably including the Quantum Approximate Optimization Algorithm and all quantum circuits on a bounded-degree architecture of up to $\epsilon \cdot \log n$ depth.
• Abstract（参考訳）: 我々は,ランダムCSPと平均場Isingスピングラスの接続により,El Alaoui,Montanari,Sellke for Maximum Cut (arXiv:2111.06813) を一般化し,大節密度でランダム制約満足問題(CSP)に対するメッセージパッシングアルゴリズムを構築し,解析する。 偶数述語を持つ CSP に対して、アルゴリズムは漸近的にパリ変分法に双対する確率的最適制御問題を解く。 これにより、huang と sellke [arxiv:2110.07847] の分岐重なりギャップ特性によって阻害されるアルゴリズム間の最適制約の分数、特に、最大$\epsilon \cdot \log n$ の有界度アーキテクチャ上の量子近似最適化アルゴリズムと全ての量子回路を含む。

関連論文リスト

• 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)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。 本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-06-11T04:40:05Z)
• The role of quantum and classical correlations in shrinking algorithms for optimization [0.0]
  最適化問題(COP)における縮小アルゴリズムの性能について検討する。 量子近似最適化アルゴリズム (QAOA) と古典線形計画法 (LP) と半定値計画法 (SDP) の相関によるアルゴリズムの性能の比較を行った。 その結果、LPは低密度のインスタンスに対して他の全てのアプローチよりも優れており、SDPは高密度の問題に対して優れていた。
  論文  参考訳（メタデータ） (2024-04-26T08:29:04Z)
• Extending relax-and-round combinatorial optimization solvers with quantum correlations [0.0]
  量子近似最適化アルゴリズム (QAOA) を$pgeq 1$ の層に埋め込む。 Sherrington-Kirk メガネを含む多くの問題に対して、$p=1$とすると、その古典的な問題と同じくらい正確であることを示す。 古典的アルゴリズムに匹敵するパフォーマンスで、量子リラクゼーションとラウンドを網羅するフレームワークの道を開いた。
  論文  参考訳（メタデータ） (2023-07-11T22:02:01Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• An Asymptotically Optimal Algorithm for the Convex Hull Membership Problem [21.312152185262]
  純粋な探査環境における凸船体構成問題について検討する。 我々はThompson-CHMというアルゴリズムを初めて提案し、そのモジュラー設計は停止規則とサンプリング規則から構成される。
  論文  参考訳（メタデータ） (2023-02-03T23:41:53Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• An entanglement perspective on the quantum approximate optimization algorithm [0.0]
  ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討する。 また、ランダム行列理論に関連する絡み合いスペクトルについても検討する。
  論文  参考訳（メタデータ） (2022-06-14T17:37:44Z)
• 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)
• SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
  我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。 我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。 我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
  論文  参考訳（メタデータ） (2020-06-12T05:00:44Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。