A Low-Complexity Quantum Principal Component Analysis Algorithm

Abstract

In this article, we propose a low-complexity quantum principal component analysis (qPCA) algorithm. Similar to the state-of-the-art qPCA, it achieves dimension reduction by extracting principal components of the data matrix, rather than all components of the data matrix, to quantum registers, so that the samples of measurement required can be reduced considerably. Both our qPCA and Lin’s qPCA are based on quantum singular-value thresholding (QSVT). The key of Lin’s qPCA is to combine QSVT, and modified QSVT is to obtain the superposition of the principal components. The key of our algorithm, however, is to modify QSVT by replacing the rotation-controlled operation of QSVT with the controlled-not operation to obtain the superposition of the principal components. As a result, this small trick makes the circuit much simpler. Particularly, the proposed qPCA requires three phase estimations, while the state-of-the-art qPCA requires five phase estimations. Since the runtime of qPCA mainly comes from phase estimations, the proposed qPCA achieves a runtime of roughly 3/5 of that of the state of the art. We simulate the proposed qPCA on the IBM quantum computing platform, and the simulation result verifies that the proposed qPCA yields the expected quantum state.

Keywords

• Quantum computing
• quantum principal component analysis (qPCA)
• quantum singular-value threshold