Classical data analysis requires computational efforts that become intractable in the age of Big Data. An essential task in time series analysis is the extraction of physically meaningful information from a noisy time series. One algorithm devised for this very purpose is singular spectrum decomposition (SSD), an adaptive method that allows for the extraction of narrow-banded components from non-stationary and non-linear time series. The main computational bottleneck of this algorithm is the singular value decomposition (SVD). Quantum computing could facilitate a speedup in this domain through superior scaling laws. We propose quantum SSD by assigning the SVD subroutine to a quantum computer. The viability for implementation and performance of this hybrid algorithm on a near term hybrid quantum computer is investigated. In this work, we show that by employing randomized SVD, we can impose a qubit limit on one of the circuits to improve scalibility. Using this, we efficiently perform quantum SSD on simulations of local field potentials recorded in brain tissue, as well as GW150914, the first detected gravitational wave event.
Classical data analysis requires computational efforts that become intractable in the age of Big Data. An essential task in time series analysis is the extraction of physically meaningful information from a noisy time series. One algorithm devised for this very purpose is singular spectrum decomposition (SSD), an adaptive method that allows for the extraction of narrow-banded components from non-stationary and non-linear time series. The main computational bottleneck of this algorithm is the singular value decomposition (SVD). Quantum computing could facilitate a speedup in this domain through superior scaling laws. We propose quantum SSD by assigning the SVD subroutine to a quantum computer. The viability for implementation and performance of this hybrid algorithm on a near term hybrid quantum computer is investigated. In this work, we show that by employing randomized SVD, we can impose a qubit limit on one of the circuits to improve scalibility. Using this, we efficiently perform quantum SSD on simulations of local field potentials recorded in brain tissue, as well as GW150914, the first detected gravitational wave event.
This research paper explores the application of singular value decomposition (SVD) in quantum image processing (QIP), specifically focusing on the computation of eigenvalues using variational quantum algorithms. SVD is a powerful mathematical tool in image processing, used for tasks such as image compression, noise reduction, and feature extraction. In this study, we propose quantum variational singular value decomposition (QVSVD) based on the variational quantum deflation (VQD) algorithm to determine the eigenvalues that contributes in calculating the singular values of the image matrix and eventually doing the SVD. This facilitates the extraction of eigenvalues with exponential speedup on real hardware compared to classical methods. We detail the implementation of this quantum algorithm within the framework of QIP, highlighting its advantages in terms of computational efficiency and accuracy on a Fault-Tolerant Quantum Computing (FTQC). Furthermore, we present a comparative analysis of the quantum and the classical method of SVD, demonstrating the accuracy of the image data. The simulation results validate the theoretical advantages of using quantum algorithms for SVD in image processing. This work not only underscores the potential of quantum computing in enhancing image processing techniques but also sets the stage for future research in the field, exploring more complex image processing tasks and other quantum algorithms. Our findings suggest that quantum image processing can offer unprecedented capabilities, paving the way for advancements in various applications such as medical imaging, remote sensing, and multimedia processing.
The dynamic mode decomposition (DMD) algorithm is a widely used factorization and dimensionality reduction technique in time series analysis. When analyzing high-dimensional time series, the DMD algorithm requires extremely large amounts of computational power. To accelerate the DMD algorithm, we propose a quantum-classical hybrid algorithm that we call the quantum dynamic mode decomposition (QDMD) algorithm. Given a time series X ∈ R n × ( m + 1) with n ≫ m , the QDMD algorithm first executes quantum singular value decomposition on a matrix related to X and obtains a quantum state containing the main singular values and singular vectors of the decomposed matrix, then performs a low-sampling-frequency process on the obtained quantum state and computes the low-dimensional projection of the DMD operator through the sampling results. Finally, the algorithm computes the DMD eigenvalues and prepares the amplitude-encoding states of the DMD modes using the obtained classical information and X . Considering the main variables, the complexity of the QDMD algorithm is O ~ M m polylog n / ϵ , where M = O ~ m 3 / ϵ 2 denotes the number of samples. Compared with the classical DMD algorithm, which has complexity O ~ n m 2 log 1 / ϵ , the QDMD algorithm provides an exponential acceleration of n , at the cost of greater dependence on M and ϵ . We test the effects of M on the QDMD algorithm in the specific application scenarios of data denoising, scene background extraction, and fluid dynamics analysis. We determined that the QDMD algorithm requires only a small number of samples M in specific applications, further demonstrating the quantum advantage of the QDMD algorithm in high-dimensional data analysis.
Singular Value Decomposition (SVD) is one of the most useful techniques for analyzing data in linear algebra. SVD decomposes a rectangular real or complex matrix into two orthogonal matrices and one diagonal matrix. The proposed Quantum-SVD algorithm interpolates the non-uniform angles in the Fourier domain. The error of the Quantum-SVD approach is some orders lower than the error given by ordinary Quantum Fourier Transformation. Our Quantum-SVD algorithm is a fundamentally novel approach for the computation of the Quantum Fourier Transformation (QFT) of non-uniform states. The presented Quantum-SVD algorithm is based on the singular value decomposition mechanism, and the computation of Quantum Fourier Transformation of non-uniform angles of a quantum system. The Quantum-SVD approach provides advantages in terms of computational structure, being based on QFT and multiplications.
Abstract Tensors are increasingly ubiquitous in various areas of applied mathematics and computing, and tensor decompositions are of practical significance and benefit many applications in data completion, image processing, computer vision, collaborative filtering, etc. Recently, Kilmer and Martin propose a new tensor factorization strategy, tensor singular value decomposition (t-svd), which extends the matrix singular value decomposition to tensors. However, computing t-svd for high dimensional tensors costs much computation and thus cannot efficiently handle large scale datasets. Motivated by advantage of quantum computation, in this paper, we present a quantum algorithm of t-svd for third-order tensors and then extend it to order-p tensors. We prove that our quantum t-svd algorithm for a third-order N dimensional tensor runs in time N polylog ( N ) if we do not recover classical information from the quantum output state. Moreover, we apply our quantum t-svd algorithm to context-aware multidimensional recommendation systems, where we just need to extract partial classical information from the quantum output state, thus achieving low time complexity.
Abstract Researchers have put a lot of effort into reducing the gap between current quantum processing units (QPU) capabilities and their potential supremacy.One approach is to keep supplementary computations in the CPU, and use QPU only for the core of the problem. In this work, we address the complexity of quantum algorithm of arbitrary quantum state initialization, an important building block of quantum data analysis and machine learning.QPUs do not outperform classical machines with existing precise initialization algorithms.Hence, many studies propose an approximate but robust quantum state initialization.Cutting a quantum state into a product of (almost) independent partitions with the help of CPU reduces the number of two-qubit gates, and correspondingly minimizes the loss of state fidelity in the quantum part of the algorithm.To find the least entangled qubits, current methods compute the singular value decomposition (SVD) for each qubit separately with CPU.In this paper, we optimize CPU usage and memory resource bottlenecks.We consider Tucker tensor decomposition as an alternative to the CPU-based SVD in a single low-entangled qubit detection task without the loss of solution quality.Both proposed methods outperform the SVD in time and memory for systems of at least ten qubits. We achieve an order faster implementation and two orders less memory usage for a system of 15 qubits.
Singular value decomposition is central to many problems in engineering and scientific fields. Several quantum algorithms have been proposed to determine the singular values and their associated singular vectors of a given matrix. Although these algorithms are promising, the required quantum subroutines and resources are too costly on near-term quantum devices. In this work, we propose a variational quantum algorithm for singular value decomposition (VQSVD). By exploiting the variational principles for singular values and the Ky Fan Theorem, we design a novel loss function such that two quantum neural networks (or parameterized quantum circuits) could be trained to learn the singular vectors and output the corresponding singular values. Furthermore, we conduct numerical simulations of VQSVD for random matrices as well as its applications in image compression of handwritten digits. Finally, we discuss the applications of our algorithm in recommendation systems and polar decomposition. Our work explores new avenues for quantum information processing beyond the conventional protocols that only works for Hermitian data, and reveals the capability of matrix decomposition on near-term quantum devices.