論文の概要: Quantum Enhanced Greedy Solver for Optimization Problems

• arxiv url: http://arxiv.org/abs/2303.05509v1
• Date: Thu, 9 Mar 2023 18:59:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-10 13:28:29.879269
• Title: Quantum Enhanced Greedy Solver for Optimization Problems
• Title（参考訳）: 最適化問題に対する量子強化グリーディソルバー
• Authors: Maxime Dupont, Bram Evert, Mark J. Hodson, Bhuvanesh Sundar, Stephen Jeffrey, Yuki Yamaguchi, Dennis Feng, Filip B. Maciejewski, Stuart Hadfield, M. Sohaib Alam, Zhihui Wang, Shon Grabbe, P. Aaron Lott, Eleanor G. Rieffel, Davide Venturelli, Matthew J. Reagor
• Abstract要約: 平均最悪の性能を持つ反復型量子最適化アルゴリズムを提案する。 このアルゴリズムは、72キュービットまでの量子ビットを用いて、シリントン・カークパトリック・イジングスピングラスの問題を解くために、プログラム可能な超伝導量子システムに実装する。
• 参考スコア（独自算出の注目度）: 8.272107199483203
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization is a broadly attractive area for potential quantum advantage, but no quantum algorithm has yet made the leap. Noise in quantum hardware remains a challenge, and more sophisticated quantum-classical algorithms are required to bolster performance guarantees. Here, we introduce an iterative quantum heuristic optimization algorithm with an average worst-case performance, in the presence of depolarizing quantum noise, equivalent to that of a classical greedy algorithm. We implement this algorithm on a programmable superconducting quantum system using up to 72 qubits for solving paradigmatic Sherrington-Kirkpatrick Ising spin glass problems. The quantum-classical algorithm systematically outperforms its classical counterpart, signaling a quantum enhancement with respect to its guaranteed output quality. Moreover, we observe an absolute performance comparable with the guarantees for a state-of-the-art semi-definite programming method. Classical simulations of the algorithm illustrate that a key challenge to reaching quantum advantage remains improving the quantum device characteristics.
• Abstract（参考訳）: 組合せ最適化は潜在的な量子アドバンテージにとって広く魅力的な分野だが、量子アルゴリズムがまだ飛躍を遂げていない。 量子ハードウェアのノイズは依然として課題であり、より洗練された量子古典アルゴリズムは性能保証を強化するために必要である。 本稿では,古典的グリードアルゴリズムと等価な非分極量子雑音の存在下で,平均最悪の性能を有する反復型量子ヒューリスティック最適化アルゴリズムを提案する。 このアルゴリズムを最大72量子ビットを用いてプログラム可能な超伝導量子システム上で実装し、シェリントン・カークパトリックのスピンガラス問題を解く。 量子古典アルゴリズムはその古典的なアルゴリズムを体系的に上回っており、その保証された出力品質に関して量子拡張を示唆している。 さらに,最先端半確定プログラミング手法の保証に匹敵する絶対性能を観測する。 このアルゴリズムの古典的なシミュレーションは、量子優位に達するための重要な課題が量子デバイス特性の改善であることを示している。

関連論文リスト

• Hybrid quantum-classical approach for combinatorial problems at hadron colliders [7.2572969510173655]
  粒子物理学実験における問題を解くために量子アルゴリズムの可能性を探る。 大型ハドロン衝突型加速器の完全ハドロンチャネルにおけるトップクォーク対生成について検討した。 量子アルゴリズムを用いることで,正しいペアリングを選択する効率を大幅に向上することを示す。
  論文  参考訳（メタデータ） (2024-10-29T18:00:07Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。 どの場の量子スピードアップが達成できるかという新たな課題が生じる。 量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
  論文  参考訳（メタデータ） (2024-02-26T09:32:07Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  本稿では,二項問題の近似解を計算するためのハイブリッド量子古典アルゴリズムを提案する。 我々は、重み付き最大カットまたはイジング・ハミルトン演算子をブロック符号化するユニタリおよびエルミート演算子を実装するために浅深さ量子回路を用いる。 この作用素の変動量子状態への期待を測定すると、量子系の変動エネルギーが得られる。
  論文  参考訳（メタデータ） (2023-06-10T23:28:13Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• The Role of Entanglement in Quantum-Relaxation Based Optimization Algorithms [4.00916638804083]
  量子ランダムアクセスコード(QRAC)は、バイナリ最適化の複数の変数を1量子ビットでエンコードする。 この結果から,QRAOは量子コンピュータに制限された二項最適化問題の解決可能なインスタンスをスケールできるだけでなく,量子絡み合いの恩恵を受けることが示唆された。
  論文  参考訳（メタデータ） (2023-02-01T13:24:51Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer [13.528362112761805]
  本稿では,量子ハードウェアの制約を保存する量子最適化アルゴリズムの,これまでで最大の実行方法を示す。 我々は、最大20キュービットと2キュービットゲート深さ最大159の量子進化を制限するXY-QAOA回路を実行する。 本稿では,アルゴリズムのトレードオフと,短期量子ハードウェア上での実行に対する影響について論じる。
  論文  参考訳（メタデータ） (2022-06-13T16:21:04Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Surviving The Barren Plateau in Variational Quantum Circuits with Bayesian Learning Initialization [0.0]
  変分量子古典ハイブリッドアルゴリズムは、近い将来に量子コンピュータの実用的な問題を解くための有望な戦略と見なされている。 本稿では,ベイズ空間における有望な領域を特定するために勾配を用いた高速・スローアルゴリズムを提案する。 本研究は, 量子化学, 最適化, 量子シミュレーション問題における変分量子アルゴリズムの応用に近づいたものである。
  論文  参考訳（メタデータ） (2022-03-04T17:48:57Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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