論文の概要: Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems

• arxiv url: http://arxiv.org/abs/2411.19388v1
• Date: Thu, 28 Nov 2024 21:39:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-02 15:19:45.027024
• Title: Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems
• Title（参考訳）: 遺伝的高次制約-満足問題の解法における量子近似最適化の限界
• Authors: Thorge Müller, Ajainderpal Singh, Frank K. Wilhelm, Tim Bode,
• Abstract要約: 量子近似最適化アルゴリズムの最適化問題に対する量子優位性を実現する能力はまだ不明である。 ランダムなMax-$k$XOR上でのQAOAの性能を$k$の関数と節対変数比として解析する。 満足度の高いレベルに達するには、非常に大きな$p$が必要であり、変動コンテキストと短期デバイスの両方において、かなり難しいとみなす必要がある。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: The ability of the Quantum Approximate Optimization Algorithm (QAOA) to deliver a quantum advantage on combinatorial optimization problems is still unclear. Recently, a scaling advantage over a classical solver was postulated to exist for random 8-SAT at the satisfiability threshold. At the same time, the viability of quantum error mitigation for deep circuits on near-term devices has been put in doubt. Here, we analyze the QAOA's performance on random Max-$k$XOR as a function of $k$ and the clause-to-variable ratio. As a classical benchmark, we use the Mean-Field Approximate Optimization Algorithm (MF-AOA) and find that it performs better than or equal to the QAOA on average. Still, for large $k$ and numbers of layers $p$, there may remain a window of opportunity for the QAOA. However, by extrapolating our numerical results, we find that reaching high levels of satisfaction would require extremely large $p$, which must be considered rather difficult both in the variational context and on near-term devices.
• Abstract（参考訳）: 組合せ最適化問題において量子近似最適化アルゴリズム(QAOA)が量子優位性をもたらす能力は未だ不明である。 近年, 古典解法に対するスケーリングの優位性は, 確率的8-SATに対して, 満足度閾値で存在することが仮定された。 同時に、近距離デバイス上での深部回路の量子誤差低減の可能性は疑問視されている。 ここでは、ランダムなMax-$k$XOR上でのQAOAの性能を、$k$の関数と節対変数比として解析する。 古典的なベンチマークとして,平均場近似最適化アルゴリズム (MF-AOA) を用いて,QAOAの平均値よりも高い性能を示した。 それでも、大きな$kと層数$p$の場合、QAOAの機会の窓口は残っています。 しかし, 数値計算の結果を外挿することにより, 高い満足度に達するには極端に高額のp$が必要であり, 変動状況と短期デバイスの両方において, かなり困難であると考えられる。

関連論文リスト

• 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)
• Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
  変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。 両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
  論文  参考訳（メタデータ） (2024-01-05T15:11:24Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。 この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。 我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
  論文  参考訳（メタデータ） (2023-06-15T15:28:12Z)
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm [0.05076419064097732]
  量子コンピューティング問題とは対照的に,QAOAがハード制約満足度問題を解く能力について検討する。 我々は,QAOAの平均成功確率を,満足度しきい値のランダムな式上で解析的に評価する。 約14のアンザッツ層に対して、QAOAは高性能な古典解法のスケーリング性能と一致することがわかった。
  論文  参考訳（メタデータ） (2022-08-14T20:39:48Z)
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm [0.7046417074932257]
  量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。 古典的解法は線形時間複雑性において高品質な近似解を生成することができる。 異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
  論文  参考訳（メタデータ） (2022-06-07T20:59:19Z)
• 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)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Quantum Computational Phase Transition in Combinatorial Problems [0.966840768820136]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、量子コンピュータにおける離散最適化問題の近似解を求めることを目的としたアルゴリズムである。 SATのような難解な問題を解く際に,QAOAの計算位相遷移を同定する。 本稿では,QAOAの性能に限界がある高問題密度領域が,実際はQAOAを利用するのに最適であることを示す。
  論文  参考訳（メタデータ） (2021-09-27T20:46:52Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• 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)
• Evaluation of QAOA based on the approximation ratio of individual samples [0.0]
  我々は、Max-Cut問題に適用されたQAOAの性能をシミュレートし、いくつかの古典的代替品と比較する。 QAOA計算複雑性理論のガイダンスが進化しているため、量子的優位性を求めるためのフレームワークを利用する。
  論文  参考訳（メタデータ） (2020-06-08T18:00:18Z)

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

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