論文の概要: Sampling-based sublinear low-rank matrix arithmetic framework for
dequantizing quantum machine learning
- arxiv url: http://arxiv.org/abs/1910.06151v4
- Date: Mon, 10 Jul 2023 19:49:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-13 20:55:15.313465
- Title: Sampling-based sublinear low-rank matrix arithmetic framework for
dequantizing quantum machine learning
- Title（参考訳）: 量子機械学習のためのサンプリングベースサブ線形低ランク行列演算フレームワーク
- Authors: Nai-Hui Chia, Andr\'as Gily\'en, Tongyang Li, Han-Hsuan Lin, Ewin
Tang, Chunhao Wang
- Abstract要約: 近接-低階行列上の量子インスピレーション付き古典アルゴリズムのアルゴリズムフレームワークを提案する。
量子線型代数アルゴリズムと量子特異値変換フレームワークに動機付け,入力次元に依存しない時間で動作するSVTの古典的アルゴリズムを開発した。
この結果から,対応するQRAMデータ構造入力モデルでは,量子SVTが指数的な量子スピードアップを生じないことを示す。
- 参考スコア（独自算出の注目度）: 7.356328937024184
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present an algorithmic framework for quantum-inspired classical algorithms
on close-to-low-rank matrices, generalizing the series of results started by
Tang's breakthrough quantum-inspired algorithm for recommendation systems
[STOC'19]. Motivated by quantum linear algebra algorithms and the quantum
singular value transformation (SVT) framework of Gily\'en, Su, Low, and Wiebe
[STOC'19], we develop classical algorithms for SVT that run in time independent
of input dimension, under suitable quantum-inspired sampling assumptions. Our
results give compelling evidence that in the corresponding QRAM data structure
input model, quantum SVT does not yield exponential quantum speedups. Since the
quantum SVT framework generalizes essentially all known techniques for quantum
linear algebra, our results, combined with sampling lemmas from previous work,
suffice to generalize all recent results about dequantizing quantum machine
learning algorithms. In particular, our classical SVT framework recovers and
often improves the dequantization results on recommendation systems, principal
component analysis, supervised clustering, support vector machines, low-rank
regression, and semidefinite program solving. We also give additional
dequantization results on low-rank Hamiltonian simulation and discriminant
analysis. Our improvements come from identifying the key feature of the
quantum-inspired input model that is at the core of all prior quantum-inspired
results: $\ell^2$-norm sampling can approximate matrix products in time
independent of their dimension. We reduce all our main results to this fact,
making our exposition concise, self-contained, and intuitive.
- Abstract（参考訳）: 本稿では,Tang's Breaking quantum-inspired algorithm for recommendation system[STOC'19]から始まる一連の結果を一般化した,近接-低階行列上の量子インスパイア古典アルゴリズムのアルゴリズムフレームワークを提案する。
量子線形代数アルゴリズムとgily\'en,su,low,wiebe [stoc'19]の量子特異値変換(svt)フレームワークに動機付けられ,入力次元に依存しない時間内で動作するsvtの古典的なアルゴリズムを開発した。
この結果から,対応するQRAMデータ構造入力モデルでは,量子SVTが指数的な量子スピードアップを生じないことを示す。
量子svtフレームワークは、本質的にすべての既知の量子線形代数のテクニックを一般化しているため、これまでの研究から抽出された補題を組み合わせることで、量子機械学習アルゴリズムの非量子化に関する最近の結果をすべて一般化することができる。
特に,従来のSVTフレームワークでは,リコメンデーションシステム,主成分分析,クラスタリング,サポートベクタマシン,低ランク回帰,半定値プログラム問題解決などにおいて,復号化結果を回復し,しばしば改善する。
また,低位ハミルトンシミュレーションと判別分析において,さらに定量化結果を与える。
我々の改良は、以前の全ての量子インスパイアされた結果の中核である量子インスパイアされた入力モデルの鍵となる特徴を同定することによる:$\ell^2$-norm サンプリングは、その次元に依存しない時間で行列積を近似することができる。
私たちはこの事実に対する主要な結果をすべて削減し、展示を簡潔で、自己完結的で、直感的にします。
関連論文リスト
- Fourier Neural Operators for Learning Dynamics in Quantum Spin Systems [77.88054335119074]
ランダム量子スピン系の進化をモデル化するためにFNOを用いる。
量子波動関数全体の2n$の代わりに、コンパクトなハミルトン観測可能集合にFNOを適用する。
論文 参考訳（メタデータ） (2024-09-05T07:18:09Z) - Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Robust Dequantization of the Quantum Singular value Transformation and
Quantum Machine Learning Algorithms [0.0]
この弱い仮定の下では、ランダム化線形代数の技法がどれだけ多く適用できるかを示す。
また、これらの結果を用いて、多くの量子機械学習アルゴリズムの頑健な復号化を行う。
論文 参考訳（メタデータ） (2023-04-11T02:09:13Z) - The Quantum Path Kernel: a Generalized Quantum Neural Tangent Kernel for
Deep Quantum Machine Learning [52.77024349608834]
古典的なディープニューラルネットワークの量子アナログを構築することは、量子コンピューティングにおける根本的な課題である。
鍵となる問題は、古典的なディープラーニングの本質的な非線形性にどのように対処するかである。
我々は、深層機械学習のこれらの側面を複製できる量子機械学習の定式化であるQuantum Path Kernelを紹介する。
論文 参考訳（メタデータ） (2022-12-22T16:06:24Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Provably efficient variational generative modeling of quantum many-body
systems via quantum-probabilistic information geometry [3.5097082077065003]
パラメータ化混合状態に対する量子自然勾配降下の一般化を導入する。
また、堅牢な一階近似アルゴリズム、Quantum-Probabilistic Mirror Descentを提供する。
我々のアプローチは、モデル選択における柔軟性を実現するために、それまでのサンプル効率の手法を拡張しました。
論文 参考訳（メタデータ） (2022-06-09T17:58:15Z) - Dequantizing the Quantum Singular Value Transformation: Hardness and
Applications to Quantum Chemistry and the Quantum PCP Conjecture [0.0]
量子特異値変換は効率的に「等化」できることを示す。
逆多項式精度では、同じ問題がBQP完全となることを示す。
また、この分位化手法が中心量子PCPの進展にどう役立つかについても論じる。
論文 参考訳（メタデータ） (2021-11-17T12:50:13Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。
変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。
量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
論文 参考訳（メタデータ） (2021-08-09T18:00:05Z) - A Grand Unification of Quantum Algorithms [0.0]
最近、多くの量子アルゴリズムが量子特異値変換(quantum singular value transformation)と呼ばれる手法で結合された。
本稿では,まず量子信号処理を量子固有値変換に一般化する方法について解説する。
次に、QSVTを用いて、探索、位相推定、ハミルトニアンシミュレーションのための直感的な量子アルゴリズムを構築する。
論文 参考訳（メタデータ） (2021-05-06T17:46:33Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。
一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。
幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
論文 参考訳（メタデータ） (2021-04-01T19:06:00Z) - Towards quantum advantage via topological data analysis [0.0]
ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。
ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-05-06T06:31:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。