Quantum QR decomposition in the computational basis
- PDF / 312,452 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 51 Downloads / 215 Views
Quantum QR decomposition in the computational basis Guangsheng Ma1 · Hongbo Li2 · Jiman Zhao1 Received: 21 November 2019 / Accepted: 17 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we propose a quantum algorithm for approximating the QR decomposition of any N × N matrix with a running time O( 12 N 2.5 polylog(N )), where is the desired precision. This quantum algorithm provides a polynomial speedup over the best classical algorithm, which has a running time O(N 3 ). Our quantum algorithm utilizes the quantum computation in the computational basis (QCCB) and a setting of updatable quantum memory. We further present a systematic approach to applying the QCCB to simulate any quantum algorithm. By this approach, the simulation time does not exceed O(N 2 polylog(N )) times the running time of the quantum algorithm originally designed with the amplitude encoding method, where N is the size of the problem. Keywords Quantum algorithms · Computational basis · Quantum QR decomposition Mathematics Subject Classification 68Q12 · 81P68
H. Li supported by NSFC (Grant No. 11671388), National Key Research Program 2018YFA0704705. J. Zhao supported by National Natural Science Foundation of China (Grant Nos. 11471040 and 11761131002).
B
Jiman Zhao [email protected] Guangsheng Ma [email protected] Hongbo Li [email protected]
1
Key Laboratory of Mathematics and Complex Systems, Ministry of Education, School of Mathematical Sciences, Beijing Normal University, Beijing 100875, China
2
Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China 0123456789().: V,-vol
123
271
Page 2 of 16
G. Ma et al.
1 Introduction Motivated by the work of Harrow et al. [12], many researchers began the study of quantum generalizations of classical matrix analysis tools, such as singular value decomposition [15] and principal component analysis [17]. Nevertheless, how to extend the QR decomposition to the quantum case is still a problem that remains to be solved. QR decomposition, a useful decomposition in matrix analysis, decomposes a matrix A into a product A = Q R of an orthogonal matrix Q and an upper triangular matrix R. In addition to the eigenvalue problem, this decomposition can be used to solve the linear least-square problem. We refer to [6,13,19] for more details. In this paper, we first propose a quantum version of the QR decomposition for any given N × N matrix A with running time O( 12 N 2.5 polylog(N )), where is the desired precision. Our quantum algorithm provides the QR decomposition faster than the best classical algorithm, which has running time1 O(N 3 ) [20]. A remarkable point of our quantum algorithm is the information encoding method. Most existing quantum algorithms encode the input information in the amplitudes of the quantum states (henceforth called the standard quantum algorithms). Examples include Harrow, Hassidim, and Lloyd’s linear system algorithm [12], as well as the quantum machine learning algorithms where the d
Data Loading...
