論文の概要: How Much Structure Is Needed for Huge Quantum Speedups?
- arxiv url: http://arxiv.org/abs/2209.06930v1
- Date: Wed, 14 Sep 2022 21:09:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-26 16:41:29.118411
- Title: How Much Structure Is Needed for Huge Quantum Speedups?
- Title(参考訳): 量子速度アップにはどのくらいの構造が必要か?
- Authors: Scott Aaronson
- Abstract要約: 私は、一般的な科学的な聴衆に対して、量子コンピュータによる指数的なスピードアップを許容する問題について30年間の研究を行いました。
量子回路モデルといわゆるオラクルモデル、ブラックボックスモデル、クエリ複雑性モデルの両方について論じる。
私は、実用的な機械学習と最適化問題に対する指数的量子スピードアップの広範囲にわたる主張について、懐疑的な発言をしている。
- 参考スコア(独自算出の注目度): 4.467248776406005
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: I survey, for a general scientific audience, three decades of research into
which sorts of problems admit exponential speedups via quantum computers --
from the classics (like the algorithms of Simon and Shor), to the breakthrough
of Yamakawa and Zhandry from April 2022. I discuss both the quantum circuit
model, which is what we ultimately care about in practice but where our
knowledge is radically incomplete, and the so-called oracle or black-box or
query complexity model, where we've managed to achieve a much more thorough
understanding that then informs our conjectures about the circuit model. I
discuss the strengths and weaknesses of switching attention to sampling tasks,
as was done in the recent quantum supremacy experiments. I make some skeptical
remarks about widely-repeated claims of exponential quantum speedups for
practical machine learning and optimization problems. Through many examples, I
try to convey the "law of conservation of weirdness," according to which every
problem admitting an exponential quantum speedup must have some unusual
property to allow the amplitude to be concentrated on the unknown right
answer(s).
- Abstract(参考訳): 2022年4月の山川とZhandryの突破口から古典的な(SimonとShorのアルゴリズムのような)量子コンピュータによる指数的なスピードアップを許容する問題に関する30年の研究を、一般の科学読者向けに調査しました。
量子回路モデルについて論じていますが、私たちの知識は根本的に不完全ですし、いわゆるオラクルやブラックボックス、クエリの複雑さモデルも議論しています。
最近の量子超越実験のように、サンプリングタスクに注意を移すことの強みと弱みについて論じる。
実用的機械学習と最適化問題に対する指数関数的量子スピードアップの広範にわたる主張に対して、いくつかの懐疑的な意見を述べます。
多くの例を通して、指数的量子スピードアップを許容するすべての問題は、振幅が未知の右の答えに集中できるように、いくつかの異常な性質を持つ必要があるという「奇数の保存の法則」を伝えようとしている。
関連論文リスト
- Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳(メタデータ) (2023-10-04T17:53:55Z) - Disentangling Hype from Practicality: On Realistically Achieving Quantum
Advantage [13.163255711706864]
我々は、量子コンピュータを実際に有用なものにするためには、小さなデータ問題と超二乗スピードアップを伴う量子アルゴリズムが不可欠であると主張している。
提案された量子アルゴリズムや応用のほとんどは、実用的と考えられるために必要なスピードアップを達成できていないが、物質科学や化学において、すでに大きなポテンシャルを見出している。
論文 参考訳(メタデータ) (2023-07-02T09:14:32Z) - Improving Metrology with Quantum Scrambling [0.520082039162174]
量子スクランブル(Quantum scrambling)は、多体量子系の多くの自由度に量子情報の高速な拡散を記述する。
我々は,Lipkin-Meshkov-Glick (LMG)多体ハミルトニアンの指数的揺らぎ特性を探索する。
我々の実験は、制御されたテーブルトップ実験における量子カオスとスクランブルの研究への道を開いた。
論文 参考訳(メタデータ) (2022-12-24T20:00:52Z) - Quantum communication complexity of linear regression [0.05076419064097732]
量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。
本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
論文 参考訳(メタデータ) (2022-10-04T13:27:01Z) - Demonstrating robust simulation of driven-dissipative problems on
near-term quantum computers [53.20999552522241]
量子コンピュータは物理学と化学における量子力学系のシミュレーションに革命をもたらす。
現在の量子コンピュータは、訂正されていないノイズ、ゲートエラー、デコヒーレンスのためにアルゴリズムを不完全に実行している。
ここでは、量子力学における最も難しい問題の1つとして、駆動散逸多体問題の解法が本質的にエラーに対して堅牢であることを示す。
論文 参考訳(メタデータ) (2021-08-02T21:36:37Z) - Limits of quantum speed-ups for computational geometry and other
problems: Fine-grained complexity via quantum walks [0.0]
いくつかの計算問題に対して、量子アルゴリズムの時間的複雑さを最適に下界として証明する。
我々の下界のほとんどは、既知の上界と一致しているため、量子スピードアップに厳しい制限が課せられるため、最適である。
論文 参考訳(メタデータ) (2021-06-03T17:22:08Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
想像時間における進化は、量子多体系の基底状態を見つけるための顕著な技術である。
本稿では,量子コンピュータ上での仮想時間伝搬を実現するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-02-24T12:48:00Z) - Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
53量子ビット量子プロセッサにおける量子スクランブルのダイナミクスを実験的に検討する。
演算子の拡散は効率的な古典的モデルによって捉えられるが、演算子の絡み合いは指数関数的にスケールされた計算資源を必要とする。
論文 参考訳(メタデータ) (2021-01-21T22:18:49Z) - Quantum walk processes in quantum devices [55.41644538483948]
グラフ上の量子ウォークを量子回路として表現する方法を研究する。
提案手法は,量子ウォークアルゴリズムを量子コンピュータ上で効率的に実装する方法である。
論文 参考訳(メタデータ) (2020-12-28T18:04:16Z) - Sampling random quantum circuits: a pedestrian's guide [0.0]
Google、NASAエイムズ、カリフォルニア大学サンタバーバラ校などの共同研究グループによる最近の実験は、超伝導量子プロセッサ上で量子超越性が達成されたことを示す説得力のある証拠となった。
残念なことに、量子超越性を定義するためにこの理論的基礎をどのように利用できるかを理解することは、非常に難しい課題である。
本稿は、Googleの量子超越性実験の理論的基礎を理解したい人々にとって、量子超越性に関する正確な数学的定義の導出を慎重に行うことで、この困難を軽減しようとする試みである。
論文 参考訳(メタデータ) (2020-07-10T19:26:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。