論文の概要: Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm

• arxiv url: http://arxiv.org/abs/2206.03579v2
• Date: Tue, 25 Jul 2023 17:27:39 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-26 21:38:15.387064
• Title: Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Title（参考訳）: 量子近似最適化アルゴリズムの量子利用のためのサンプリング周波数閾値
• Authors: Danylo Lykov, Jonathan Wurtz, Cody Poole, Mark Saffman, Tom Noel, Yuri Alexeev
• Abstract要約: 量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。 古典的解法は線形時間複雑性において高品質な近似解を生成することができる。 異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
• 参考スコア（独自算出の注目度）: 0.7046417074932257
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers such as Gurobi and MQLib to solve the combinatorial optimization problem MaxCut on 3-regular graphs. The goal is to identify under which conditions QAOA can achieve "quantum advantage" over classical algorithms, in terms of both solution quality and time to solution. One might be able to achieve quantum advantage on hundreds of qubits and moderate depth $p$ by sampling the QAOA state at a frequency of order 10 kHz. We observe, however, that classical heuristic solvers are capable of producing high-quality approximate solutions in linear time complexity. In order to match this quality for $\textit{large}$ graph sizes $N$, a quantum device must support depth $p>11$. Otherwise, we demonstrate that the number of required samples grows exponentially with $N$, hindering the scalability of QAOA with $p\leq11$. These results put challenging bounds on achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, maximum independent set, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.
• Abstract（参考訳）: 本研究では, 量子近似最適化アルゴリズム (qaoa) の性能と, gurobi や mqlib のような最先端の古典的解法との比較を行い, 3次元正則グラフ上での組合せ最適化問題maxcut を解く。 ゴールは、QAOAが古典的なアルゴリズムよりも「量子優位性」が得られる条件を、ソリューションの品質と解決までの時間の両方の観点から特定することである。 10khzの周波数でqaoa状態をサンプリングすることで、数百キュービットと適度な深さのp$で量子優位が得られるかもしれない。 しかし、古典的ヒューリスティック解法は線形時間複雑性において高品質な近似解を生成することができる。 この品質を$\textit{large}$グラフサイズ$n$に合わせるためには、量子デバイスは深さ$p>11$をサポートする必要がある。 さもなくば、必要なサンプルの数は、$N$で指数関数的に増加し、$p\leq11$でQAOAのスケーラビリティを妨げることが示される。 これらの結果から、3つの正則グラフ上のQAOA MaxCutに対する量子優位性の実現に挑戦的な限界が得られた。 他の問題、例えば異なるグラフ、重み付きマックスカット、最大独立集合、および3satは、近距離量子デバイスでの量子優位を達成するのに適しているかもしれない。

関連論文リスト

• Recursive Quantum Relaxation for Combinatorial Optimization Problems [3.3053321430025258]
  既存の量子最適化手法のいくつかは、最適量子状態から最も高い確率で測定される二項解を求める解法に統一可能であることを示す。 テンソルネットワーク技術を用いたMAX-CUT問題における数百ノードの標準ベンチマークグラフの実験は、RQRAOがゴーマン-ウィリアムソン法より優れ、最先端の古典的解法に匹敵することを示した。
  論文  参考訳（メタデータ） (2024-03-04T13:48:21Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin Models [8.463477025989542]
  我々は、デジタルカウンタダイバティック量子最適化(DCQO)アルゴリズムを利用して、4つの局所相互作用までの$p$-spinモデルの最適解を求める。 変分法を用いてパラメータを最適化することにより,それぞれ100ドル,93%,83%のインスタンスに対して,単位精度2-スピン,3-スピン,4-スピンの問題を解く。
  論文  参考訳（メタデータ） (2023-11-11T22:49:16Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  量子Max-$d$-Cut問題(Quantum Max-$d$-Cut problem)は、プロジェクターに付随する期待エネルギーを、全ての局所相互作用上の2つの$d$-dimensional quditsの非対称部分空間に最大化する量子状態を見つけることである。 我々は,非自明な性能保証を実現するために,有界な純度を持つ混合状態の積状態解を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-09-19T22:53:17Z)
• Alleviating the quantum Big-$M$ problem [0.237499051649312]
  古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。 我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。 本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-19T18:00:05Z)
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization [0.0]
  本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。 目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
  論文  参考訳（メタデータ） (2023-05-23T16:17:57Z)
• 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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。 本稿では,QAOAの回路深度依存性能について実験的に検討する。 この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
  論文  参考訳（メタデータ） (2020-05-11T17:20:51Z)

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

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