Quantum Time-Space Tradeoffs for Matrix Problems

We prove lower bounds on 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. Using a novel way of applying recording query methods we show that for many linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed 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 are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems at any space bound. We also improve the previous quantum time-space tradeoff lower bounds for n × n Boolean (i.e. AND-OR) matrix multiplication from T =Ω( n 2.5 / S 1/2 ) to T =Ω( n 2.5 / S 1/4 ) which has optimal exponents for the powerful query algorithms to which it applies. Our method also yields improved lower bounds for classical algorithms.

Authors

• Paul Beame
• Niels Kornerup
• Michael Whitmeyer

Keywords

• matrix-problems
• quantum time-space tradeoffs
• query complexity