  Data compression can be achieved by reducing the dimensionality of
high-dimensional but approximately low-rank datasets, which may in fact be
described by the variation of a much smaller number of parameters. It often
serves as a preprocessing step to surmount the curse of dimensionality and to
gain efficiency, and thus it plays an important role in machine learning and
data mining. In this paper, we present a quantum algorithm that compresses an
exponentially large high-dimensional but approximately low-rank dataset in
quantum parallel, by dimensionality reduction (DR) based on principal component
analysis (PCA), the most popular classical DR algorithm. We show that the
proposed algorithm achieves exponential speedup over the classical PCA
algorithm when the original dataset are projected onto a polylogarithmically
low-dimensional space. The compressed dataset can then be further processed to
implement other tasks of interest, with significantly less quantum resources.
As examples, we apply this algorithm to reduce data dimensionality for two
important quantum machine learning algorithms, quantum support vector machine
and quantum linear regression for prediction. This work demonstrates that
quantum machine learning can be released from the curse of dimensionality to
solve problems of practical importance.
