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

Information

Quantum Algorithms for the Multiplication of Circulant Matrices and Vectors

Lu Hou, Zhenyu Huang, Chang Lv

Published Aug 1, 2024• 2 citations
Publisher

Abstract

This article presents two quantum algorithms for computing the product of a circulant matrix and a vector. The arithmetic complexity of the first algorithm is O(Nlog2N) in most cases. For the second algorithm, when the entries in the circulant matrix and the vector take values in C or R, the complexity is O(Nlog2N) in most cases. However, when these entries take values from positive real numbers, the complexity is reduced to O(log3N) in most cases, which presents an exponential speedup compared to the classical complexity of O(NlogN) for computing the product of a circulant matrix and vector. We apply this algorithm to the convolution calculation in quantum convolutional neural networks, which effectively accelerates the computation of convolutions. Additionally, we present a concrete quantum circuit structure for quantum convolutional neural networks.

DOI
10.3390/info15080453

Related papers

A quantum algorithm for Toeplitz matrix-vector multiplication

Shang Gao, Yu-Guang 宇光 Yang 杨

Toeplitz matrix-vector multiplication is widely used in various fields, including optimal control, systolic finite field multipliers, multidimensional convolution, etc. In this paper, we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity O ( κ polylog n ) , where κ and 2n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix, respectively. For the case with an unknown generating function, we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L 1-norm ρ of the displacement of the structured matrices. Due to the good use of the special properties of Toeplitz matrices, the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.

Chinese Physics B•Feb 6, 2023•5 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

Reducing the Complexity of Matrix Multiplication by Quantum Computing

Jiaqi Yao, Tianjian Huang, Tonghe Zhang +1 more

Matrix multiplication is a fundamental operation in compute-intensive tasks and a key component of modern quantum acceleration frameworks. Here we present a quantum matrix multiplication algorithm based on quantum kernels (QKMM), achieving an elementary gate complexity of \(O(N^2\log_2N)\), with amplitude encoding overhead explicitly included and without assuming a QRAM oracle. This scaling is asymptotically lower than that of the best-known classical matrix multiplication algorithm \(O(N^{2.371339})\). Building upon QKMM, we establish a family of quantum linear algebra operators, including Quantum Vector Inner Product (V${\scriptstyle 2}$V), Quantum Vector-Matrix Multiplication (V${\scriptstyle 2}$M), QKMM (M${\scriptstyle 2}$M), Quantum One-to-Many Matrix Multiplication(O${\scriptstyle 2}$M) and Quantum Sequential Matrix Multiplication (SMM), providing a unified framework from vector operations to parallel and sequential matrix transformations. Through noiseless simulations, realistic noise modelling and experiments on a superconducting quantum processor, we systematically characterize the numerical accuracy, resource requirements and hardware execution limits of this operator framework. Furthermore, we integrate SMM into deep neural-network inference, enabling intermediate features to propagate coherently across layers without repeated measurement and re-encoding. These results establish a pathway from quantum circuit-level algorithm design to end-to-end coherent computation, providing a quantum computing framework for matrix-centric compute-intensive applications.

quant-pharXiv:2602.05541•Feb 6, 2026•0 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

Universal Matrix Multiplication on Quantum Computer

J. M. Yao, Huang, Tianjian, Cai, Zipeng +1 more

As the most central and computationally intensive component of deep neural networks, the execution efficiency of matrix multiplication directly determines the training and inference performance of models. Harnessing the parallel processing capabilities afforded by quantum superposition and entanglement to reshape matrix multiplication implementations has become a promising entry point for optimising underlying quantum arithmetic logic and improving the operational efficiency of quantum circuits. This paper proposes a universal quantum matrix multiplication (QMM) framework designed to achieve substantial computational acceleration through an optimised quantum arithmetic logic unit. To circumvent the limitations of multi-register and multi-control gates in conventional quantum arithmetic circuits, we encode classical data directly into parameterised \(R_z\) rotation gates using the quantum Fourier transform (QFT), thereby reducing the base gate complexity of the quantum adder to \(O(n)\). In addition, by adopting the column-wise multiplication principle from classical arithmetic, we optimize the gate complexity of the quantum multiplier to \(O(n^2)\). We further extend this approach to a quantum version of the Strassen algorithm, and experimentally quantify the trade-off between reduced multiplication time and increased overhead in addition resources. This work establishes a reliable technical pathway for constructing general-purpose quantum matrix operations, with the potential to unlock substantial computational power for training modern machine learning models.

arXiv:2408.03085•Aug 6, 2024•1 citation

Quantum positive matrix-positive matrix multiplication algorithm

Jinchuan Yang, S. He, Ming-Qiang Bai +1 more

