Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1803.01601

Quantum Algorithms to Matrix Multiplication

Changpeng Shao

Published Mar 5, 2018• 34 citations
arXivHTMLPDF

Abstract

In this paper, we study quantum algorithms of matrix multiplication from the viewpoint of inputting quantum/classical data to outputting quantum/classical data. The main target is trying to overcome the input and output problem, which are not easy to solve and many quantum algorithms will encounter, to study matrix operations in quantum computer with high efficiency. And solving matrix multiplication will be the first step. We propose three quantum algorithms to matrix multiplication based on swap test, SVE and HHL. From the point of making fewer assumptions, swap test method works the best than the other two. We also show that the quantum algorithm of matrix multiplication with classical input and output data by swap test achieves the best complexity $\widetilde{O}(n^2/ε)$ with no assumptions. This is proved by giving an efficient quantum algorithm in polynomial time to solve the input problem, that is to prepare the quantum states of the classical data efficiently. Other contributions of this paper include: (1). Extending swap test to a more general form that is suitable to deal with quantum data in parallel, which will have further applications in other matrix operations. (2). Generalizing SVE technique such that it applies to any matrix (not just Hermitian) directly only with quantum data. (3). Proposing two new efficient quantum algorithms to prepare quantum states of classical data, which solves the input problem efficiently than other quantum algorithms.

DOI
10.48550/arxiv.1803.01601

Related papers

Quantum Matrix Multiplication

Changpeng Shao

In this work, we provide a quantum algorithm to the matrix multiplication problem. When the norm of rows and columns of given matrices are small in size $O(d^{0.3728639})$, then our algorithm is better than the best classical algorithm. The main techniques are swap test and quantum state preparation.

•Mar 5, 2018•0 citations

Quantum Algorithms for Matrix Problems and Machine Learning

Sathyawageeswar Subramanian

This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.

•Jul 24, 2020•0 citations

Quantum Time-Space Tradeoffs for Matrix Problems

Paul W. Beame, Niels Kornerup, Michael Whitmeyer

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 with at most a constant factor loss. For example, for almost all fixed matrices [Formula: see text], including the discrete Fourier transform matrix, we prove that quantum circuits with at most [Formula: see text] input queries and [Formula: see text] qubits of memory require [Formula: see text] to compute matrix-vector product [Formula: see text] for [Formula: see text]. We similarly prove that matrix multiplication for [Formula: see text] binary matrices requires [Formula: see text]. 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 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 [Formula: see text] Boolean matrix multiplication to [Formula: see text] from [Formula: see text]. Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits.

arXiv:2401.05321•SIAM Journal on Computing•May 20, 2026•5 citations

QW-HHL: A Quantum Computer Amenable General Matrix Equation Solver

Christopher D. Phillips, Helia Akbari, Vladimir Okhmatovski

Quantum computation offers a promising alternative to classical computing methods in many areas of numerical science, with algorithms that make use of the unique ways in which quantum computers store and manipulate data often achieving dramatic improvements in performance over their classical counterparts. The potential efficiency of quantum computers is particularly important for numerical simulations, where the capabilities of classical computing systems are often insufficient for the analysis of real-world problems. In this work, we study problems involving the solution of matrix equations, for which there is limited research on efficient, general, and fully implemented quantum procedures. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary, which we have adopted from research in the area of quantum walks, has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware for any well-conditioned system. The procedure is most useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with O(sN log(N)) complexity, where N is the number of unknowns, and s is an upper bound on the number of nonzero elements in any row of the system matrix. This efficiency is competitive with the most sophisticated available classical solvers, and is independent of the structure of the input matrix. Hence, this procedure represents an important step towards the achievement of quantum advantage over classical algorithms for practical problems in numerical science.

IEEE journal on multiscale and multiphysics computational techniques•Jan 1, 2026•1 citation

A Quasi-Random Approach to Matrix Spectral Analysis

Michael Ben-Or, Lior Eldar

Inspired by the quantum computing algorithms for Linear Algebra problems [HHL,TaShma] we study how the simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to solve the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in $O(\log^2 n)$ parallel time with a total cost of $O(n^{ω+1})$ Boolean operations. This Boolean complexity matches the best known rigorous $O(\log^2 n)$ parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so further improvements may lead to practical implementations. All previous efficient and rigorous approaches to solve the Eigen-Problem use randomization to avoid bad condition as we do too. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases $(\mod (2π))$ is the main technical contribution of this work. This randomization enables us, given a Hermitian matrix with well separated eigenvalues, to sample a random eigenvalue and produce an approximate eigenvector in $O(\log^2 n)$ parallel time and $O(n^ω)$ Boolean complexity. We conjecture that further improvements of our method can provide a stable solution to the full approximate spectral decomposition problem with complexity similar to the complexity (up to a logarithmic factor) of sampling a single eigenvector.

arXiv:1505.08126•Leibniz international proceedings in informatics•May 29, 2015•4 citations

Quantum-Efficient Convolution through Sparse Matrix Encoding and Low-Depth Inner Product Circuits

Mohammad Rasoul Roshanshah, Payman Kazemikhah, Hossein Aghababa

Convolution operations are foundational to classical image processing and modern deep learning architectures, yet their extension into the quantum domain has remained algorithmically and physically costly due to inefficient data encoding and prohibitive circuit complexity. In this work, we present a resource-efficient quantum algorithm that reformulates the convolution product as a structured matrix multiplication via a novel sparse reshaping formalism. Leveraging the observation that localized convolutions can be encoded as doubly block-Toeplitz matrix multiplications, we construct a quantum framework wherein sparse input patches are prepared using optimized key-value QRAM state encoding, while convolutional filters are represented as quantum states in superposition. The convolution outputs are computed through inner product estimation using a low-depth SWAP test circuit, which yields probabilistic amplitude information with reduced sampling overhead. Our architecture supports batched convolution across multiple filters using a generalized SWAP circuit. Compared to prior quantum convolutional approaches, our method eliminates redundant preparation costs, scales logarithmically with input size under sparsity, and enables direct integration into hybrid quantum-classical machine learning pipelines. This work provides a scalable and physically realizable pathway toward quantum-enhanced feature extraction, opening up new possibilities for quantum convolutional neural networks and data-driven quantum inference.

