Fugu-MT 論文翻訳(概要): On the quantum time complexity of divide and conquer

論文の概要: On the quantum time complexity of divide and conquer

arxiv url: http://arxiv.org/abs/2311.16401v1
Date: Tue, 28 Nov 2023 01:06:03 GMT
ステータス: 処理完了
システム内更新日: 2023-11-29 20:52:45.806201
Title: On the quantum time complexity of divide and conquer
Title（参考訳）: 分割と征服の量子時間複雑性について
Authors: Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha
Abstract要約: 量子分割の時間的複雑さと古典的問題に対するアルゴリズムの克服について検討する。これらの定理を、弦、整数、幾何学的対象を含む一連の問題に適用する。
参考スコア（独自算出の注目度）: 42.7410400783548
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We initiate a systematic study of the time complexity of quantum divide and conquer algorithms for classical problems. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup and apply these theorems to an array of problems involving strings, integers, and geometric objects. They include LONGEST DISTINCT SUBSTRING, KLEE'S COVERAGE, several optimization problems on stock transactions, and k-INCREASING SUBSEQUENCE. For most of these results, our quantum time upper bound matches the quantum query lower bound for the problem, up to polylogarithmic factors.
Abstract（参考訳）: 我々は,古典的問題に対する量子分割アルゴリズムの時間複雑性を体系的に研究する。古典的除算アルゴリズムによる探索と最小化の問題が量子スピードアップに有効である一般的な条件を確立し、これらの定理を弦、整数、幾何学的対象を含む一連の問題に適用する。その中には、LongEST DISTINCT SUBSTRING、KLEE's COVERAGE、ストック取引における最適化問題、k-IncrASING SUBsequenceなどがある。これらの結果のほとんどにおいて、我々の量子時間上限は問題に対する量子クエリ下限に一致し、多対数因子までである。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
A Faster Algorithm for the Free Energy in One-Dimensional Quantum Systems [0.0]
翻訳不変な1次元量子スピン系の自由エネルギー密度を有限範囲で近似する問題を考える。この問題の複雑さは、既知の硬度問題と密接な関係にあるため自明ではないが、最近、古典的なサブポリノミカル時間アルゴリズムが提案されている。そこで本研究では,これより優れたアルゴリズムを提案し,その実行時に厳密なバウンダリを与える。
論文参考訳（メタデータ） (2024-02-29T10:42:18Z)
Lower bounds for quantum-inspired classical algorithms via communication complexity [0.5461938536945723]
線形回帰の解法,クラスタリングの監督,主成分分析,レコメンデーションシステム,ハミルトニアンシミュレーションに焦点をあてる。基底行列のフロベニウスノルムの観点で二次下界を証明する。これらの問題に対する量子アルゴリズムはフロベニウスノルムにおいて線型であるため、この結果は量子古典的分離が少なくとも二次的であることを意味する。
論文参考訳（メタデータ） (2024-02-24T02:15:00Z)
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 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)
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文参考訳（メタデータ） (2022-09-28T17:53:25Z)
Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
古典的なエミュレーションと、すべての定数を含む詳細な複雑性境界を組み合わせたアプローチを考える。本手法を古典的アルゴリズムの単純量子スピードアップに適用し,よく研究されたMAX-$k$-SAT最適化問題を解く。これは、2つの重要な量子サブルーチンの期待と最悪のケースの複雑さに厳密な境界(全定数を含む)を必要とする。
論文参考訳（メタデータ） (2022-03-09T19:00:00Z)

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