論文の概要: Robust Dequantization of the Quantum Singular value Transformation and
Quantum Machine Learning Algorithms
- arxiv url: http://arxiv.org/abs/2304.04932v1
- Date: Tue, 11 Apr 2023 02:09:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-12 16:27:18.232801
- Title: Robust Dequantization of the Quantum Singular value Transformation and
Quantum Machine Learning Algorithms
- Title(参考訳): 量子特異値変換と量子機械学習アルゴリズムのロバスト量子化
- Authors: Fran\c{c}ois Le Gall
- Abstract要約: この弱い仮定の下では、ランダム化線形代数の技法がどれだけ多く適用できるかを示す。
また、これらの結果を用いて、多くの量子機械学習アルゴリズムの頑健な復号化を行う。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Several quantum algorithms for linear algebra problems, and in particular
quantum machine learning problems, have been "dequantized" in the past few
years. These dequantization results typically hold when classical algorithms
can access the data via length-squared sampling. In this work we investigate
how robust these dequantization results are. We introduce the notion of
approximate length-squared sampling, where classical algorithms are only able
to sample from a distribution close to the ideal distribution in total
variation distance. While quantum algorithms are natively robust against small
perturbations, current techniques in dequantization are not. Our main technical
contribution is showing how many techniques from randomized linear algebra can
be adapted to work under this weaker assumption as well. We then use these
techniques to show that the recent low-rank dequantization framework by Chia,
Gily\'en, Li, Lin, Tang and Wang (JACM 2022) and the dequantization framework
for sparse matrices by Gharibian and Le Gall (STOC 2022), which are both based
on the Quantum Singular Value Transformation, can be generalized to the case of
approximate length-squared sampling access to the input. We also apply these
results to obtain a robust dequantization of many quantum machine learning
algorithms, including quantum algorithms for recommendation systems, supervised
clustering and low-rank matrix inversion.
- Abstract(参考訳): 線形代数問題、特に量子機械学習問題に対するいくつかの量子アルゴリズムは、ここ数年で「不等化」されてきた。
これらの重複化の結果は、古典的なアルゴリズムが長さ2乗サンプリングによってデータにアクセスできることが典型的である。
本研究では,これらの分散化結果がいかに堅牢かを検討する。
本稿では,古典的アルゴリズムが全変動距離における理想分布に近い分布からのみサンプリングできるような,近似長2乗サンプリングの概念を導入する。
量子アルゴリズムは小さな摂動に対して本質的に堅牢であるが、復調の現在の技術はそうではない。
我々の主要な技術的貢献は、ランダム化された線型代数の技法が、この弱い仮定の下でどのように機能するかを示すことです。
次に、これらの手法を用いて、近年のChia, Gily\'en, Li, Lin, Tang and Wang (JACM 2022)による低ランク化フレームワークと、量子特異値変換に基づくGharibian and Le Gall (STOC 2022)によるスパース行列の分位化フレームワークが、入力への近似長二乗サンプリングアクセスの場合に一般化可能であることを示す。
また、これらの結果を用いて、推薦システムのための量子アルゴリズム、教師付きクラスタリング、低ランク行列反転を含む、多くの量子機械学習アルゴリズムのロバストな非量子化を得る。
関連論文リスト
- 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) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Quantum algorithms for grid-based variational time evolution [36.136619420474766]
本稿では,第1量子化における量子力学の実行のための変分量子アルゴリズムを提案する。
シミュレーションでは,従来観測されていた変動時間伝播手法の数値不安定性を示す。
論文 参考訳(メタデータ) (2022-03-04T19:00:45Z) - Variational Quantum Linear Solver with Dynamic Ansatz [0.0]
変分量子アルゴリズムは、そのハイブリッド量子古典的アプローチにより、NISQ時代に成功している。
線形代数方程式系に対する変分量子線形解法に動的アンサッツを導入する。
より少ない量子資源を利用することで、標準の静的アンサッツと比較してアルゴリズムの優位性を実証する。
論文 参考訳(メタデータ) (2021-07-19T03:42:25Z) - A Grand Unification of Quantum Algorithms [0.0]
最近、多くの量子アルゴリズムが量子特異値変換(quantum singular value transformation)と呼ばれる手法で結合された。
本稿では,まず量子信号処理を量子固有値変換に一般化する方法について解説する。
次に、QSVTを用いて、探索、位相推定、ハミルトニアンシミュレーションのための直感的な量子アルゴリズムを構築する。
論文 参考訳(メタデータ) (2021-05-06T17:46:33Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳(メタデータ) (2020-11-09T01:13:07Z) - Towards quantum advantage via topological data analysis [0.0]
ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。
ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
論文 参考訳(メタデータ) (2020-05-06T06:31:24Z) - Sampling-based sublinear low-rank matrix arithmetic framework for
dequantizing quantum machine learning [7.356328937024184]
近接-低階行列上の量子インスピレーション付き古典アルゴリズムのアルゴリズムフレームワークを提案する。
量子線型代数アルゴリズムと量子特異値変換フレームワークに動機付け,入力次元に依存しない時間で動作するSVTの古典的アルゴリズムを開発した。
この結果から,対応するQRAMデータ構造入力モデルでは,量子SVTが指数的な量子スピードアップを生じないことを示す。
論文 参考訳(メタデータ) (2019-10-14T14:04:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。