arXiv:2507.19658•Jul 25, 2025•0 citations
In this paper, we study quantum algorithms of matrix multiplication from the viewpoint of inputting quantum/classical data to outputting quantum/classical data. The main target is trying to overcome the input and output problem, which are not easy to solve and many quantum algorithms will encounter, to study matrix operations in quantum computer with high efficiency. And solving matrix multiplication will be the first step. We propose three quantum algorithms to matrix multiplication based on swap test, SVE and HHL. From the point of making fewer assumptions, swap test method works the best than the other two. We also show that the quantum algorithm of matrix multiplication with classical input and output data by swap test achieves the best complexity O~(n2/ε)\widetilde{O}(n^2/ε)O(n2/ε) with no assumptions. This is proved by giving an efficient quantum algorithm in polynomial time to solve the input problem, that is to prepare the quantum states of the classical data efficiently. Other contributions of this paper include: (1). Extending swap test to a more general form that is suitable to deal with quantum data in parallel, which will have further applications in other matrix operations. (2). Generalizing SVE technique such that it applies to any matrix (not just Hermitian) directly only with quantum data. (3). Proposing two new efficient quantum algorithms to prepare quantum states of classical data, which solves the input problem efficiently than other quantum algorithms.
In this work, we provide a quantum algorithm to the matrix multiplication problem. When the norm of rows and columns of given matrices are small in size O(d0.3728639)O(d^{0.3728639})O(d0.3728639), then our algorithm is better than the best classical algorithm. The main techniques are swap test and quantum state preparation.
This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.
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 with at most a constant factor loss. For example, for almost all fixed matrices [Formula: see text], including the discrete Fourier transform matrix, we prove that quantum circuits with at most [Formula: see text] input queries and [Formula: see text] qubits of memory require [Formula: see text] to compute matrix-vector product [Formula: see text] for [Formula: see text]. We similarly prove that matrix multiplication for [Formula: see text] binary matrices requires [Formula: see text]. 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 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 [Formula: see text] Boolean matrix multiplication to [Formula: see text] from [Formula: see text]. Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits.
Quantum computation offers a promising alternative to classical computing methods in many areas of numerical science, with algorithms that make use of the unique ways in which quantum computers store and manipulate data often achieving dramatic improvements in performance over their classical counterparts. The potential efficiency of quantum computers is particularly important for numerical simulations, where the capabilities of classical computing systems are often insufficient for the analysis of real-world problems. In this work, we study problems involving the solution of matrix equations, for which there is limited research on efficient, general, and fully implemented quantum procedures. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary, which we have adopted from research in the area of quantum walks, has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware for any well-conditioned system. The procedure is most useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with O(sN log(N)) complexity, where N is the number of unknowns, and s is an upper bound on the number of nonzero elements in any row of the system matrix. This efficiency is competitive with the most sophisticated available classical solvers, and is independent of the structure of the input matrix. Hence, this procedure represents an important step towards the achievement of quantum advantage over classical algorithms for practical problems in numerical science.
Inspired by the quantum computing algorithms for Linear Algebra problems [HHL,TaShma] we study how the simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to solve the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in O(log⁡2n)O(\log^2 n)O(log2n) parallel time with a total cost of O(nω+1)O(n^{ω+1})O(nω+1) Boolean operations. This Boolean complexity matches the best known rigorous O(log⁡2n)O(\log^2 n)O(log2n) parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so further improvements may lead to practical implementations. All previous efficient and rigorous approaches to solve the Eigen-Problem use randomization to avoid bad condition as we do too. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases (mod  (2π))(\mod (2π))(mod(2π)) is the main technical contribution of this work. This randomization enables us, given a Hermitian matrix with well separated eigenvalues, to sample a random eigenvalue and produce an approximate eigenvector in O(log⁡2n)O(\log^2 n)O(log2n) parallel time and O(nω)O(n^ω)O(nω) Boolean complexity. We conjecture that further improvements of our method can provide a stable solution to the full approximate spectral decomposition problem with complexity similar to the complexity (up to a logarithmic factor) of sampling a single eigenvector.
Convolution operations are foundational to classical image processing and modern deep learning architectures, yet their extension into the quantum domain has remained algorithmically and physically costly due to inefficient data encoding and prohibitive circuit complexity. In this work, we present a resource-efficient quantum algorithm that reformulates the convolution product as a structured matrix multiplication via a novel sparse reshaping formalism. Leveraging the observation that localized convolutions can be encoded as doubly block-Toeplitz matrix multiplications, we construct a quantum framework wherein sparse input patches are prepared using optimized key-value QRAM state encoding, while convolutional filters are represented as quantum states in superposition. The convolution outputs are computed through inner product estimation using a low-depth SWAP test circuit, which yields probabilistic amplitude information with reduced sampling overhead. Our architecture supports batched convolution across multiple filters using a generalized SWAP circuit. Compared to prior quantum convolutional approaches, our method eliminates redundant preparation costs, scales logarithmically with input size under sparsity, and enables direct integration into hybrid quantum-classical machine learning pipelines. This work provides a scalable and physically realizable pathway toward quantum-enhanced feature extraction, opening up new possibilities for quantum convolutional neural networks and data-driven quantum inference.