Quantum Algorithms to Matrix Multiplication
arXiv:1803.01601
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 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 comment18 pages
References in corpus (16)
- Quantum Machine Learning
- Quantum algorithm for solving linear systems of equations
- Quantum principal component analysis
- Quantum random access memory
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Quantum Data Fitting
- Quantum algorithms for supervised and unsupervised machine learning
- Preconditioned quantum linear system algorithm
- Prediction by linear regression on a quantum computer
- Creating superpositions that correspond to efficiently integrable probability distributions
- A quantum linear system algorithm for dense matrices
- Powers of Tensors and Fast Matrix Multiplication
- Quantum gradient descent for linear systems and least squares
- Quantum Algorithm for Linear Regression
- Universal Quantum Emulator
- From linear combination of quantum states to Grover's searching algorithm
Cited by in corpus (6)
- Quantum Computing and Preconditioners for Hydrological Linear Systems
- A Quantum Model for Multilayer Perceptron
- Quantum subspace alignment for domain adaptation
- Quantum Optical Convolutional Neural Network: A Novel Image Recognition Framework for Quantum Computing
- Hamiltonian singular value transformation and inverse block encoding
- Quantum Higher Order Singular Value Decomposition