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

Quantum Matrix Multiplication

Changpeng Shao

Published Mar 5, 2018• 0 citations
OpenAlex

Abstract

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.

Related papers

Quantum Algorithms to Matrix Multiplication

Changpeng Shao

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.

arXiv:1803.01601•Mar 5, 2018•34 citations

Improved Quantum Lower and Upper Bounds for Matrix Scaling

Sander Gribling, Harold A. Nieuwboer

Matrix scaling is a simple to state, yet widely applicable linear-algebraic problem: the goal is to scale the rows and columns of a given non-negative matrix such that the rescaled matrix has prescribed row and column sums. Motivated by recent results on first-order quantum algorithms for matrix scaling, we investigate the possibilities for quantum speedups for classical second-order algorithms, which comprise the state-of-the-art in the classical setting. We first show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime: any quantum algorithm that solves the matrix scaling problem for $n \times n$ matrices with at most $m$ non-zero entries and with $\ell_2$-error $\varepsilon=\widetildeΘ(1/m)$ must make $\widetildeΩ(m)$ queries to the matrix, even when the success probability is exponentially small in $n$. Additionally, we show that for $\varepsilon\in[1/n,1/2]$, any quantum algorithm capable of producing $\frac{\varepsilon}{100}$-$\ell_1$-approximations of the row-sum vector of a (dense) normalized matrix uses $Ω(n/\varepsilon)$ queries, and that there exists a constant $\varepsilon_0>0$ for which this problem takes $Ω(n^{1.5})$ queries. To complement these results we give improved quantum algorithms in the low-precision regime: with quantum graph sparsification and amplitude estimation, a box-constrained Newton method can be sped up in the large-$\varepsilon$ regime, and outperforms previous quantum algorithms. For entrywise-positive matrices, we find an $\varepsilon$-$\ell_1$-scaling in time $\widetilde O(n^{1.5}/\varepsilon^2)$, whereas the best previously known bounds were $\widetilde O(n^2\mathrm{polylog}(1/\varepsilon))$ (classical) and $\widetilde O(n^{1.5}/\varepsilon^3)$ (quantum).

arXiv:2109.15282•Leibniz international proceedings in informatics•Sep 30, 2021•7 citations

Quantum Algorithms for Matrix Products over Semirings

François Le Gall, Harumichi Nishimura

In this paper we construct quantum algorithms for matrix products over several algebraic structures called semirings, including the (max, min)-matrix product, the distance matrix product and the Boolean matrix product.In particular, we obtain the following results.• We construct a quantum algorithm computing the product of two n × n matrices over the (max, min) semiring with time complexity O(n 2.473 ).In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity O(n 2.687 ).• We construct a quantum algorithm computing the ℓ most significant bits of each entry of the distance product of two n × n matrices in time O(2 0.64ℓ n 2.46 ).In comparison, the best known classical algorithm for the same problem, by Vassilevska and Williams (STOC'06) and Yuster (SODA'09), has complexity O(2 ℓ n 2.69 ).The above two algorithms are the first quantum algorithms that perform better than the Õ(n 5/2 )-time straightforward quantum algorithm based on quantum search for matrix multiplication over these semirings.We also consider the Boolean semiring, and construct a quantum algorithm computing the product of two n × n Boolean matrices that outperforms the best known classical algorithms for sparse matrices.

arXiv:1310.3898•Chicago Journal of Theoretical Computer Science•Jan 1, 2017•2 citations

Quantum Subroutine for Efficient Matrix Multiplication

Anna Bernasconi, Alessandro Berti, Gianna M. Del Corso +1 more

We propose an efficient quantum subroutine for matrix multiplication that computes a state vector encoding the entries of the product of two matrices in superposition. The subroutine exploits efficient state preparation techniques and shows a potential speed-up with respect to classical methods. The most important benefit of our subroutine is that it encodes the entries of the matrix product directly in the state vector, which can be used for further computations within the same quantum circuit. All scenarios involving the computation of non-homomorphic functions of the product of two matrices can benefit from our technique. As a possible application, we discuss the computation of the variance of the entries of a matrix product, which can be a useful tool for some machine learning algorithms.

IEEE Access•Jan 1, 2024•12 citations

Quantum Linear System Algorithm for Dense Matrices

Leonard Wossnig, Zhikuan Zhao, Anupam Prakash

Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix $A$ and a vector $\mathbf{b}$ the task is to find the vector $\mathbf{x}$ such that $A\mathbf{x}=\mathbf{b}$. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional $A$ with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of $A$, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of $A$ is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of $A$ and the vector of Euclidean norms of the rows of $A$.

arXiv:1704.06174•Physical Review Letters•Jan 31, 2018•248 citations

Quantum hyperparallel algorithm for matrix multiplication

Xin-Ding Zhang, Xiao‐Ming Zhang, Zheng‐Yuan Xue

