論文の概要: An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning

• arxiv url: http://arxiv.org/abs/2411.02087v1
• Date: Mon, 04 Nov 2024 13:49:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 14:48:40.524804
• Title: An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning
• Title（参考訳）: 機械学習のための量子と量子にインスパイアされた古典的アルゴリズムの指数分離
• Authors: Allan Grønlund, Kasper Green Larsen,
• Abstract要約: 証明可能な指数的量子スピードアップは、線形系を解くためのセミナルHHL量子アルゴリズム以来、中心的な研究目標となっている。 量子と量子に着想を得た古典的アルゴリズム間で、このような証明可能な指数的分離を初めて提示する。
• 参考スコア（独自算出の注目度）: 14.955338558971787
• License:
• Abstract: Achieving a provable exponential quantum speedup for an important machine learning task has been a central research goal since the seminal HHL quantum algorithm for solving linear systems and the subsequent quantum recommender systems algorithm by Kerenidis and Prakash. These algorithms were initially believed to be strong candidates for exponential speedups, but a lower bound ruling out similar classical improvements remained absent. In breakthrough work by Tang, it was demonstrated that this lack of progress in classical lower bounds was for good reasons. Concretely, she gave a classical counterpart of the quantum recommender systems algorithm, reducing the quantum advantage to a mere polynomial. Her approach is quite general and was named quantum-inspired classical algorithms. Since then, almost all the initially exponential quantum machine learning speedups have been reduced to polynomial via new quantum-inspired classical algorithms. From the current state-of-affairs, it is unclear whether we can hope for exponential quantum speedups for any natural machine learning task. In this work, we present the first such provable exponential separation between quantum and quantum-inspired classical algorithms. We prove the separation for the basic problem of solving a linear system when the input matrix is well-conditioned and has sparse rows and columns.
• Abstract（参考訳）: 重要な機械学習タスクのための証明可能な指数的量子スピードアップを実現することは、線形系を解くためのセミナルHHL量子アルゴリズムと、KerenidisとPrakashによるその後の量子レコメンダ・システムアルゴリズム以来、中心的な研究目標となっている。 これらのアルゴリズムは、当初は指数的スピードアップの強い候補と考えられていたが、古典的な改善を除外する下位境界は存在しなかった。 唐の画期的な研究において、古典的な下界の進歩の欠如が良い理由であったことが証明された。 具体的には、彼女は量子レコメンデータシステムアルゴリズムの古典的なものを与え、単なる多項式に対する量子上の優位性を減らした。 彼女のアプローチは非常に一般的で、量子にインスパイアされた古典的アルゴリズムと名付けられた。 それ以来、初期の指数関数的量子機械学習のスピードアップは、新しい量子に着想を得た古典的アルゴリズムによって多項式に減らされてきた。 現在の状況からすると、どんな自然な機械学習タスクでも指数的な量子スピードアップを期待できるかどうかは不明だ。 本研究では、量子と量子に着想を得た古典的アルゴリズムの間で、このような証明可能な指数的分離を初めて提示する。 入力行列が十分に条件付きであり、スパース列と列を持つ場合、線形系を解くための基本的な問題の分離を証明した。

関連論文リスト

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか? 我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。 我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Quantum Machine Learning: Quantum Kernel Methods [0.0]
  カーネルメソッドは古典的な機械学習において強力で一般的なテクニックである。 量子コンピュータ上でしか効率的に計算できない量子特徴空間を使用することで、量子上の優位性を導出することができる。 データ依存型投影量子カーネルは、古典的カーネルに対して大きな利点をもたらすことが示されている。
  論文  参考訳（メタデータ） (2024-05-02T23:45:29Z)
• Expressive Quantum Supervised Machine Learning using Kerr-nonlinear Parametric Oscillators [0.0]
  変分量子アルゴリズム(VQA)を用いた量子機械学習は、ノイズのある中間スケール量子(NISQ)時代の実用的なアルゴリズムとして積極的に研究されている。 近年の研究では、古典的なデータを量子回路に繰り返しエンコードするデータ再アップロードが、表現力のある量子機械学習モデルを得るために必要であることが示されている。 我々は、Kerrnon Parametric Hilberts (KPO) を別の有望な量子コンピューティングデバイスとして用いて量子機械学習を提案する。
  論文  参考訳（メタデータ） (2023-05-01T07:01:45Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Quantum-Enhanced Greedy Combinatorial Optimization Solver [12.454028945013924]
  最適化問題を解くために反復量子最適化アルゴリズムを導入する。 72量子ビット以下のプログラム可能な超伝導量子系に量子アルゴリズムを実装した。 量子アルゴリズムは古典的な欲求よりも体系的に優れており、量子エンハンスメントのシグナルとなる。
  論文  参考訳（メタデータ） (2023-03-09T18:59:37Z)
• Quantum Machine Learning: from physics to software engineering [58.720142291102135]
  古典的な機械学習アプローチが量子コンピュータの設備改善にどのように役立つかを示す。 量子アルゴリズムと量子コンピュータは、古典的な機械学習タスクを解くのにどのように役立つかについて議論する。
  論文  参考訳（メタデータ） (2023-01-04T23:37:45Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
  想像時間における進化は、量子多体系の基底状態を見つけるための顕著な技術である。 本稿では,量子コンピュータ上での仮想時間伝搬を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-24T12:48:00Z)
• A rigorous and robust quantum speed-up in supervised machine learning [6.402634424631123]
  本稿では,汎用量子学習アルゴリズムを用いて,教師付き分類のための厳密な量子スピードアップを確立する。 我々の量子分類器は、フォールトトレラント量子コンピュータを用いてカーネル関数を推定する従来のサポートベクトルマシンである。
  論文  参考訳（メタデータ） (2020-10-05T17:22:22Z)
• Towards quantum advantage via topological data analysis [0.0]
  ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。 ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-05-06T06:31:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。