論文の概要: Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm
- arxiv url: http://arxiv.org/abs/2605.13979v1
- Date: Wed, 13 May 2026 18:00:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-15 21:45:34.44109
- Title: Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm
- Title（参考訳）: 量子インスパイアされた古典的アルゴリズムによるニューラルネットワークにおけるロッキーティケットの獲得
- Authors: Natsuto Isogai, Hayata Yamasaki, Sho Sonoda, Mio Murao,
- Abstract要約: 我々は、同じサンプリングタスクに対して量子に着想を得た完全古典的アルゴリズムを構築し、分析する。
我々のアルゴリズムは時間$O(operatornamepoly(D))$で動作し、従って以前の古典的アプローチから$D$への指数的依存を取り除く。
- 参考スコア（独自算出の注目度）: 4.633161758939183
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum machine learning (QML) aims to accelerate machine learning tasks by exploiting quantum computation. Previous work studied a QML algorithm for selecting sparse subnetworks from large shallow neural networks. Instead of directly solving an optimization problem over a large-scale network, this algorithm constructs a sparse subnetwork by sampling hidden nodes from an optimized probability distribution defined using the ridgelet transform. The quantum algorithm performs this sampling in time $O(D)$ in the data dimension $D$, whereas a naive classical implementation relies on handling exponentially many candidate nodes and hence takes $\exp[O(D)]$ time. In this work, we construct and analyze a quantum-inspired fully classical algorithm for the same sampling task. We show that our algorithm runs in time $O(\operatorname{poly}(D))$, thereby removing the exponential dependence on $D$ from the previous classical approach. Numerical simulations show that the proposed sampler achieves empirical risk comparable to exact sampling from the optimized distribution and substantially lower than sampling from the non-optimized uniform distribution, while also exhibiting exponentially improved runtime scaling compared with the conventional classical implementation. These successful dequantization results show that sparse subnetwork selection via optimized sampling can be achieved classically with polynomial data-dimension scaling on conventional computers without quantum hardware, providing an alternative to the existing quantum algorithm.
- Abstract（参考訳）: 量子機械学習(QML)は、量子計算を利用して機械学習タスクを高速化することを目的としている。
従来の研究では、大きな浅いニューラルネットワークからスパースサブネットワークを選択するためのQMLアルゴリズムが研究されていた。
大規模ネットワーク上での最適化問題を直接解決する代わりに、このアルゴリズムは、リッジレット変換を用いて定義された最適化確率分布から隠れノードをサンプリングすることによりスパースサブネットワークを構築する。
量子アルゴリズムはこのサンプリングをデータ次元$D$で時間$O(D)$で行い、一方単純古典的な実装は指数関数的に多くの候補ノードを扱うことに依存しているので、$\exp[O(D)]$時間を要する。
本研究では、同じサンプリングタスクに対して量子に着想を得た完全古典的アルゴリズムを構築し、解析する。
我々のアルゴリズムは時間$O(\operatorname{poly}(D))$で実行され、これにより以前の古典的アプローチから$D$への指数的依存が取り除かれる。
シミュレーションにより,提案手法は最適化分布からの正確なサンプリングに匹敵し,最適化されていない均一分布からのサンプリングよりもかなり低い精度で,従来の古典的実装と比較して指数関数的に改善された実行時スケーリングを示す。
これらの量子化結果は、最適化サンプリングによるスパースサブネットワークの選択が、従来の量子ハードウェアを使わずに、多項式データ次元のスケーリングによって古典的に達成できることを示し、既存の量子アルゴリズムの代替となる。
関連論文リスト
- Classical Combinatorial Optimization Scaling for Random Ising Models on 2D Heavy-Hex Graphs [0.8192907805418583]
重ヘックスグラフ上のイジングモデルは、経験的時間スケーリングにより古典的な計算硬度について検討する。
これらのイジングモデルの空間性のため、古典的アルゴリズムは大規模インスタンスに対しても効率的に最適解を見つけることができる。
論文 参考訳（メタデータ） (2024-12-20T05:09:30Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph
Classification [0.9935277311162707]
2つのグラフが互いに小さいかどうかを決定するNP完全問題に対するハイブリッド量子古典アルゴリズムを提案する。
ワンショット分類精度と入力スクイーズ量とのトレーディングが可能なグラフ埋め込みを見つける。
本稿では,グラフスペクトルに基づく新しい古典的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-05T21:24:11Z) - Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
変分量子アルゴリズムは, 近い将来, 古典的アルゴリズムの代替となる可能性が示唆された。
特に、2つのアルゴリズム、すなわち量子近似最適化アルゴリズム(QAOA)と変分量子固有解器(VQE)の性能を比較した。
シミュレーション実験は、クラウドと2つのエッジノードを含む %CM230124 の単純な問題に対して実施され、VQE アルゴリズムは、検索空間を制限できる適切な回路テクスタイタンサッチを備えている場合に、より良い性能を保証することを示す。
論文 参考訳（メタデータ） (2024-01-25T17:37:40Z) - Automatic and effective discovery of quantum kernels [41.61572387137452]
量子コンピューティングは、カーネルマシンが量子カーネルを利用してデータ間の類似度を表現できるようにすることで、機械学習モデルを強化することができる。
本稿では,ニューラルアーキテクチャ検索やAutoMLと同じような最適化手法を用いて,この問題に対するアプローチを提案する。
その結果、高エネルギー物理問題に対する我々のアプローチを検証した結果、最良のシナリオでは、手動設計のアプローチに関して、テストの精度を一致または改善できることが示された。
論文 参考訳（メタデータ） (2022-09-22T16:42:14Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
勾配勾配勾配による古典的トレーサビリティに寄与する条件は、量子線形系を効率的に解くために必要な条件と一致することを示す。
MNIST画像データセットがそのような条件を満たすことを数値的に示す。
我々は、プールを用いた畳み込みニューラルネットワークのトレーニングに$O(log n)$の実証的証拠を提供する。
論文 参考訳（メタデータ） (2021-07-19T23:41:03Z) - Accelerating variational quantum algorithms with multiple quantum
processors [78.36566711543476]
変分量子アルゴリズム(VQA)は、特定の計算上の利点を得るために、短期量子マシンを利用する可能性がある。
現代のVQAは、巨大なデータを扱うために単独の量子プロセッサを使用するという伝統によって妨げられている、計算上のオーバーヘッドに悩まされている。
ここでは、この問題に対処するため、効率的な分散最適化手法であるQUDIOを考案する。
論文 参考訳（メタデータ） (2021-06-24T08:18:42Z) - Learning with Optimized Random Features: Exponential Speedup by Quantum
Machine Learning without Sparsity and Low-Rank Assumptions [8.08640000394814]
我々は,実行時特性を最適化した分布からサンプリングする量子アルゴリズムを開発した。
我々のアルゴリズムは、このサンプリングタスクの既知の古典的アルゴリズムと比較して、D$の指数的な高速化を実現している。
論文 参考訳（メタデータ） (2020-04-22T18:00:00Z) - Lipschitz constant estimation of Neural Networks via sparse polynomial
optimization [47.596834444042685]
LiPoptは、ニューラルネットワークのリプシッツ定数上のより厳密な上限を計算するためのフレームワークである。
ネットワークの疎結合性を利用して、ネットワークの複雑さを大幅に軽減する方法を示す。
ランダムな重みを持つネットワークと、MNISTで訓練されたネットワークで実験を行う。
論文 参考訳（メタデータ） (2020-04-18T18:55:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。