Hyperentangled states, entangled states with more than one degree of freedom, are considered as promising resource in quantum computation. Here we present a hyperparallel quantum algorithm for matrix multiplication with time complexity O(N(2)), which is better than the best known classical algorithm. In our scheme, an N dimensional vector is mapped to the state of a single source, which is separated to N paths. With the assistance of hyperentangled states, the inner product of two vectors can be calculated with a time complexity independent of dimension N. Our algorithm shows that hyperparallel quantum computation may provide a useful tool in quantum machine learning and "big data" analysis.

Scientific Reports•Apr 29, 2016•14 citations
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.
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.
Matrix scaling is a simple to state, yet widely applicable linear-algebraic problem: the goal is to scale the rows and columns of a given non-negative matrix such that the rescaled matrix has prescribed row and column sums. Motivated by recent results on first-order quantum algorithms for matrix scaling, we investigate the possibilities for quantum speedups for classical second-order algorithms, which comprise the state-of-the-art in the classical setting. We first show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime: any quantum algorithm that solves the matrix scaling problem for n×nn \times nn×n matrices with at most mmm non-zero entries and with ℓ2\ell_2ℓ2​-error ε=Θ~(1/m)\varepsilon=\widetildeΘ(1/m)ε=Θ(1/m) must make Ω~(m)\widetildeΩ(m)Ω(m) queries to the matrix, even when the success probability is exponentially small in nnn. Additionally, we show that for ε∈[1/n,1/2]\varepsilon\in[1/n,1/2]ε∈[1/n,1/2], any quantum algorithm capable of producing ε100\frac{\varepsilon}{100}100ε​-ℓ1\ell_1ℓ1​-approximations of the row-sum vector of a (dense) normalized matrix uses Ω(n/ε)Ω(n/\varepsilon)Ω(n/ε) queries, and that there exists a constant ε0>0\varepsilon_0>0ε0​>0 for which this problem takes Ω(n1.5)Ω(n^{1.5})Ω(n1.5) queries. To complement these results we give improved quantum algorithms in the low-precision regime: with quantum graph sparsification and amplitude estimation, a box-constrained Newton method can be sped up in the large-ε\varepsilonε regime, and outperforms previous quantum algorithms. For entrywise-positive matrices, we find an ε\varepsilonε-ℓ1\ell_1ℓ1​-scaling in time O~(n1.5/ε2)\widetilde O(n^{1.5}/\varepsilon^2)O(n1.5/ε2), whereas the best previously known bounds were O~(n2polylog(1/ε))\widetilde O(n^2\mathrm{polylog}(1/\varepsilon))O(n2polylog(1/ε)) (classical) and O~(n1.5/ε3)\widetilde O(n^{1.5}/\varepsilon^3)O(n1.5/ε3) (quantum).
In this paper we construct quantum algorithms for matrix products over several algebraic structures called semirings, including the (max, min)-matrix product, the distance matrix product and the Boolean matrix product.In particular, we obtain the following results.• We construct a quantum algorithm computing the product of two n × n matrices over the (max, min) semiring with time complexity O(n 2.473 ).In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity O(n 2.687 ).• We construct a quantum algorithm computing the ℓ most significant bits of each entry of the distance product of two n × n matrices in time O(2 0.64ℓ n 2.46 ).In comparison, the best known classical algorithm for the same problem, by Vassilevska and Williams (STOC'06) and Yuster (SODA'09), has complexity O(2 ℓ n 2.69 ).The above two algorithms are the first quantum algorithms that perform better than the Õ(n 5/2 )-time straightforward quantum algorithm based on quantum search for matrix multiplication over these semirings.We also consider the Boolean semiring, and construct a quantum algorithm computing the product of two n × n Boolean matrices that outperforms the best known classical algorithms for sparse matrices.
We propose an efficient quantum subroutine for matrix multiplication that computes a state vector encoding the entries of the product of two matrices in superposition. The subroutine exploits efficient state preparation techniques and shows a potential speed-up with respect to classical methods. The most important benefit of our subroutine is that it encodes the entries of the matrix product directly in the state vector, which can be used for further computations within the same quantum circuit. All scenarios involving the computation of non-homomorphic functions of the product of two matrices can benefit from our technique. As a possible application, we discuss the computation of the variance of the entries of a matrix product, which can be a useful tool for some machine learning algorithms.
Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix AAA and a vector b\mathbf{b}b the task is to find the vector x\mathbf{x}x such that Ax=bA\mathbf{x}=\mathbf{b}Ax=b. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional AAA with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of AAA, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of AAA is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of AAA and the vector of Euclidean norms of the rows of AAA.
Hyperentangled states, entangled states with more than one degree of freedom, are considered as promising resource in quantum computation. Here we present a hyperparallel quantum algorithm for matrix multiplication with time complexity O(N(2)), which is better than the best known classical algorithm. In our scheme, an N dimensional vector is mapped to the state of a single source, which is separated to N paths. With the assistance of hyperentangled states, the inner product of two vectors can be calculated with a time complexity independent of dimension N. Our algorithm shows that hyperparallel quantum computation may provide a useful tool in quantum machine learning and "big data" analysis.