論文の概要: Lower bounds for quantum-inspired classical algorithms via communication
complexity
- arxiv url: http://arxiv.org/abs/2402.15686v1
- Date: Sat, 24 Feb 2024 02:15:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-27 17:31:41.635507
- Title: Lower bounds for quantum-inspired classical algorithms via communication
complexity
- Title(参考訳): 通信複雑性を用いた量子インスパイアされた古典アルゴリズムの下限
- Authors: Nikhil S. Mande and Changpeng Shao
- Abstract要約: 線形回帰の解法,クラスタリング,主成分分析,レコメンデーションシステム,ハミルトンシミュレーションについて検討する。
我々は、スパース、ハイランク、良質な行列関連問題に対して、大きな量子スピードアップが存在することを発見した。
- 参考スコア(独自算出の注目度): 0.6138671548064356
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum-inspired classical algorithms provide us with a new way to understand
the computational power of quantum computers for practically-relevant problems,
especially in machine learning. In the past several years, numerous efficient
algorithms for various tasks have been found, while an analysis of lower bounds
is still missing. Using communication complexity, in this work we propose the
first method to study lower bounds for these tasks. We mainly focus on lower
bounds for solving linear regressions, supervised clustering, principal
component analysis, recommendation systems, and Hamiltonian simulations. More
precisely, we show that for linear regressions, in the row-sparse case, the
lower bound is quadratic in the Frobenius norm of the underlying matrix, which
is tight. In the dense case, with an extra assumption on the accuracy we obtain
that the lower bound is quartic in the Frobenius norm, which matches the upper
bound. For supervised clustering, we obtain a tight lower bound that is quartic
in the Frobenius norm. For the other three tasks, we obtain a lower bound that
is quadratic in the Frobenius norm, and the known upper bound is quartic in the
Frobenius norm. Through this research, we find that large quantum speedup can
exist for sparse, high-rank, well-conditioned matrix-related problems. Finally,
we extend our method to study lower bounds analysis of quantum query algorithms
for matrix-related problems. Some applications are given.
- Abstract(参考訳): 量子に触発された古典的アルゴリズムは、量子コンピュータの計算能力を理解する新しい方法を提供してくれます。
過去数年間、様々なタスクに対する多くの効率的なアルゴリズムが発見されているが、下位境界の解析はいまだに欠けている。
本研究は,コミュニケーションの複雑さを用いて,これらの課題の下位境界を研究するための最初の手法を提案する。
線形回帰,教師付きクラスタリング,主成分分析,レコメンデーションシステム,ハミルトニアンシミュレーションの解法として,下限に着目した。
より正確には、線形回帰について、行スパースの場合、下界は、基礎となる行列のフロベニウスノルムにおいて2次的であることを示す。
濃密な場合、その精度について余分な仮定をすれば、下界は上界と一致するフロベニウスノルムにおいて四角形であることが分かる。
教師付きクラスタリングでは、フロベニウスノルムにおいて四分の一の厳密な下界が得られる。
他の3つのタスクについて、フロベニウスノルムにおいて二次であり、既知の上界はフロベニウスノルムにおいて四進法である下界を得る。
本研究により, スパース, 高位, 条件のよい行列関連問題に対して, 大規模な量子スピードアップが存在することがわかった。
最後に,本手法を拡張し,行列問題に対する量子クエリアルゴリズムの下限解析を行う。
応用がいくつかある。
関連論文リスト
- An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning [14.955338558971787]
証明可能な指数的量子スピードアップは、線形系を解くためのセミナルHHL量子アルゴリズム以来、中心的な研究目標となっている。
量子と量子に着想を得た古典的アルゴリズム間で、このような証明可能な指数的分離を初めて提示する。
論文 参考訳(メタデータ) (2024-11-04T13:49:26Z) - On the quantum time complexity of divide and conquer [42.7410400783548]
量子分割の時間的複雑さと古典的問題に対するアルゴリズムの克服について検討する。
これらの定理を、弦、整数、幾何学的対象を含む一連の問題に適用する。
論文 参考訳(メタデータ) (2023-11-28T01:06:03Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳(メタデータ) (2023-10-04T17:53:55Z) - 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 communication complexity of linear regression [0.05076419064097732]
量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。
本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
論文 参考訳(メタデータ) (2022-10-04T13:27:01Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳(メタデータ) (2020-11-09T01:13:07Z) - Quantum Geometric Machine Learning for Quantum Circuits and Control [78.50747042819503]
我々は、量子幾何学的制御問題に対するディープラーニングの適用をレビューし、拡張する。
量子回路合成問題における時間-最適制御の強化について述べる。
我々の研究結果は、時間-最適制御問題に対する機械学習と幾何学的手法を組み合わせた量子制御と量子情報理論の研究者にとって興味深いものである。
論文 参考訳(メタデータ) (2020-06-19T19:12:14Z) - Towards quantum advantage via topological data analysis [0.0]
ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。
ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
論文 参考訳(メタデータ) (2020-05-06T06:31:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。