論文の概要: The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight
- arxiv url: http://arxiv.org/abs/2610.42069v1
- Date: Fri, 30 Oct 2026 17:27:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-02 22:05:31.853525
- Title: The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight
- Title(参考訳): 線形代数の量子と量子化アルゴリズムの間の量子ギャップはわずか
- Abstract要約: 量子ランダムアクセスメモリ(QRAM)を介して行列$A$にアクセスする線形代数の量子アルゴリズムについて検討する。
古典的なアルゴリズムでは、サンプリングとクエリアクセスが$A$に与えられると、サンプリングとクエリアクセスを近似したソリューションに返します。
その結果, 線形代数に対する多くの量子アルゴリズムは, 最悪の場合, 近似的な高速化を実現することがわかった。
- 参考スコア(独自算出の注目度): 4.433169165028139
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to $A$, return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm $ρ=\|A\|_F/\|A\|$ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use $\widetilde O(ρ)$ queries, whereas the best dequantized algorithms use $\widetilde O(ρ^4)$. We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant $κ_0>1$, we construct dense linear systems with condition number at most $κ_0$ for which sampling from the solution within a sufficiently small constant total variation distance requires $Ω(ρ^4/\logρ)$ classical queries but only $Θ(ρ)$ quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.
- Abstract(参考訳): 行列$A$に量子ランダムアクセスメモリ(QRAM)を介してアクセスする線形代数の量子アルゴリズムは、線形系の解と関連する問題に比例する量子状態を作成する。
古典的なアルゴリズムでは、サンプリングとクエリアクセスが$A$に与えられると、サンプリングとクエリアクセスを近似したソリューションに返します。
どちらのアルゴリズムも、正規化されたフロベニウスノルム $ρ=\|A\|_F/\|A\|$ の多項式である多くのクエリを使用し、その次元に直接依存しない。
固定条件数と精度の線形系では、量子アルゴリズムは$\widetilde O(ρ)$クエリを使用するのに対し、最良の量子化アルゴリズムは$\widetilde O(ρ^4)$を使用する。
我々は、このクォートギャップが最悪の場合、対数係数まできついことを証明している。
すべての定数 $κ_0>1$ に対して、条件番号が最大$κ_0$ の高密度線型系を構築する。
同じ分離は、より小さなしきい値以下の誤差に対して、正定値系の最小二乗、尾根回帰、行列パワーと平方根、虚時間および実時間ハミルトン進化、および上位主成分からのサンプリングを保っている。
以上の結果から,線形代数に対する多くの量子アルゴリズムは,サンプリングとクエリアクセスを伴う古典的アルゴリズムよりも,最悪の場合において近似的な高速化を実現していることがわかった。
これらの古典的な下界はすべて、未知のブール関数のフーリエ係数の固定集合に依存する分布からサンプリングするための下界に基づく同じ枠組みから従う。
関連論文リスト
- Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。
我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
論文 参考訳(メタデータ) (2026-09-30T17:51:21Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳(メタデータ) (2026-04-09T16:38:14Z) - Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers [1.1666234644810893]
量子線形システム (quantum linear system, QLS) は、潜在的な量子コンピューティングアプリケーションで使用される量子アルゴリズムの基本クラスである。
QLSソルバの複雑性を決定する主要なパラメータは、線形系の条件番号$$とsprsity$s$である。
一定の誤差でQLSを解く任意の量子アルゴリズムに対して、$(sqrts)$の低い境界を証明します。
論文 参考訳(メタデータ) (2026-01-23T12:27:08Z) - A probabilistic quantum algorithm for Lyapunov equations and matrix inversion [0.0]
リアプノフ方程式の解に比例した混合状態を生成する確率論的量子アルゴリズムを提案する。
各ステップでアルゴリズムは現在の状態を返すか、全く正の正の地図をトレースしないか、あるいは偏りのあるコインフリップとアンシラ測定の結果に応じて再起動する。
最も一般的な形式で、アルゴリズムは行列値の重み付き和と積分を近似した混合状態を生成する。
論文 参考訳(メタデータ) (2025-08-06T17:52:06Z) - 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) - Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳(メタデータ) (2023-12-21T18:57:54Z) - Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs [0.0]
そこで我々は, 断熱量子計算に基づく線形線形解法アルゴリズムを開発した。
このアルゴリズムは最適スケーリング$O(kappa/log$)$に改善され、$epsilon$が指数関数的に改善される。
ハミルトンシミュレーションの代わりに、より安価なランダム化されたウォーク演算子法を導入する。
論文 参考訳(メタデータ) (2023-05-19T00:07:32Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳(メタデータ) (2022-10-12T19:10:43Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-12T16:29:45Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳(メタデータ) (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。