論文の概要: 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つのタスクについて、フロベニウスノルムにおいて二次であり、既知の上界はフロベニウスノルムにおいて四進法である下界を得る。
本研究により, スパース, 高位, 条件のよい行列関連問題に対して, 大規模な量子スピードアップが存在することがわかった。
最後に,本手法を拡張し,行列問題に対する量子クエリアルゴリズムの下限解析を行う。
応用がいくつかある。
関連論文リスト
- Quantum Algorithms for the Pathwise Lasso [1.9374282535132377]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
論文 参考訳(メタデータ) (2023-12-21T18:57:54Z) - Quantum Bayesian Optimization [64.58749619145908]
本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。
O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。
線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
論文 参考訳(メタデータ) (2023-10-09T03:10:42Z) - Robust Dequantization of the Quantum Singular value Transformation and
Quantum Machine Learning Algorithms [0.0]
この弱い仮定の下では、ランダム化線形代数の技法がどれだけ多く適用できるかを示す。
また、これらの結果を用いて、多くの量子機械学習アルゴリズムの頑健な復号化を行う。
論文 参考訳(メタデータ) (2023-04-11T02:09:13Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Unitary property testing lower bounds by polynomials [0.15229257192293197]
我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。
これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。
我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
論文 参考訳(メタデータ) (2022-10-12T03:01:00Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳(メタデータ) (2021-11-30T12:21:41Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳(メタデータ) (2020-11-09T01:13:07Z) - Finding high-order Hadamard matrices by using quantum computers [0.0]
H行列の古典的構成・探索手法を採用することにより、高次H行列を見つけるための新しい量子コンピューティング手法を開発することができることを示す。
特に、チューリンに基づく量子計算法は、任意に高次H行列を見つけるためにさらに発展することができる。
論文 参考訳(メタデータ) (2020-09-23T03:19:39Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。