論文の概要: Assessing Quantum and Classical Approaches to Combinatorial Optimization: Testing Quadratic Speed-ups for Heuristic Algorithms

• arxiv url: http://arxiv.org/abs/2412.13035v1
• Date: Tue, 17 Dec 2024 15:59:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-18 13:58:01.421925
• Title: Assessing Quantum and Classical Approaches to Combinatorial Optimization: Testing Quadratic Speed-ups for Heuristic Algorithms
• Title（参考訳）: 組合せ最適化への量子的および古典的アプローチの評価:ヒューリスティックアルゴリズムの2次高速化をテストする
• Authors: Pedro C. S. Costa, Mauro E. S. Morales, Dong An, Yuval R. Sanders,
• Abstract要約: 2次最適化(CO)における量子および古典的ベンチマークの課題を取り上げる。 我々の数値解析は、現在の手法が量子的優位性を全く示さないという考え方に疑問を投げかけている。 我々は、COの量子優位性を評価するためには、より慎重な数値的な調査が必要であると結論付けている。
• 参考スコア（独自算出の注目度）: 2.1909093150752303
• License:
• Abstract: Many recent investigations conclude, based on asymptotic complexity analyses, that quantum computers could accelerate combinatorial optimization (CO) tasks relative to a purely classical computer. However, asymptotic analysis alone cannot support a credible claim of quantum advantage. Here, we highlight the challenges involved in benchmarking quantum and classical heuristics for combinatorial optimization (CO), with a focus on the Sherrington-Kirkpatrick problem. Whereas hope remains that a quadratic quantum advantage is possible,our numerical analysis casts doubt on the idea that current methods exhibit any quantum advantage at all. This doubt arises because even a simple classical approach can match with quantum methods we investigated. We conclude that more careful numerical investigations are needed to evaluate the potential for quantum advantage in CO, and we give some possible future directions for such investigations.
• Abstract（参考訳）: 最近の多くの研究は、漸近的複雑性分析に基づいて、量子コンピュータは純粋に古典的なコンピュータと比較して組合せ最適化(CO)タスクを加速することができると結論付けている。 しかし、漸近解析だけでは、量子優位性の信頼できる主張を支持できない。 ここでは、シェリントン・カークパトリック問題に焦点をあて、組合せ最適化(CO)のための量子および古典的ヒューリスティックのベンチマークに関わる課題を取り上げる。 二次的な量子的優位性が可能であるという希望は残るが、我々の数値解析は、現在の方法が量子的優位性を全く示さないという考えに疑問を投げかける。 この疑問は、単純な古典的アプローチでさえ、我々が調査した量子法と一致するためである。 我々は、COにおける量子優位性の可能性を評価するためにより慎重な数値的な調査が必要であると結論し、そのような調査の今後の方向性を示す。

関連論文リスト

• Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing [0.0]
  この研究で、限られた資源を持つ量子がNPハード問題に対する大規模な正確な最適化アルゴリズムにどのように統合できるかを実証する。 我々のアルゴリズムの重要な特徴は、量子によって返される最良の解からではなく、あるコスト閾値以下の全ての解から得られることである。
  論文  参考訳（メタデータ） (2024-12-20T08:27:23Z)
• Realistic Runtime Analysis for Quantum Simplex Computation [0.4407851469168588]
  重要な最適化問題の現実のインスタンスを解く際に,古典的ランタイム解析のための量子アナログを提案する。 現実的な問題サイズに対する現実的な量子的優位性は、現在の物理的な制限よりもかなり低い量子ゲート演算時間を必要とすることを示します。
  論文  参考訳（メタデータ） (2023-11-16T16:11:44Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。 結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
  論文  参考訳（メタデータ） (2023-04-17T16:42:05Z)
• An introduction to variational quantum algorithms for combinatorial optimization problems [0.0]
  このチュートリアルは変分量子アルゴリズムのクラスに関する数学的記述を提供する。 量子側および古典側におけるこれらのハイブリッドアルゴリズムの重要な側面を正確に紹介する。 我々はQAOAに特に注意を払って、そのアルゴリズムに関わる量子回路と、その可能な誘導関数によって満たされる特性を詳述した。
  論文  参考訳（メタデータ） (2022-12-22T14:27:52Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  量子計算を古典的な結果によって補う手法を提案する。 予測の利点を生かして、新しいタイプの量子測度がもたらされる。 予測量子測定では、古典計算と量子計算の結果の組み合わせは最後にのみ起こる。
  論文  参考訳（メタデータ） (2022-09-12T15:47:44Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  本稿では,量子回路の初期化を最適化するために,古典計算資源を利用するスケーラブルな手法を提案する。 本手法は, PQCのトレーニング性, 性能を, 様々な問題において著しく向上させることを示す。 古典的コンピュータを用いて限られた量子資源を増強する手法を実証することにより、量子コンピューティングにおける量子と量子に着想を得たモデル間の相乗効果を実証する。
  論文  参考訳（メタデータ） (2022-08-29T15:24:03Z)
• Limitations of optimization algorithms on noisy quantum devices [0.0]
  我々は、古典的アルゴリズムと、短期的な量子デバイス上で動作している量子アルゴリズムを比較する透過的な方法を提案する。 我々のアプローチは、量子状態がノイズモデルの定点にどれだけ早く収束するかを決定するエントロピック不等式の組み合わせに基づいている。
  論文  参考訳（メタデータ） (2020-09-11T17:07:26Z)
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing [0.0]
  量子アニール(QA)の一般的な枠組みにおけるアルゴリズムの展望を評価し,量子スピードアップを実現する。 我々は、コヒーレンス時間と制御能力の改善が、いくつかの量子最適化アルゴリズムの短期的な探索を可能にすることに基づいて、QAフレームワークへの継続的な探索と関心を論じる。 これらの全てのプロトコルは、時間依存の有効横場イジング・ハミルトンにより生成される新しい平衡量子力学の全ての範囲を受け入れることによって、最先端の方法で探索することができると論じる。
  論文  参考訳（メタデータ） (2020-08-22T21:25:51Z)

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

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