Abstract In quantum computing, matrix multiplication occurs as a subroutine in more complex algorithms. We improve the quantum linear system algorithm [Harrow et al. 2009 Phys. Rev. Lett. 103 150502] to perform sparse matrix-matrix multiplication and propose a subroutine for parallel vector addition. Based on them, a quantum algorithm is exhibited for N×N positive matrix-positive matrix multiplication. For some small ratio of the maximum element to the minimum element of the positive matrices (i.e.,O(poly logN)), this algorithm achieves exponential acceleration.

Journal of Physics A Mathematical and Theoretical•Sep 30, 2024•0 citations
This article presents two quantum algorithms for computing the product of a circulant matrix and a vector. The arithmetic complexity of the first algorithm is O(Nlog2N) in most cases. For the second algorithm, when the entries in the circulant matrix and the vector take values in C or R, the complexity is O(Nlog2N) in most cases. However, when these entries take values from positive real numbers, the complexity is reduced to O(log3N) in most cases, which presents an exponential speedup compared to the classical complexity of O(NlogN) for computing the product of a circulant matrix and vector. We apply this algorithm to the convolution calculation in quantum convolutional neural networks, which effectively accelerates the computation of convolutions. Additionally, we present a concrete quantum circuit structure for quantum convolutional neural networks.
Toeplitz matrix-vector multiplication is widely used in various fields, including optimal control, systolic finite field multipliers, multidimensional convolution, etc. In this paper, we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity O ( κ polylog n ) , where κ and 2n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix, respectively. For the case with an unknown generating function, we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L 1-norm ρ of the displacement of the structured matrices. Due to the good use of the special properties of Toeplitz matrices, the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.
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.
Matrix multiplication is a fundamental operation in compute-intensive tasks and a key component of modern quantum acceleration frameworks. Here we present a quantum matrix multiplication algorithm based on quantum kernels (QKMM), achieving an elementary gate complexity of O(N2log⁡2N)O(N^2\log_2N)O(N2log2​N), with amplitude encoding overhead explicitly included and without assuming a QRAM oracle. This scaling is asymptotically lower than that of the best-known classical matrix multiplication algorithm O(N2.371339)O(N^{2.371339})O(N2.371339). Building upon QKMM, we establish a family of quantum linear algebra operators, including Quantum Vector Inner Product (V2{\scriptstyle 2}2V), Quantum Vector-Matrix Multiplication (V2{\scriptstyle 2}2M), QKMM (M2{\scriptstyle 2}2M), Quantum One-to-Many Matrix Multiplication(O2{\scriptstyle 2}2M) and Quantum Sequential Matrix Multiplication (SMM), providing a unified framework from vector operations to parallel and sequential matrix transformations. Through noiseless simulations, realistic noise modelling and experiments on a superconducting quantum processor, we systematically characterize the numerical accuracy, resource requirements and hardware execution limits of this operator framework. Furthermore, we integrate SMM into deep neural-network inference, enabling intermediate features to propagate coherently across layers without repeated measurement and re-encoding. These results establish a pathway from quantum circuit-level algorithm design to end-to-end coherent computation, providing a quantum computing framework for matrix-centric compute-intensive applications.
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.
As the most central and computationally intensive component of deep neural networks, the execution efficiency of matrix multiplication directly determines the training and inference performance of models. Harnessing the parallel processing capabilities afforded by quantum superposition and entanglement to reshape matrix multiplication implementations has become a promising entry point for optimising underlying quantum arithmetic logic and improving the operational efficiency of quantum circuits. This paper proposes a universal quantum matrix multiplication (QMM) framework designed to achieve substantial computational acceleration through an optimised quantum arithmetic logic unit. To circumvent the limitations of multi-register and multi-control gates in conventional quantum arithmetic circuits, we encode classical data directly into parameterised RzR_zRz​ rotation gates using the quantum Fourier transform (QFT), thereby reducing the base gate complexity of the quantum adder to O(n)O(n)O(n). In addition, by adopting the column-wise multiplication principle from classical arithmetic, we optimize the gate complexity of the quantum multiplier to O(n2)O(n^2)O(n2). We further extend this approach to a quantum version of the Strassen algorithm, and experimentally quantify the trade-off between reduced multiplication time and increased overhead in addition resources. This work establishes a reliable technical pathway for constructing general-purpose quantum matrix operations, with the potential to unlock substantial computational power for training modern machine learning models.
Abstract In quantum computing, matrix multiplication occurs as a subroutine in more complex algorithms. We improve the quantum linear system algorithm [Harrow et al. 2009 Phys. Rev. Lett. 103 150502] to perform sparse matrix-matrix multiplication and propose a subroutine for parallel vector addition. Based on them, a quantum algorithm is exhibited for N×N positive matrix-positive matrix multiplication. For some small ratio of the maximum element to the minimum element of the positive matrices (i.e.,O(poly logN)), this algorithm achieves exponential acceleration.