論文の概要: Realistic Runtime Analysis for Quantum Simplex Computation
- arxiv url: http://arxiv.org/abs/2311.09995v1
- Date: Thu, 16 Nov 2023 16:11:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-17 13:40:36.941818
- Title: Realistic Runtime Analysis for Quantum Simplex Computation
- Title（参考訳）: 量子シンプル計算のための実時間解析
- Authors: Sabrina Ammann, Maximilian Hess, Debora Ramacciotti, S\'andor P.
Fekete, Paulina L. A. Goedicke, David Gross, Andreea Lefterovici, Tobias J.
Osborne, Michael Perk, Antonio Rotundo, S. E. Skelton, Sebastian Stiller,
Timo de Wolff
- Abstract要約: 重要な最適化問題の現実のインスタンスを解く際に,古典的ランタイム解析のための量子アナログを提案する。
現実的な問題サイズに対する現実的な量子的優位性は、現在の物理的な制限よりもかなり低い量子ゲート演算時間を必要とすることを示します。
- 参考スコア（独自算出の注目度）: 0.4407851469168588
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In recent years, strong expectations have been raised for the possible power
of quantum computing for solving difficult optimization problems, based on
theoretical, asymptotic worst-case bounds. Can we expect this to have
consequences for Linear and Integer Programming when solving instances of
practically relevant size, a fundamental goal of Mathematical Programming,
Operations Research and Algorithm Engineering? Answering this question faces a
crucial impediment: The lack of sufficiently large quantum platforms prevents
performing real-world tests for comparison with classical methods.
In this paper, we present a quantum analog for classical runtime analysis
when solving real-world instances of important optimization problems. To this
end, we measure the expected practical performance of quantum computers by
analyzing the expected gate complexity of a quantum algorithm. The lack of
practical quantum platforms for experimental comparison is addressed by hybrid
benchmarking, in which the algorithm is performed on a classical system,
logging the expected cost of the various subroutines that are employed by the
quantum versions. In particular, we provide an analysis of quantum methods for
Linear Programming, for which recent work has provided asymptotic speedup
through quantum subroutines for the Simplex method. We show that a practical
quantum advantage for realistic problem sizes would require quantum gate
operation times that are considerably below current physical limitations.
- Abstract（参考訳）: 近年、理論的に漸近的な最悪ケース境界に基づいて、難解な最適化問題を解く量子コンピューティングの可能性に対して強い期待が寄せられている。
数学的プログラミング、オペレーションリサーチ、アルゴリズム工学の基本的な目標である、実際に関連するサイズのインスタンスを解く際に、線形プログラミングと整数プログラミングが結果をもたらすと期待できますか?
十分に大きな量子プラットフォームがないことで、古典的な手法と比較する実際のテストの実行が妨げられます。
本稿では,重要な最適化問題の実例を解く際に,古典的ランタイム解析のための量子アナログを提案する。
この目的のために,量子アルゴリズムの期待ゲート複雑性を解析し,量子コンピュータの期待実用性能を測定する。
実験的な比較のための実用的な量子プラットフォームがないことは、古典的なシステム上でアルゴリズムが実行されるハイブリッドベンチマークによって解決され、量子バージョンで使用される様々なサブルーチンの期待コストが記録される。
特に、線形計画法における量子法の解析を行い、最近の研究はSimplex法に対する量子サブルーチンによる漸近的高速化を提供している。
現実的な問題サイズに対する実用的な量子アドバンテージは、現在の物理的限界を大幅に下回る量子ゲート操作時間を必要とする。
関連論文リスト
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Parallel Quantum Computing Simulations via Quantum Accelerator Platform Virtualization [44.99833362998488]
本稿では,量子回路実行の並列化モデルを提案する。
このモデルはバックエンドに依存しない機能を利用することができ、任意のターゲットバックエンド上で並列量子回路の実行を可能にする。
論文 参考訳（メタデータ） (2024-06-05T17:16:07Z) - 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) - NP-hard but no longer hard to solve? Using quantum computing to tackle
optimization problems [1.1470070927586016]
量子コンピュータを用いて最適化問題を解く量子最適化の分野について論じる。
適切なユースケースを通じてこれを実証し、量子コンピュータの現在の品質について論じる。
本稿では、最近の量子最適化のブレークスルーと現状と今後の方向性について論じる。
論文 参考訳（メタデータ） (2022-12-21T12:56:37Z) - Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the
Race to Practical Quantum Advantage [43.3054117987806]
本稿では,量子回路の初期化を最適化するために,古典計算資源を利用するスケーラブルな手法を提案する。
本手法は, PQCのトレーニング性, 性能を, 様々な問題において著しく向上させることを示す。
古典的コンピュータを用いて限られた量子資源を増強する手法を実証することにより、量子コンピューティングにおける量子と量子に着想を得たモデル間の相乗効果を実証する。
論文 参考訳（メタデータ） (2022-08-29T15:24:03Z) - Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
古典的なエミュレーションと、すべての定数を含む詳細な複雑性境界を組み合わせたアプローチを考える。
本手法を古典的アルゴリズムの単純量子スピードアップに適用し,よく研究されたMAX-$k$-SAT最適化問題を解く。
これは、2つの重要な量子サブルーチンの期待と最悪のケースの複雑さに厳密な境界(全定数を含む)を必要とする。
論文 参考訳（メタデータ） (2022-03-09T19:00:00Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。
変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。
量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
論文 参考訳（メタデータ） (2021-08-09T18:00:05Z) - Quantum mean value approximator for hard integer value problems [19.4417702222583]
正確な予想よりも近似を用いることで、最適化を大幅に改善できることを示す。
効率的な古典的サンプリングアルゴリズムとともに、極小ゲート数を持つ量子アルゴリズムは、一般的な整数値問題の効率を向上させることができる。
論文 参考訳（メタデータ） (2021-05-27T13:03:52Z) - Towards quantum advantage via topological data analysis [0.0]
ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。
ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-05-06T06:31:24Z) - Large-scale quantum hybrid solution for linear systems of equations [0.0]
指数的高速化を伴う方程式の線形系を解くためのハイブリッド量子アルゴリズムを導入,実装する。
我々は、量子コンピュータ上での線形システム解の記録である超伝導IBMQデバイスにおける217ドルの次元問題を実験的に解決した。
論文 参考訳（メタデータ） (2020-03-28T11:23:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。