Resource-efficient quantum principal component analysis

Abstract

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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi>λ</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−</mml:mo> <mml:mi>η</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> requests a query complexity <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mrow> <mml:mrow> <mml:mover> <mml:mi class="MJX-tex-calligraphic">O</mml:mi> <mml:mo class="MJX-tex-calligraphic">~</mml:mo> </mml:mover> </mml:mrow> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mrow> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> and a sample complexity <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mrow> <mml:mrow> <mml:mover> <mml:mi class="MJX-tex-calligraphic">O</mml:mi> <mml:mo class="MJX-tex-calligraphic">~</mml:mo> </mml:mover> </mml:mrow> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mrow> <mml:mo>−</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:msup> <mml:mi>η</mml:mi> <mml:mrow> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> , respectively. To our knowledge, our result is the first quantum speedup that achieves asymptotic linear scaling in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mrow> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:math> 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.