論文の概要: Limits of quantum speed-ups for computational geometry and other
problems: Fine-grained complexity via quantum walks
- arxiv url: http://arxiv.org/abs/2106.02005v1
- Date: Thu, 3 Jun 2021 17:22:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-27 23:10:27.327344
- Title: Limits of quantum speed-ups for computational geometry and other
problems: Fine-grained complexity via quantum walks
- Title（参考訳）: 計算幾何学やその他の問題に対する量子スピードアップの限界:量子ウォークによる微細な複雑性
- Authors: Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman
- Abstract要約: いくつかの計算問題に対して、量子アルゴリズムの時間的複雑さを最適に下界として証明する。
我々の下界のほとんどは、既知の上界と一致しているため、量子スピードアップに厳しい制限が課せられるため、最適である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many computational problems are subject to a quantum speed-up: one might find
that a problem having an O(n^3)-time or O(n^2)-time classic algorithm can be
solved by a known O(n^1.5)-time or O(n)-time quantum algorithm. The question
naturally arises: how much quantum speed-up is possible?
The area of fine-grained complexity allows us to prove optimal lower-bounds
on the complexity of various computational problems, based on the conjectured
hardness of certain natural, well-studied problems. This theory has recently
been extended to the quantum setting, in two independent papers by Buhrman,
Patro, and Speelman (arXiv:1911.05686), and by Aaronson, Chia, Lin, Wang, and
Zhang (arXiv:1911.01973).
In this paper, we further extend the theory of fine-grained complexity to the
quantum setting. A fundamental conjecture in the classical setting states that
the 3SUM problem cannot be solved by (classical) algorithms in time O(n^{2-a}),
for any a>0. We formulate an analogous conjecture, the Quantum-3SUM-Conjecture,
which states that there exist no sublinear O(n^{1-b})-time quantum algorithms
for the 3SUM problem.
Based on the Quantum-3SUM-Conjecture, we show new lower-bounds on the time
complexity of quantum algorithms for several computational problems. Most of
our lower-bounds are optimal, in that they match known upper-bounds, and hence
they imply tight limits on the quantum speedup that is possible for these
problems.
- Abstract（参考訳）: 多くの計算問題は量子スピードアップの対象となり、O(n^3)時間またはO(n^2)時間古典アルゴリズムを持つ問題は、既知のO(n^1.5)時間またはO(n)時間量子アルゴリズムによって解くことができる。
量子スピードアップはどの程度可能ですか?
きめ細かい複雑さの領域は、ある種の自然でよく研究された問題の予想された硬さに基づいて、様々な計算問題の複雑性の最適下限を証明できる。
この理論は近年、buhrman, patro, speelman (arxiv:1911.05686) とaaronson, chia, lin, wang, zhang (arxiv:1911.01973) の2つの独立論文で量子集合にまで拡張されている。
本稿では,細粒度複雑性の理論をさらに量子集合にまで拡張する。
古典的な設定の基本的な予想では、3SUM問題は任意の a>0 に対して時間 O(n^{2-a}) における(古典的な)アルゴリズムでは解けない。
類似の予想であるQuantum-3SUM-Conjectureを定式化し、3SUM問題に対して線形O(n^{1-b})時間量子アルゴリズムが存在しないことを述べる。
量子 3sum-conjecture に基づいて、いくつかの計算問題に対する量子アルゴリズムの時間複雑性の新たな下界を示す。
我々の下界の大部分は、既知の上界と一致するため、これらの問題に対して可能な量子スピードアップの制限が厳しくなるという点で最適である。
関連論文リスト
- Towards Entropic Constraints on Quantum Speedups [0.0]
いくつかの量子アルゴリズムは「量子スピードアップ(quantum speedups)」を持ち、同じタスクを解くための最もよく知られた古典的アルゴリズムと比較して、時間複雑性を改善している。
エントロピーの観点から、これらのスピードアップに何をもたらすのか理解できますか?
情報理論は、アルゴリズムを実行する量子コンピュータの振る舞いを「量子」がいかに根本的に測定するかを測定するために、私たちが選択できる様々な指標を与えてくれる。
論文 参考訳（メタデータ） (2024-11-05T19:00:04Z) - Bosonic Quantum Computational Complexity [0.0]
私たちはそのような研究計画の基礎をつくった。
本稿では,BQPのボゾン一般化に基づく自然複雑性クラスと問題を紹介する。
ボソニックハミルトニアンのスペクトルの有界性を決定する問題はコ-NPハードであることを示す。
論文 参考訳（メタデータ） (2024-10-05T19:43:41Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - QSETH strikes again: finer quantum lower bounds for lattice problem,
strong simulation, hitting set problem, and more [5.69353915790503]
現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。
量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか?
QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
論文 参考訳（メタデータ） (2023-09-28T13:30:20Z) - Quantum and classical query complexities for determining connectedness
of matroids [5.654637296499481]
接続性はマトロイドの基本的な構造特性であり、アルゴリズムによって50年以上研究されてきた。
量子アルゴリズムは$O(n3/2)$クエリで、古典的なクエリよりも証明可能な量子スピードアップを示す。
論文 参考訳（メタデータ） (2023-06-21T08:31:52Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Quantum communication complexity of linear regression [0.05076419064097732]
量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。
本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
論文 参考訳（メタデータ） (2022-10-04T13:27:01Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。