論文の概要: Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm
- arxiv url: http://arxiv.org/abs/2602.05541v1
- Date: Thu, 05 Feb 2026 10:58:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-06 18:49:08.897254
- Title: Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm
- Title（参考訳）: 漸近最適量子アルゴリズムによる$O(N^2log_2N)$への行列乗算の複雑さの低減
- Authors: Jiaqi Yao, Ding Liu,
- Abstract要約: 本研究は量子カーネルベースの行列乗算アルゴリズム(QKMM)を提案する。
O(N2 log N) $ の計算複雑性は、古典的最適複雑性を$ O(N2.371552) $ よりも上回る。
- 参考スコア（独自算出の注目度）: 3.5649163180026484
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Matrix multiplication is a fundamental classical computing operation whose efficiency becomes a major challenge at scale, especially for machine learning applications. Quantum computing, with its inherent parallelism and exponential storage capacity, offers a potential solution to these limitations. This work presents a quantum kernel-based matrix multiplication algorithm (QKMM) that achieves an asymptotically optimal computational complexity of $ O(N^2 \log_2 N) $, outperforming the classical optimal complexity of $ O(N^{2.371552}) $, where $N$ denotes the matrix dimension. Through noiseless and noisy quantum simulation experiments, we demonstrate that the proposed algorithm not only exhibits superior theoretical efficiency but also shows practical advantages in runtime performance and stability.
- Abstract（参考訳）: 行列乗算(英: Matrix multiplication)は、特に機械学習アプリケーションにおいて、計算効率が大規模で大きな課題となる古典的な演算である。
量子コンピューティングは、本質的に並列性と指数的ストレージ容量を持ち、これらの制限に対する潜在的な解決策を提供する。
この研究は、量子カーネルベースの行列乗算アルゴリズム(QKMM)で、漸近的に最適な計算複雑性を$O(N^2 \log_2 N)$で達成し、古典的な最適複雑性を$O(N^{2.371552})$で上回る。
ノイズのない,ノイズの多い量子シミュレーション実験により,提案アルゴリズムは理論的効率性に優れるだけでなく,実行時の性能や安定性にも実用的優位性を示すことを示した。
関連論文リスト
- Optimal Scaling Quantum Interior Point Method for Linear Optimization [0.0]
本稿では,量子コンピュータ上でシステムを構築し,解決する新しい量子IPMを提案する。
このフレームワークは、完全に高密度なLO問題に対して$mathcalO(n2)$の最適な最悪のスケーリングを実現する。
我々のアルゴリズムは量子複雑性が$mathcalO(n1.5 _A log1)$QRAMへのクエリと$mathcalO(n2 log(frac1)$古典演算である。
論文 参考訳（メタデータ） (2025-12-04T06:44:22Z) - Towards efficient quantum algorithms for diffusion probabilistic models [27.433686030846072]
拡散モデル(DPM)は、画像や音声生成などのタスクで高品質な出力を生成する能力で有名である。
様々な量子解法を用いてDPMを実装するための効率的な量子アルゴリズムを導入する。
論文 参考訳（メタデータ） (2025-02-20T04:39:09Z) - Quantum-Trajectory-Inspired Lindbladian Simulation [16.17464946935405]
リンドブラディアンズが支配するオープン量子系の力学をシミュレーションする2つの量子アルゴリズムを提案する。
最初のアルゴリズムはジャンプ演算子数とは無関係にゲート複雑性を達成し、$m$は効率を大幅に向上させる。
第二のアルゴリズムは進化時間$t$と精度$epsilon$にほぼ最適に依存し、追加の$tildeO(m)$ factorを導入する。
論文 参考訳（メタデータ） (2024-08-20T03:08:27Z) - 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) - Compact quantum algorithms for time-dependent differential equations [0.0]
我々は、ユニタリの線形結合に基づくアイデアに基づいて、非ユニタリで非エルミート量子系をシミュレートする。
我々は,行列ベクトル乗算と行列逆演算を効率的に行うハイブリッド量子古典アルゴリズムを生成する。
論文 参考訳（メタデータ） (2024-05-16T02:14:58Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - A Quantum Computer Amenable Sparse Matrix Equation Solver [0.0]
本稿では,行列方程式の解法に関わる問題について検討する。
Harrow/Hassidim/Lloydアルゴリズムを固有位相推定のための代替ユニタリを提供することにより一般化する。
このユニタリは任意の行列方程式に対して十分に定義されているという利点があり、それによって解の手順を量子ハードウェアに直接実装することができる。
論文 参考訳（メタデータ） (2021-12-05T15:42:32Z) - Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。
LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
論文 参考訳（メタデータ） (2021-11-15T17:10:40Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。
一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。
幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
論文 参考訳（メタデータ） (2021-04-01T19:06:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。