論文の概要: 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年の研究を、一般の科学読者向けに調査しました。 量子回路モデルについて論じていますが、私たちの知識は根本的に不完全ですし、いわゆるオラクルやブラックボックス、クエリの複雑さモデルも議論しています。 最近の量子超越実験のように、サンプリングタスクに注意を移すことの強みと弱みについて論じる。 実用的機械学習と最適化問題に対する指数関数的量子スピードアップの広範にわたる主張に対して、いくつかの懐疑的な意見を述べます。 多くの例を通して、指数的量子スピードアップを許容するすべての問題は、振幅が未知の右の答えに集中できるように、いくつかの異常な性質を持つ必要があるという「奇数の保存の法則」を伝えようとしている。

関連論文リスト

• Towards Entropic Constraints on Quantum Speedups [0.0]
  いくつかの量子アルゴリズムは「量子スピードアップ(quantum speedups)」を持ち、同じタスクを解くための最もよく知られた古典的アルゴリズムと比較して、時間複雑性を改善している。 エントロピーの観点から、これらのスピードアップに何をもたらすのか理解できますか? 情報理論は、アルゴリズムを実行する量子コンピュータの振る舞いを「量子」がいかに根本的に測定するかを測定するために、私たちが選択できる様々な指標を与えてくれる。
  論文  参考訳（メタデータ） (2024-11-05T19:00:04Z)
• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。 同じ手法は他の1次元階層グラフにも適用できる。
  論文  参考訳（メタデータ） (2024-04-30T11:45:49Z)
• Quantum Optimization for the Maximum Cut Problem on a Superconducting Quantum Computer [0.3518016233072556]
  半定値アプローチに着想を得たハイブリッド量子古典アルゴリズムの性能について検討した。 何千もの問題インスタンスのランダムアンサンブルに対して平均99%のパフォーマンスを達成した。 実行時解析により、大規模問題における量子解法は、グロビと競合するが、他の問題には劣ることを示した。
  論文  参考訳（メタデータ） (2024-04-26T17:59:22Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• 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)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• 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)

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

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