論文の概要: Quadratic Quantum Speedup for Perceptron Training
- arxiv url: http://arxiv.org/abs/2109.04695v1
- Date: Fri, 10 Sep 2021 06:50:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-15 11:55:49.395483
- Title: Quadratic Quantum Speedup for Perceptron Training
- Title（参考訳）: パーセプトロントレーニングのための擬似量子スピードアップ
- Authors: Pengcheng Liao, Barry C. Sanders, Tim Byrnes
- Abstract要約: バイナリ分類を行うパーセプトロンは、ニューラルネットワークの基本的な構成要素である。
パーセプトロンのためのオラクルを構築するためのクエリの複雑さは、古典的手法よりも2次的に改善されていることを示す。
我々のアルゴリズムはニューラルネットワークのようなより複雑な機械学習モデルを訓練するために一般化することができる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Perceptrons, which perform binary classification, are the fundamental
building blocks of neural networks. Given a data set of size~$N$ and
margin~$\gamma$ (how well the given data are separated), the query complexity
of the best-known quantum training algorithm scales as either
$(\nicefrac{\sqrt{N}}{\gamma^2})\log(\nicefrac1{\gamma^2)}$ or
$\nicefrac{N}{\sqrt{\gamma}}$, which is achieved by a hybrid of classical and
quantum search. In this paper, we improve the version space quantum training
method for perceptrons such that the query complexity of our algorithm scales
as $\sqrt{\nicefrac{N}{\gamma}}$. This is achieved by constructing an oracle
for the perceptrons using quantum counting of the number of data elements that
are correctly classified. We show that query complexity to construct such an
oracle has a quadratic improvement over classical methods. Once such an oracle
is constructed, bounded-error quantum search can be used to search over the
hyperplane instances. The optimality of our algorithm is proven by reducing the
evaluation of a two-level AND-OR tree (for which the query complexity lower
bound is known) to a multi-criterion search. Our quantum training algorithm can
be generalized to train more complex machine learning models such as neural
networks, which are built on a large number of perceptrons.
- Abstract（参考訳）: バイナリ分類を行うパーセプトロンは、ニューラルネットワークの基本的な構成要素である。
大きさのデータセット~$N$ and margin~$\gamma$(与えられたデータがどの程度分離されているか)が与えられたとき、最もよく知られている量子トレーニングアルゴリズムのクエリ複雑性は$(\nicefrac{\sqrt{N}}{\gamma^2})\log(\nicefrac1{\gamma^2)}$または$\nicefrac{N}{\sqrt{\gamma}}$としてスケールする。
本稿では,パーセプトロンに対するバージョン空間量子トレーニング法を改良し,アルゴリズムのクエリ複雑性を$\sqrt{\nicefrac{n}{\gamma}}$に拡張する。
これは、正しく分類されたデータ要素の数の量子カウントを使用して、パーセプトロンのためのオラクルを構築することで達成される。
このようなオラクルを構築するためのクエリの複雑さは、古典的手法よりも2次的に改善されていることを示す。
そのようなオラクルが構築されると、境界付きエラー量子検索を使用してハイパープレーンインスタンスを検索できる。
本アルゴリズムの最適性は,クエリの複雑さが低い2段階のAND-ORツリーの評価をマルチ基準探索に還元することで証明される。
我々の量子トレーニングアルゴリズムは、多数のパーセプトロン上に構築されたニューラルネットワークのような、より複雑な機械学習モデルをトレーニングするために一般化することができる。
関連論文リスト
- Non-Linear Transformations of Quantum Amplitudes: Exponential
Improvement, Generalization, and Applications [0.0]
量子アルゴリズムは量子状態の振幅を操作して計算問題の解を求める。
量子状態の振幅に非線形関数の一般クラスを適用するための枠組みを提案する。
我々の研究は、最適化、状態準備、量子化学、機械学習といった分野において、潜在的に多くの応用が可能な重要かつ効率的なビルディングブロックを提供する。
論文 参考訳（メタデータ） (2023-09-18T14:57:21Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳（メタデータ） (2023-04-06T02:18:52Z) - Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
本稿では,行列関数からのサンプリング作業のためのランダム化量子アルゴリズムのクラスを提案する。
量子ビットの使用は純粋にアルゴリズムであり、量子データ構造には追加の量子ビットは必要ない。
論文 参考訳（メタデータ） (2023-02-03T17:22:49Z) - 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) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Quantum Sparse Coding [5.130440339897477]
我々はスパース符号化のための量子インスピレーション付きアルゴリズムを開発した。
量子コンピュータとイジングマシンの出現は、より正確な推定につながる可能性がある。
我々はLightrの量子インスパイアされたデジタルプラットフォーム上でシミュレーションデータを用いて数値実験を行う。
論文 参考訳（メタデータ） (2022-09-08T13:00:30Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
勾配勾配勾配による古典的トレーサビリティに寄与する条件は、量子線形系を効率的に解くために必要な条件と一致することを示す。
MNIST画像データセットがそのような条件を満たすことを数値的に示す。
我々は、プールを用いた畳み込みニューラルネットワークのトレーニングに$O(log n)$の実証的証拠を提供する。
論文 参考訳（メタデータ） (2021-07-19T23:41:03Z) - Quantum algorithms for learning a hidden graph and beyond [0.05076419064097732]
本稿では、量子アルゴリズムを用いて、託宣によって提供された未知のグラフを学習する問題について研究する。
ORおよびパリティクエリモデルにおいて、最も優れた古典的アルゴリズムの高速化を実現する量子アルゴリズムを提供する。
さらに、グループテスト問題の"ガッペ"バージョンに対して、Ambainisらのアルゴリズムに基づいて、この問題に対する時間効率の量子アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-11-17T13:12:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。