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.
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.
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.
Photon system is a promising candidate for quantum information processing, and it can be used to achieve some important tasks with the interaction between a photon and an atom (or a artificial atom), such as the transmission of secret information, the storage of quantum states, and parallel quantum computing. Several degrees of freedom (DOFs) of a photon system can be used to carry information in the realization of quantum information processing, such as the polarization, spatial-mode, orbit-angular-momentum, time-bin, and frequency DOFs. A hyperparallel quantum computer can implement the quantum operations on several DOFs of a quantum system simultaneously, which reduces the operation time and the resources consumed in quantum information processing. The hyperparallel quantum operations are more robust against the photonic dissipation noise than the quantum computing in one DOF of a photon system. Hyperentanglement, defined as the entanglement in several DOFs of a quantum system, can improve the channel capacity and the security of long-distance quantum communication, and it can also be conductive to completing some important tasks in quantum communication. Hyperentangled Bell-state analysis is used to completely distinguish the 16 hyperentangled Bell states, which is very useful in high-capacity quantum communication protocols and quantum repeaters. In order to depress the effect of noises in quantum channel, hyperentanglement concentration and hyperentanglement purification are required to improve the entanglement of the quantum systems in long-distance quantum communication, which is also very useful in high-capacity quantum repeaters. Hyperentanglement concentration is used to distill several nonlocal photon systems in a maximally hyperentangled state from those in a partially hyperentangled pure state, and hyperentanglement purification is used to distill several nonlocal photon systems in a high-fidelity hyperentangled state from those in a mixed hyperentangled state with less entanglement. In this reviewing article, we review some new applications of photon systems with multiple DOFs in quantum information processing, including hyperparallel photonic quantum computation, hyperentangled-Bell-state analysis, hyperentanglement concentration, and hyperentanglement purification.
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.
This paper presents a novel quantum algorithm for matrix multiplication, leveraging quantum superposition and entanglement to achieve significantly enhanced computational speed and quantum advantage compared to classical methods. We propose a unique approach to matrix multiplication based on the quantum state representation of matrices, employing quantum entanglement to dramatically reduce the computational complexity inherent in traditional matrix multiplication. The algorithm demonstrates potential for high-throughput matrix operations, offering a substantial improvement in performance for computationally intensive tasks, particularly within the fields of machine learning and image processing. The proposed method offers a fundamentally new perspective on matrix multiplication, potentially ushering in a new era of quantum computing.
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.