  Learning low dimensional representation is a crucial issue for many machine
learning tasks such as pattern recognition and image retrieval. In this
article, we present a quantum algorithm and a quantum circuit to efficiently
perform A-Optimal Projection for dimensionality reduction. Compared with the
best-know classical algorithms, the quantum A-Optimal Projection (QAOP)
algorithm shows an exponential speedup in both the original feature space
dimension $n$ and the reduced feature space dimension $k$. We show that the
space and time complexity of the QAOP circuit are $O\left[ {{{\log }_2}\left(
{nk} /{\epsilon} \right)} \right]$ and $O[ {\log_2(nk)} {poly}\left({{\log
}_2}\epsilon^{-1} \right)]$ respectively, with fidelity at least $1-\epsilon$.
Firstly, a reformation of the original QAOP algorithm is proposed to help omit
the quantum-classical interactions during the QAOP algorithm. Then the quantum
algorithm and quantum circuit with performance guarantees are proposed.
Specifically, the quantum circuit modules for preparing the initial quantum
state and implementing the controlled rotation can be also used for other
quantum machine learning algorithms.
