Quantum algorithm and quantum circuit for A-optimal projection: Dimensionality reduction
Quantum algorithm and quantum circuit for A-optimal projection: Dimensionality reduction
复制标题
A 最优投影的量子算法和量子电路：降维
DOI：
10.1103/physreva.99.032311
复制
发表时间：
2019-03-11
影响因子：
2.9
通讯作者：
Li, Dan
中科院分区：
文献类型：
--
作者：
Duan, Bojia;Yuan, Jiabin;Li, Dan
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.
