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.
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.
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.
Abstract Solving linear systems of equations is of vital importance in various fields of science. With the scale of calculation soaring, classical computers are intractable, and the advantage of quantum computing is reflected. Quantum algorithm has exponential acceleration in solving the linear systems A x ⃗ = b ⃗ for sparse and well-conditioned coefficient matrix A with dimension N × N . In this paper, we present a quantum algorithm to solve matrix equations of the form AX = B , where X = ( x ⃗ 1 , x ⃗ 2 , … , x ⃗ n ) , B = ( b ⃗ 1 , b ⃗ 2 , … , b ⃗ n ) , x ⃗ k and b ⃗ k are unit vectors. The problem can be intuitively treated as solving n linear systems simultaneously, which will needs O ( n log N ) complexity by the famous HHL algorithm. We demonstrate that in our algorithm the scale of complexity is O ( log n N ) . In the error analysis part, phase estimation is discussed in details.
Harrow, Hassidim, and Lloyd [ Phys. Rev. Lett., 103 (2009), 150502] showed that for a suitably specified N×N matrix A and an N-dimensional vector b, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations Ax=b. If A is sparse and well-conditioned, their algorithm runs in time poly(logN,1/ϵ), where ϵ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log(1/ϵ), exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on ϵ is prohibitive.
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(N2log2N), 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). Building upon QKMM, we establish a family of quantum linear algebra operators, including Quantum Vector Inner Product (V2V), Quantum Vector-Matrix Multiplication (V2M), QKMM (M2M), Quantum One-to-Many Matrix Multiplication(O2M) 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.
This paper explores a novel approach to accelerating matrix multiplication by leveraging the principles of quantum state superposition. Traditional matrix multiplication is computationally intensive, particularly for large matrices, and is a core component of many scientific and engineering applications. We propose a hardware acceleration strategy that maps the matrix multiplication process onto a quantum circuit exploiting the inherent parallelism offered by quantum superposition. The core idea involves representing matrix elements as quantum states and performing the multiplication operations using controlled quantum gates. This approach aims to potentially achieve exponential speedups compared to classical algorithms. We detail the theoretical framework, outlining the quantum circuit design, and discuss the key challenges and potential improvements associated with this methodology. The primary focus is on the algorithmic design and conceptual framework rather than experimental validation, offering a foundational exploration of this concept.