Quantum Time-Space Tradeoffs for Matrix Problems

• URL: http://arxiv.org/abs/2401.05321v2
• Date: Mon, 12 Feb 2024 20:17:45 GMT
• Title: Quantum Time-Space Tradeoffs for Matrix Problems
• Authors: Paul Beame, Niels Kornerup, Michael Whitmeyer
• Abstract summary: We consider the time and space required for quantum computers to solve a range of problems involving matrices. For almost all matrices $A$, we prove that quantum circuits with at most $T$ input queries and $S$ qubits of memory require $T=Omega(n2/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 advantage for these problems with any space bound.
• Score: 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.

Related papers

• Optimal Quantization for Matrix Multiplication [35.007966885532724]
  We present a universal quantizer based on nested lattices with an explicit guarantee of approximation error for any (non-random) pair of matrices $A$, $B$ in terms of only Frobenius norms $|A|_F, |B|_F$ and $|Atop B|_F$.
  arXiv  Detail & Related papers  (2024-10-17T17:19:48Z)
• A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
  We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix. This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup. We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix's low-energy subspace.
  arXiv  Detail & Related papers  (2023-11-07T22:52:56Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
  arXiv  Detail & Related papers  (2022-02-10T08:12:20Z)
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra [6.338178373376447]
  We propose a block-encoding scheme of the hierarchical matrix structure on a quantum computer. Our method can improve the runtime of solving quantum linear systems of dimension $N$ to $O(kappa operatornamepolylog(fracNvarepsilon))$.
  arXiv  Detail & Related papers  (2022-01-27T05:24:02Z)
• Improved quantum lower and upper bounds for matrix scaling [0.0]
  We investigate the possibilities for quantum speedups for classical second-order algorithms. We show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime. We give improved quantum algorithms in the low-precision regime.
  arXiv  Detail & Related papers  (2021-09-30T17:29:23Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Quantum algorithms for matrix scaling and matrix balancing [9.010461408997646]
  Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications. We study the power and limitations of quantum algorithms for these problems. We provide quantum implementations of two classical methods: Sinkhorn's algorithm for matrix scaling and Osborne's algorithm for matrix balancing.
  arXiv  Detail & Related papers  (2020-11-25T15:26:59Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  We propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix. We show that our approach obtains small error and is efficient in both space and time.
  arXiv  Detail & Related papers  (2020-02-23T03:07:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.