Quantum Time-Space Tradeoffs for Matrix Problems
CoRR(2024)
摘要
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=Ω(n^2/S) to compute matrix-vector product
Ax for x ∈{0,1}^n. We similarly prove that matrix multiplication for
n× n binary matrices requires T=Ω(n^3 / √(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× n Boolean matrix multiplication to
T=Ω(n^2.5/S^1/4) from T=Ω(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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要