論文の概要: Constant Factor Analysis of Optimal Quantum Linear Solvers in Practice

• arxiv url: http://arxiv.org/abs/2604.22185v2
• Date: Mon, 27 Apr 2026 10:50:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-28 17:12:06.95138
• Title: Constant Factor Analysis of Optimal Quantum Linear Solvers in Practice
• Title（参考訳）: 最適量子線形解法の実践における定数因子解析
• Authors: Pedro C. S. Costa, Alexander M. Dalzell, Dong An, Dominic W. Berry,
• Abstract要約: 離散的断熱的アプローチを用いた最適解法は、複雑性上の上界に対して大きな解析的に証明された定数因子を持つ。 ショートカット法は、証明された定数要素も小さい最適解法であることがわかった。 その結果,解ノルムが未知の場合,解解法は若干性能が向上することがわかった。
• 参考スコア（独自算出の注目度）: 42.05066415498962
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimal quantum linear equation solvers provide complexity $O(κ\log(1/ε))$, where $κ$ is the condition number and $ε$ is the allowable error. The optimal solver using a discrete adiabatic approach [PRX Quantum 3, 040303 (2022)] has large analytically proven constant factors for the upper bound on the complexity. The constant factors were later found to be about 1,200 times smaller in numerical testing [Quantum 9, 1887 (2025)]. This meant it is about an order of magnitude more efficient than using a randomised approach from [PRX Quantum 6, 040373 (2025)], which has far smaller analytically proven constant factors. Recently, a ``Shortcut'' method has been found to provide an optimal solver which also has small proven constant factors. In the present work, we conduct a comprehensive numerical analysis comparing this method with the adiabatic solver for two families of random linear systems. We find that, in the case where the solution norm is unknown, the adiabatic solver provides slightly better performance. If the solution norm is known, then the shortcut method provides significantly better performance for non-Hermitian matrices.
• Abstract（参考訳）: 最適量子線型方程式ソルバは複雑性$O(κ\log(1/ε))$を与え、$κ$は条件数、$ε$は許容誤差を与える。 離散的断熱法 (PRX Quantum 3, 040303 (2022)) を用いた最適解法は, 複雑性上の上界に対して大きな解析的定数因子を有する。 その後、定数係数は数値実験(Quantum 9 1887 (2025))で約1,200倍小さいことが判明した。 これは、[PRX Quantum 6, 040373 (2025)]からのランダム化アプローチよりも、はるかに小さく解析的に証明された定数因子を持つ、桁違いに効率的であることを意味している。 近年、 `Shortcut'' 法は、証明された定数要素が小さい最適解法を提供することがわかった。 本研究では,この手法を2種類のランダム線形系に対する断熱解法と比較した包括的数値解析を行った。 その結果,解ノルムが未知の場合,解解法は若干性能が向上することがわかった。 解ノルムが知られている場合、ショートカット法は非エルミート行列に対して著しく優れた性能を与える。

関連論文リスト

• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。 本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。 本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
  論文  参考訳（メタデータ） (2024-06-18T20:14:52Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver [3.2655159697679292]
  方程式の線形系の解は、他の多くの量子アルゴリズムの基礎である。 最近の結果は、条件番号 $kappa$ と許容可能なエラー $epsilon$ の両方で最適なスケーリングのアルゴリズムを提供する。 ここでは, ランダム行列の数値実験により, 定数係数は, 前回の結果から得られた上限値の約1,200倍小さいことを示す。
  論文  参考訳（メタデータ） (2023-12-12T19:36:41Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Optimal scaling quantum linear systems solver via discrete adiabatic theorem [0.9846257338039974]
  離散的に最適となる線形系を解くための量子アルゴリズムを開発した。 既存の最適化手法と比較して,本アルゴリズムはよりシンプルで実装が容易である。
  論文  参考訳（メタデータ） (2021-11-16T00:21:37Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。