論文の概要: Improved quantum lower and upper bounds for matrix scaling
- arxiv url: http://arxiv.org/abs/2109.15282v1
- Date: Thu, 30 Sep 2021 17:29:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-12 23:02:49.296390
- Title: Improved quantum lower and upper bounds for matrix scaling
- Title（参考訳）: 行列スケーリングのための量子下界と上界の改善
- Authors: Sander Gribling, Harold Nieuwboer
- Abstract要約: 古典的2次アルゴリズムにおける量子スピードアップの可能性について検討する。
我々は,高精度システムにおける入力サイズに関して,本質的に量子スピードアップが存在しないことを示す。
我々は低精度方式で改良された量子アルゴリズムを与える。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Matrix scaling is a simple to state, yet widely applicable linear-algebraic
problem: the goal is to scale the rows and columns of a given non-negative
matrix such that the rescaled matrix has prescribed row and column sums.
Motivated by recent results on first-order quantum algorithms for matrix
scaling, we investigate the possibilities for quantum speedups for classical
second-order algorithms, which comprise the state-of-the-art in the classical
setting.
We first show that there can be essentially no quantum speedup in terms of
the input size in the high-precision regime: any quantum algorithm that solves
the matrix scaling problem for $n \times n$ matrices with at most $m$ non-zero
entries and with $\ell_2$-error $\varepsilon=\widetilde\Theta(1/m)$ must make
$\widetilde\Omega(m)$ queries to the matrix, even when the success probability
is exponentially small in $n$. Additionally, we show that for
$\varepsilon\in[1/n,1/2]$, any quantum algorithm capable of producing
$\frac{\varepsilon}{100}$-$\ell_1$-approximations of the row-sum vector of a
(dense) normalized matrix uses $\Omega(n/\varepsilon)$ queries, and that there
exists a constant $\varepsilon_0>0$ for which this problem takes
$\Omega(n^{1.5})$ queries.
To complement these results we give improved quantum algorithms in the
low-precision regime: with quantum graph sparsification and amplitude
estimation, a box-constrained Newton method can be sped up in the
large-$\varepsilon$ regime, and outperforms previous quantum algorithms. For
entrywise-positive matrices, we find an $\varepsilon$-$\ell_1$-scaling in time
$\widetilde O(n^{1.5}/\varepsilon^2)$, whereas the best previously known bounds
were $\widetilde O(n^2\mathrm{polylog}(1/\varepsilon))$ (classical) and
$\widetilde O(n^{1.5}/\varepsilon^3)$ (quantum).
- Abstract（参考訳）: 行列スケーリングは単純な状態であり、広く適用可能な線形代数的問題である: 目標は、与えられた非負行列の行と列を、再スケールされた行列が所定の行と列和を持つようにスケーリングすることである。
行列スケーリングのための一階量子アルゴリズムの最近の結果に触発され、古典的な2階量子アルゴリズムの量子スピードアップの可能性について検討した。
行列のスケーリング問題をn \times n$行列で解く量子アルゴリズムは、最大$m$非ゼロエントリで$\ell_2$-error$\varepsilon=\widetilde\theta(1/m)$で、行列に対して$\widetilde\omega(m)$クエリを行なわなければならない。
さらに、$\varepsilon\in[1/n,1/2]$ に対して、(dense)正規化行列の行和ベクトルの近似値である$\frac{\varepsilon}{100}$-$\ell_1$ を生成可能な量子アルゴリズムは$\omega(n/\varepsilon)$クエリを使用し、この問題に$\omega(n^{1.5})$クエリがかかる定数 $\varepsilon_0>0$ が存在することを示す。
量子グラフのスパーシフィケーションと振幅推定により、箱に拘束されたニュートン法は、大きな$\varepsilon$レギュレーションでスピンアップでき、以前の量子アルゴリズムよりも優れていた。
入力に陽性な行列の場合、$\varepsilon$-$\ell_1$-scaling in time $\widetilde O(n^{1.5}/\varepsilon^2)$ が、最もよく知られている境界は $\widetilde O(n^2\mathrm{polylog}(1/\varepsilon))$ (古典) と $\widetilde O(n^{1.5}/\varepsilon^3)$ (量子)である。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix [2.7050250604223693]
与えられた$dtimes d$ matrix $A$ のトップ固有ベクトルのよい近似を見つけることは、基礎的で重要な計算問題である。
上位固有ベクトルの近似の古典的な記述を出力する2つの異なる量子アルゴリズムを与える。
論文 参考訳（メタデータ） (2024-05-23T16:33:13Z) - Quantum Time-Space Tradeoffs for Matrix Problems [0.5524804393257919]
量子コンピュータが行列を含む様々な問題を解くのに必要な時間と空間を考察する。
ほぼ全ての行列$A$に対して、少なくとも$T$の入力クエリと$S$のメモリを持つ量子回路は$T=Omega(n2/S)$を必要とすることを証明している。
我々の下界の多くは時間と空間の複雑さで決定論的アルゴリズムと一致するため、量子コンピュータは任意の空間境界を持つこれらの問題に対していかなる利点も提供できないことを示す。
論文 参考訳（メタデータ） (2024-01-10T18:38:43Z) - A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。
このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。
また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
論文 参考訳（メタデータ） (2023-11-07T22:52:56Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。
また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
論文 参考訳（メタデータ） (2022-12-05T19:10:32Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Quantum algorithms for matrix scaling and matrix balancing [9.010461408997646]
行列スケーリングと行列バランシングは、様々な応用の2つの基本的な線形代数問題である。
これらの問題に対する量子アルゴリズムのパワーと限界について検討する。
Sinkhornの行列スケーリングアルゴリズムとOsborneの行列バランスアルゴリズムの2つの古典的手法の量子的実装を提供する。
論文 参考訳（メタデータ） (2020-11-25T15:26:59Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。