Quantum query complexity with matrix-vector products
- URL: http://arxiv.org/abs/2102.11349v2
- Date: Sun, 14 Mar 2021 18:13:18 GMT
- Title: Quantum query complexity with matrix-vector products
- Authors: Andrew M. Childs, Shih-Han Hung, Tongyang Li
- Abstract summary: We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector.
We show that for various problems, including computing the trace, determinant or rank of a matrix, quantum computers do not provide an speedup over classical computation.
- Score: 9.192149087264033
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study quantum algorithms that learn properties of a matrix using queries
that return its action on an input vector. We show that for various problems,
including computing the trace, determinant, or rank of a matrix or solving a
linear system that it specifies, quantum computers do not provide an asymptotic
speedup over classical computation. On the other hand, we show that for some
problems, such as computing the parities of rows or columns or deciding if
there are two identical rows or columns, quantum computers provide exponential
speedup. We demonstrate this by showing equivalence between models that provide
matrix-vector products, vector-matrix products, and vector-matrix-vector
products, whereas the power of these models can vary significantly for
classical computation.
Related papers
- Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it.
Each row of the matrix is encoded as a pure state of some quantum system.
The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
arXiv Detail & Related papers (2024-01-29T23:23:27Z) - Vectorization of the density matrix and quantum simulation of the von
Neumann equation of time-dependent Hamiltonians [65.268245109828]
We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations.
We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix.
A quantum algorithm to simulate the dynamics of the density matrix is proposed.
arXiv Detail & Related papers (2023-06-14T23:08:51Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions.
The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix.
We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
arXiv Detail & Related papers (2023-04-12T18:10:47Z) - A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph [4.045204834863644]
We propose an efficient quantum algorithm to solve the eigenproblem of the Laplacian matrix of a fully connected weighted graph.
Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework.
We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.
arXiv Detail & Related papers (2022-03-28T02:24:08Z) - 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) - A Quantum Computer Amenable Sparse Matrix Equation Solver [0.0]
We study problems involving the solution of matrix equations, for which there currently exists no efficient, general quantum procedure.
We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation.
This unitary has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware.
arXiv Detail & Related papers (2021-12-05T15:42:32Z) - 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 powering stable Hermitian matrices [0.7734726150561088]
Matrix powering is a fundamental computational primitive in linear algebra.
We present two quantum algorithms that can achieve speedup over the classical matrix powering algorithms.
arXiv Detail & Related papers (2021-03-15T12:20:04Z) - Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and
Graph Problems [58.83118651518438]
We consider the general problem of learning about a matrix through vector-matrix-vector queries.
These queries provide the value of $boldsymbolumathrmTboldsymbolMboldsymbolv$ over a fixed field.
We provide new upper and lower bounds for a wide variety of problems, spanning linear algebra, statistics, and graphs.
arXiv Detail & Related papers (2020-06-24T19:33:49Z) - Block-encoding based quantum algorithm for linear systems with
displacement structures [4.145426157018113]
We present efficient and memory-reduced quantum algorithms for solving linear systems with displacement structures.
The proposed block-encodings provide a quadratic speedup with respect to the dimension over classical algorithms.
One of the quantum linear system solvers is applied to the linear prediction of time series.
arXiv Detail & Related papers (2019-12-27T16:10:13Z)
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.