論文の概要: The complexity of quantum support vector machines
- arxiv url: http://arxiv.org/abs/2203.00031v2
- Date: Sun, 7 Jan 2024 19:12:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-10 00:59:38.224681
- Title: The complexity of quantum support vector machines
- Title（参考訳）: 量子サポートベクトルマシンの複雑さ
- Authors: Gian Gentinetta, Arne Thomsen, David Sutter, Stefan Woerner
- Abstract要約: 量子サポートベクトルマシンは、カーネル関数を定義するために量子回路を使用する。
二重問題は$O(M4.67/varepsilon2)$量子回路評価で解けることを示す。
- 参考スコア（独自算出の注目度）: 1.7887848708497243
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum support vector machines employ quantum circuits to define the kernel
function. It has been shown that this approach offers a provable exponential
speedup compared to any known classical algorithm for certain data sets. The
training of such models corresponds to solving a convex optimization problem
either via its primal or dual formulation. Due to the probabilistic nature of
quantum mechanics, the training algorithms are affected by statistical
uncertainty, which has a major impact on their complexity. We show that the
dual problem can be solved in $O(M^{4.67}/\varepsilon^2)$ quantum circuit
evaluations, where $M$ denotes the size of the data set and $\varepsilon$ the
solution accuracy compared to the ideal result from exact expectation values,
which is only obtainable in theory. We prove under an empirically motivated
assumption that the kernelized primal problem can alternatively be solved in
$O(\min \{ M^2/\varepsilon^6, \, 1/\varepsilon^{10} \})$ evaluations by
employing a generalization of a known classical algorithm called Pegasos.
Accompanying empirical results demonstrate these analytical complexities to be
essentially tight. In addition, we investigate a variational approximation to
quantum support vector machines and show that their heuristic training achieves
considerably better scaling in our experiments.
- Abstract（参考訳）: 量子サポートベクターマシンは、カーネル関数を定義するために量子回路を用いる。
このアプローチは、特定のデータセットに対する既知の古典的アルゴリズムと比較して、証明可能な指数的スピードアップを提供する。
そのようなモデルのトレーニングは、原始的あるいは双対な定式化を通じて凸最適化問題を解決することに対応する。
量子力学の確率論的性質のため、トレーニングアルゴリズムは統計的不確実性の影響を受け、その複雑さに大きな影響を及ぼす。
双対問題は、データセットのサイズを表す$o(m^{4.67}/\varepsilon^2)$の量子回路評価で解くことができ、ここでは$m$は、理論上しか得られない正確な期待値による理想的な結果に比べて解の精度が$\varepsilon$である。
経験的動機づけにより、核化された原始問題は、ペガソスと呼ばれる既知の古典的アルゴリズムの一般化を用いて、$o(\min \{ m^2/\varepsilon^6, \, 1/\varepsilon^{10} \})$評価で代替的に解くことができると証明する。
経験的な結果と合わせて、これらの解析的複雑さは本質的に密であることを示す。
さらに,量子サポートベクトルマシンの変分近似について検討し,そのヒューリスティックトレーニングが実験においてかなり優れたスケーリングを実現することを示す。
関連論文リスト
- Addressing the Readout Problem in Quantum Differential Equation Algorithms with Quantum Scientific Machine Learning [14.379311972506791]
正確な量子状態の読み出しは、トモグラフィーの複雑さによってボトルネックとなる。
量子微分方程式の出力を量子データとして扱い、低次元の出力を抽出できることを実証する。
この量子科学機械学習手法を用いて衝撃波の検出と乱流モデリングの解を分類する。
論文 参考訳（メタデータ） (2024-11-21T16:09:08Z) - Improved quantum algorithm for calculating eigenvalues of differential operators and its application to estimating the decay rate of the perturbation distribution tail in stochastic inflation [0.0]
微分作用素 $mathcalL$ の最初の固有値を $mathbbRd$ 上で推定する量子アルゴリズムを提案する。
次に、量子インフレーション(quantum inflation)として知られる宇宙のインフレーションの理論的枠組みにおける問題への我々の方法の適用について考察する。
論文 参考訳（メタデータ） (2024-10-03T07:56:20Z) - Benchmarking of quantum fidelity kernels for Gaussian process regression [1.7287035469433212]
量子コンピューティングアルゴリズムは、機械学習の分類問題に対して性能の高い量子カーネルを生成することが示されている。
量子カーネルは、回帰問題に対して古典的カーネルと同じ表現性が得られるが、あまり良くない。
論文 参考訳（メタデータ） (2024-07-22T18:19:48Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Dense outputs from quantum simulations [5.295277584890625]
量子密度出力問題は、時間依存の量子力学から時間累積観測値を評価する過程である。
この問題は量子制御や分光計算などの応用で頻繁に発生する。
我々は、早期および完全フォールトトレラントな量子プラットフォームの両方で動作するように設計されたアルゴリズムを提示する。
論文 参考訳（メタデータ） (2023-07-26T18:16:51Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳（メタデータ） (2023-04-12T18:10:47Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Validation tests of GBS quantum computers give evidence for quantum
advantage with a decoherent target [62.997667081978825]
複数モードデータの検証に指紋としてグループカウント確率の正P位相空間シミュレーションを用いる。
偽データを解き放つ方法を示し、これを古典的なカウントアルゴリズムに適用する。
論文 参考訳（メタデータ） (2022-11-07T12:00:45Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Estimating Gibbs partition function with quantumClifford sampling [6.656454497798153]
分割関数を推定するハイブリッド量子古典アルゴリズムを開発した。
我々のアルゴリズムは浅い$mathcalO(1)$-depth量子回路を必要とする。
浅層量子回路は、現在利用可能なNISQ(ノイズ中間スケール量子)デバイスにとって極めて重要であると考えられている。
論文 参考訳（メタデータ） (2021-09-22T02:03:35Z) - Preparation of excited states for nuclear dynamics on a quantum computer [117.44028458220427]
量子コンピュータ上で励起状態を作成するための2つの異なる方法を研究する。
シミュレーションおよび実量子デバイス上でこれらの手法をベンチマークする。
これらの結果から,フォールトトレラントデバイスに優れたスケーリングを実現するために設計された量子技術が,接続性やゲート忠実性に制限されたデバイスに実用的なメリットをもたらす可能性が示唆された。
論文 参考訳（メタデータ） (2020-09-28T17:21:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。