We outline refined versions of two major quantum algorithms for performing principal component analysis and solving linear equations. Our methods are exponentially faster than their classical counterparts and even previous quantum algorithms/dequantization algorithms. Oracle/black-box access to classical data is not required, thus implying great capacity for near-term realization. Several applications and implications of these results are discussed. First, we show that a Hamiltonian $H$ with classically known rows/columns can be efficiently simulated, adding another model in addition to the well-known sparse access and linear combination of unitaries models. Second, we provide a simpler proof of the known result that quantum matrix inversion cannot achieve sublinear complexity $κ^{1-γ}$ where $κ$ is the conditional number of the inverted matrix.
We outline refined versions of two major quantum algorithms for performing principal component analysis and solving linear equations. Our methods are exponentially faster than their classical counterparts and even previous quantum algorithms/dequantization algorithms. Oracle/black-box access to classical data is not required, thus implying great capacity for near-term realization. Several applications and implications of these results are discussed. First, we show that a Hamiltonian H with classically known rows/columns can be efficiently simulated, adding another model in addition to the well-known sparse access and linear combination of unitaries models. Second, we provide a simpler proof of the known result that quantum matrix inversion cannot achieve sublinear complexity κ1−γ where κ is the conditional number of the inverted matrix.
Along with the development of quantum technology, finding useful applications of quantum computers has been a central pursuit. Despite various quantum algorithms have been developed, many of them often require strong input assumptions, which is hardware demanding. In particular, recent advances on dequantization have revealed that the quantum advantage is more of a mere artifact of strong input assumptions. In this work, we propose a variant of these algorithms, leveraging both classical and quantum resources. Provided the classical knowledge (the entries) of the matrix/vector of interest, a classical procedure is used to pre-process this information. Then they are fed into a quantum circuit which is shown to be a block encoding of the matrix of interest. From this block-encoding, we show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, preparing ground state, and data fitting. We also analyze our protocol, showing that both the classical and quantum procedure can achieve logarithmic complexity in the input dimension, thus implying its potential for near term realization. We then discuss several implications and corollaries of our result. First,, our results suggest there are certain matrices/Hamiltonians where our method can provide exponential improvement compared to the existing ones with respect to the sparsity. Regarding dense linear systems, our method achieves exponential speed-up with respect to the inverse of error tolerance, compared to the best previously known quantum algorithm for dense systems. Last, and most importantly, regarding quantum data fitting, we show how the output of our quantum algorithms can be leveraged to predict unseen data. Thus, it provides an end-to-end application, which has been an open aspect of the previous quantum data fitting algorithm.
Principal component analysis (PCA) is a significant dimensionality reduction technique for information. Unlike classical PCA, which is demanding in computational resources due to the increase in size and complexity of data, Quantum PCA (QPCA) theoretically can not only achieve the same outcome in an exponentially faster time by optimizing linear algebra in a new and efficient way through the use of quantum physics. Despite QPCA possessing theoretical advantages, the application of QPCA for real-world problems is limited due to quantum hardware capabilities, sensitivity of the algorithm to noise, and efficiency of the approach. New quantum circuit designs, better encoding methods of data and strategies to reduce noise, and other errors mentioned previously, Chapter 3 introduces the idea of combining quantum and classical approaches (Hybrid Quantum Classical PCA) to ameliorate these factors; we will refer to this as a “hybrid approach.” We evaluate HQCPCA with respect to QPCA's best performing algorithms with respect to fidelity, accuracy, run time, QPCA's circuit depth, and noise performance. HQCPCA is an efficient and reliable option for general quantum data processing, as these results indicate reduced circuit depth of 24.5%, a 15.8% increase in execution time, and a 2.9% increase in accuracy as compared to the best-performing algorithms mentioned above.
Abstract Principal component analysis (PCA) is an important dimensionality reduction method in machine learning and data analysis. Recently, the quantum version of PCA has been established to diagonalize quantum states. Although these quantum algorithms promise quantum advantages, they require substantial resources beyond the reach of state-of-the-art quantum technologies. This work aims to reduce resource requirements and improve the efficiency of quantum PCA. Assuming that the quantum state is accessed through a purified quantum query model and a sampling model, we propose quantum algorithms that use minimal resource requirements for ancillary qubits to reveal properties of eigenvectors and eigenvalues of a state. In particular, we show that estimating eigenvalue λ with error ε and success probability larger than λ ( 1 − η ) requests a query complexity O ~ ( ϵ − 1 ) and a sample complexity O ~ ( ϵ − 2 η − 1 ) , respectively. To our knowledge, our result is the first quantum speedup that achieves asymptotic linear scaling in 1 / ϵ for quantum PCA. As applications, we discuss estimating the minimum relative entropy of entanglement of bipartite pure-states and performing quantum state discrimination tasks. We show that quantum speedups are maintained when the pure state has a low Schmidt number and states of discrimination have a low rank. This study opens up a new quantum PCA method for high-dimensional quantum data analysis and discusses its application in quantum information processing tasks.
The machine learning model can infer desired information on processing data sets without being explicitly programmed. It needs refined data to train the perfect model, hence preprocessing is mandatory. The principal component analysis is desired classical existing methods for preprocessing and it requires polynomial time. Now, the research field of computer science is getting influenced by existence of quantum computations, as it supports exponential operations to be performed in parallel over single step of execution. An intrinsic realization of quantum machine provides simultaneous access to either classical or quantum memory. The objective of paper is to understand the importance of data preprocessing and to suggest quantum based solution that takes the advantage of quantum parallelism and thus can obtain computational speedups. So, we contribute to the emergence of quantum computations, processing aspects using quantum accessible memory models and then classical equivalent quantum principal component analysis algorithm. At last we conclude with the mathematical justification over complexity analysis, computational speedups, and prove that quantum algorithms are efficient along with the suggestions of further directions.
This paper presents a sublinear classical algorithm for principal component regression. The algorithm uses quantum-inspired linear algebra, an idea developed by Tang. Using this technique, her algorithm for recommendation systems achieved runtime only polynomially slower than its quantum counterpart. Her work was quickly adapted to solve many other problems in sublinear time complexity. In this work, we developed an algorithm for principal component regression that runs in time polylogarithmic to the number of data points, an exponential speed up over the state-of-the-art algorithm, under the mild assumption that the input is given in some data structure that supports a norm-based sampling procedure. This exponential speed up allows for potential applications in much larger data sets.
We consider the quantum implementations of two classical iterative solvers for a system of linear equations, including the row (Kaczmarz) method which utilizes a row of the coefficient matrix in each iteration step, and the column (coordinate descent) method which uses a column instead. These two methods are widely applied in big data science due to their simple iteration schemes. We propose fast quantum algorithms for these two approaches by constructing efficient unitary operators in each iteration step based on the block-encoding technique. The construction is based on the unitaries to prepare the quantum states of rows or columns of the coefficient matrix. If the quantum states are efficiently prepared, for example, by qRAM, then the quantum iterative methods achieve an exponential speedup in the problem size n over the classical versions. Meanwhile the dependence on the number of steps is linear, which is the same as the classical counterparts. The complexity of the quantum iterative linear solvers is $O({\ensuremath{\kappa}}_{s}^{2}(logn)\left(log\frac{1}{\ensuremath{\epsilon}}\right))$, where ${\ensuremath{\kappa}}_{s}$ is the scaled condition number, and $\ensuremath{\epsilon}$ is the error. The quantum iterative linear solvers do not depend on Hamiltonian simulations and quantum phase estimation, and also work for the dense case.