論文の概要: Quantum Time-Space Tradeoffs for Matrix Problems
- arxiv url: http://arxiv.org/abs/2401.05321v2
- Date: Mon, 12 Feb 2024 20:17:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 18:43:29.368511
- Title: Quantum Time-Space Tradeoffs for Matrix Problems
- Title（参考訳）: 行列問題に対する量子時間空間トレードオフ
- Authors: Paul Beame, Niels Kornerup, Michael Whitmeyer
- Abstract要約: 量子コンピュータが行列を含む様々な問題を解くのに必要な時間と空間を考察する。
ほぼ全ての行列$A$に対して、少なくとも$T$の入力クエリと$S$のメモリを持つ量子回路は$T=Omega(n2/S)$を必要とすることを証明している。
我々の下界の多くは時間と空間の複雑さで決定論的アルゴリズムと一致するため、量子コンピュータは任意の空間境界を持つこれらの問題に対していかなる利点も提供できないことを示す。
- 参考スコア（独自算出の注目度）: 0.5524804393257919
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the time and space required for quantum computers to solve a wide
variety of problems involving matrices, many of which have only been analyzed
classically in prior work. Our main results show that for a range of linear
algebra problems -- including matrix-vector product, matrix inversion, matrix
multiplication and powering -- existing classical time-space tradeoffs, several
of which are tight for every space bound, also apply to quantum algorithms. For
example, for almost all matrices $A$, including the discrete Fourier transform
(DFT) matrix, we prove that quantum circuits with at most $T$ input queries and
$S$ qubits of memory require $T=\Omega(n^2/S)$ to compute matrix-vector product
$Ax$ for $x \in \{0,1\}^n$. We similarly prove that matrix multiplication for
$n\times n$ binary matrices requires $T=\Omega(n^3 / \sqrt{S})$. Because many
of our lower bounds match deterministic algorithms with the same time and space
complexity, we show that quantum computers cannot provide any asymptotic
advantage for these problems with any space bound. We obtain matching lower
bounds for the stronger notion of quantum cumulative memory complexity -- the
sum of the space per layer of a circuit.
We also consider Boolean (i.e. AND-OR) matrix multiplication and
matrix-vector products, improving the previous quantum time-space tradeoff
lower bounds for $n\times n$ Boolean matrix multiplication to
$T=\Omega(n^{2.5}/S^{1/4})$ from $T=\Omega(n^{2.5}/S^{1/2})$.
Our improved lower bound for Boolean matrix multiplication is based on a new
coloring argument that extracts more from the strong direct product theorem
used in prior work. Our tight lower bounds for linear algebra problems require
adding a new bucketing method to the recording-query technique of Zhandry that
lets us apply classical arguments to upper bound the success probability of
quantum circuits.
- Abstract（参考訳）: 量子コンピュータが行列を含む多種多様な問題を解くのに必要な時間と空間を考察する。
我々の主な結果は、行列ベクトル積、行列逆転、行列乗算、パワーリングを含む線形代数問題に対して、既存の古典的時間空間のトレードオフであり、そのいくつかはすべての空間境界に対して厳密である。
例えば、離散フーリエ変換(dft)行列を含むほぼすべての行列に対して、最大$t$ 入力クエリと$s$ qubits のメモリを持つ量子回路は$t=\omega(n^2/s)$ で行列ベクトル積 $ax$ for $x \in \{0,1\}^n$ を計算する必要があることを証明する。
同様に、$n\times n$二進行列の行列乗法は$T=\Omega(n^3 / \sqrt{S})$である。
我々の下界の多くは時間と空間の複雑さで決定論的アルゴリズムと一致しているため、量子コンピュータは任意の空間境界を持つこれらの問題に対して漸近的な利点を与えることができない。
我々は、回路の層毎の空間の和である量子累積記憶複雑性の強い概念に一致する下界を得る。
また、Boolean (すなわち AND-OR) 行列乗法と行列ベクトル積も考慮し、以前の量子時間空間のトレードオフの下限を$n\times n$ Boolean 行列乗法により$T=\Omega(n^{2.5}/S^{1/4})$から$T=\Omega(n^{2.5}/S^{1/2})$へと改善する。
ブール行列乗法に対する改善された下界は、以前の研究で用いられる強い直積定理からより多くを抽出する新しい着色引数に基づいている。
線形代数問題の厳密な下限には、量子回路の成功確率の上限に古典的引数を適用できるzhandryのレコード・クエリ技術に新しいバケット法を加える必要がある。
関連論文リスト
- Optimal Quantization for Matrix Multiplication [35.007966885532724]
我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
論文 参考訳（メタデータ） (2024-10-17T17:19:48Z) - A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。
このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。
また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
論文 参考訳（メタデータ） (2023-11-07T22:52:56Z) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
本稿では,「Sender-Receiver」モデルを用いた行列演算のための量子アルゴリズムを提案する。
これらの量子プロトコルは、他の量子スキームのサブルーチンとして使用できる。
論文 参考訳（メタデータ） (2022-02-10T08:12:20Z) - Block-encoding dense and full-rank kernels using hierarchical matrices:
applications in quantum numerical linear algebra [6.338178373376447]
本稿では,量子コンピュータ上の階層行列構造のブロック符号化方式を提案する。
我々の手法は、次元$N$から$O(kappa operatornamepolylog(fracNvarepsilon))$の量子線型系を解くランタイムを改善することができる。
論文 参考訳（メタデータ） (2022-01-27T05:24:02Z) - Improved quantum lower and upper bounds for matrix scaling [0.0]
古典的2次アルゴリズムにおける量子スピードアップの可能性について検討する。
我々は,高精度システムにおける入力サイズに関して,本質的に量子スピードアップが存在しないことを示す。
我々は低精度方式で改良された量子アルゴリズムを与える。
論文 参考訳（メタデータ） (2021-09-30T17:29:23Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - 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) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。
提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
論文 参考訳（メタデータ） (2020-02-23T03:07:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。