論文の概要: 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)によるスパース行列の分位化フレームワークが、入力への近似長二乗サンプリングアクセスの場合に一般化可能であることを示す。
また、これらの結果を用いて、推薦システムのための量子アルゴリズム、教師付きクラスタリング、低ランク行列反転を含む、多くの量子機械学習アルゴリズムのロバストな非量子化を得る。
関連論文リスト
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Evaluation of phase shifts for non-relativistic elastic scattering using quantum computers [39.58317527488534]
本研究は, 量子コンピュータ上での一般相対論的非弾性散乱過程の位相シフトを求めるアルゴリズムの開発を報告する。
論文 参考訳（メタデータ） (2024-07-04T21:11:05Z) - The Algorithm for Solving Quantum Linear Systems of Equations With Coherent Superposition and Its Extended Applications [8.8400072344375]
コヒーレント重ね合わせを持つ方程式の量子線型系を解くための2つの量子アルゴリズムを提案する。
2つの量子アルゴリズムは、ランクと一般解の両方を1つの測定で計算できる。
分析の結果,提案アルゴリズムは主に軽量対称暗号に対する攻撃に適していることがわかった。
論文 参考訳（メタデータ） (2024-05-11T03:03:14Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。