論文の概要: On Quantum Perceptron Learning via Quantum Search
- arxiv url: http://arxiv.org/abs/2503.17308v1
- Date: Fri, 21 Mar 2025 16:57:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-24 15:40:10.544205
- Title: On Quantum Perceptron Learning via Quantum Search
- Title（参考訳）: 量子探索による量子パーセプトロン学習について
- Authors: Xiaoyu Sun, Mathieu Roget, Giuseppe Di Molfetta, Hachem Kadri,
- Abstract要約: D$次元超平面の正規分布からサンプリングされる確率は、$Theta(gamma)$の代わりに$Omega(gammaD)$と完全に分類できることが示される。
量子探索アルゴリズムを用いて、知覚論的学習の全体的な複雑さを高める方法を示す。
- 参考スコア（独自算出の注目度）: 5.172382862031037
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: With the growing interest in quantum machine learning, the perceptron -- a fundamental building block in traditional machine learning -- has emerged as a valuable model for exploring quantum advantages. Two quantum perceptron algorithms based on Grover's search, were developed in arXiv:1602.04799 to accelerate training and improve statistical efficiency in perceptron learning. This paper points out and corrects a mistake in the proof of Theorem 2 in arXiv:1602.04799. Specifically, we show that the probability of sampling from a normal distribution for a $D$-dimensional hyperplane that perfectly classifies the data scales as $\Omega(\gamma^{D})$ instead of $\Theta({\gamma})$, where $\gamma$ is the margin. We then revisit two well-established linear programming algorithms -- the ellipsoid method and the cutting plane random walk algorithm -- in the context of perceptron learning, and show how quantum search algorithms can be leveraged to enhance the overall complexity. Specifically, both algorithms gain a sub-linear speed-up $O(\sqrt{N})$ in the number of data points $N$ as a result of Grover's algorithm and an additional $O(D^{1.5})$ speed-up is possible for cutting plane random walk algorithm employing quantum walk search.
- Abstract（参考訳）: 量子機械学習への関心が高まり、従来の機械学習の基本的な構成要素であるパーセプトロンが、量子アドバンテージを探求するための貴重なモデルとして登場した。
Groverの探索に基づく2つの量子パーセプトロンアルゴリズムがarXiv:1602.04799で開発された。
本稿では,arXiv:1602.04799における定理2の証明における誤りを指摘する。
具体的には、データスケールを$\Omega(\gamma^{D})$、$\Theta({\gamma})$ではなく$\Omega(\gamma^{D})$と完全に分類する$D$次元超平面の正規分布からサンプリングする確率を示す。
次に、知覚学習の文脈において、よく確立された2つの線形プログラミングアルゴリズム(楕円体法と切断平面ランダムウォーク法)を再検討し、量子探索アルゴリズムをどのように活用して全体的な複雑さを高めるかを示す。
具体的には、Groverのアルゴリズムの結果としてデータポイント数$N$のサブ線形スピードアップ$O(\sqrt{N})$と、追加の$O(D^{1.5})$のスピードアップが、量子ウォーク探索を用いた平面ランダムウォークアルゴリズムの切断に有効である。
関連論文リスト
- Arbitrary state creation via controlled measurement [49.494595696663524]
このアルゴリズムは任意の$n$-qubit純量子重ね合わせ状態を生成し、精度は$m$-decimalsである。
このアルゴリズムは、1キュービット回転、アダマール変換、マルチキュービット制御によるC-NOT演算を使用する。
論文 参考訳（メタデータ） (2025-04-13T07:23:50Z) - Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
線形微分方程式に対する量子アルゴリズムを提案する。
アルゴリズムのゲートの複雑さは、次元に依存する$mathcalO(dlog(Nd))$を示す。
アルゴリズムはOrnstein-Uhlenbeck過程、ブラウン運動、L'evy飛行に対して数値的に検証される。
論文 参考訳（メタデータ） (2024-12-19T14:04:11Z) - A Novel Quantum-Classical Hybrid Algorithm for Determining Eigenstate Energies in Quantum Systems [1.9714447272714082]
本稿では、任意の量子系の固有エネルギースペクトルを効率的に計算するための新しい量子アルゴリズムXZ24を提案する。
XZ24には3つの大きな利点がある: 固有状態の準備の必要性を排除し、無視できない重複を持つ参照状態のみを必要とする。
参照状態に応じて複数の固有エネルギーの同時計算を可能にする。
論文 参考訳（メタデータ） (2024-06-01T04:31:43Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
本稿では,ニュートンのGDを用いたニューラルネットワークトレーニングの高速化を目的とした,ハイブリッド量子古典スケジューラQ-Newtonを提案する。
Q-Newtonは量子と古典的な線形解法を協調する合理化スケジューリングモジュールを使用している。
評価の結果,Q-Newtonは一般的な量子機械と比較してトレーニング時間を大幅に短縮できる可能性が示された。
論文 参考訳（メタデータ） (2024-04-30T23:55:03Z) - A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。
このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。
また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
論文 参考訳（メタデータ） (2023-11-07T22:52:56Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games [10.79781442303645]
ゼロサムゲームを解くための最初のオンライン量子アルゴリズムを提案する。
我々のアルゴリズムは簡潔な記述を伴う古典的な出力を生成する。
我々のアルゴリズムの核心は、ギブスサンプリング問題に対する高速な量子マルチサンプリング手法である。
論文 参考訳（メタデータ） (2023-04-27T14:02:54Z) - Learning to predict arbitrary quantum processes [7.69390398476646]
我々は、未知の量子過程を$n$ qubitsで予測するための効率的な機械学習(ML)アルゴリズムを提案する。
本結果は,複雑な量子力学の出力を,プロセス自体の実行時間よりもはるかに高速に予測するMLモデルの可能性を強調した。
論文 参考訳（メタデータ） (2022-10-26T17:52:59Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Quadratic Quantum Speedup for Perceptron Training [0.0]
バイナリ分類を行うパーセプトロンは、ニューラルネットワークの基本的な構成要素である。
パーセプトロンのためのオラクルを構築するためのクエリの複雑さは、古典的手法よりも2次的に改善されていることを示す。
我々のアルゴリズムはニューラルネットワークのようなより複雑な機械学習モデルを訓練するために一般化することができる。
論文 参考訳（メタデータ） (2021-09-10T06:50:57Z) - A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
勾配勾配勾配による古典的トレーサビリティに寄与する条件は、量子線形系を効率的に解くために必要な条件と一致することを示す。
MNIST画像データセットがそのような条件を満たすことを数値的に示す。
我々は、プールを用いた畳み込みニューラルネットワークのトレーニングに$O(log n)$の実証的証拠を提供する。
論文 参考訳（メタデータ） (2021-07-19T23:41:03Z) - Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor
Network States Algorithm [0.0]
アルゴリズムはSch$ddottexto$dinger-Feynmanアルゴリズムよりも2ドル高速である。
このアルゴリズムは, 量子コンピュータ上での比較的浅い量子回路の検証に最適であることを示す。
論文 参考訳（メタデータ） (2020-11-05T02:20:56Z) - Quantum Spectral Clustering [5.414308305392762]
スペクトルクラスタリングは、非凸構造やネスト構造でデータをクラスタリングするための強力な機械学習アルゴリズムである。
本稿では,エンドツーエンドの量子アルゴリズムのスペクトルクラスタリングを提案し,量子機械学習における多くの研究を拡張した。
論文 参考訳（メタデータ） (2020-07-01T07:11:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。