Abstract
In this paper, we propose a quantum algorithm for approximating the QR decomposition of any \(N\times N\) matrix with a running time \(O(\frac{1}{\epsilon ^2}\) \(N^{2.5}\text {polylog}(N))\), where \(\epsilon \) 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\text {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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
Generally, the time required to compute the QR decomposition of an \(N\times N\) matrix is O\((N^3)\); unless, the matrix has some special structures, such as Vandermonde-like form.
The approach to efficiently implementing the conditional rotations can be found in [25, Lemma 2]
References
Ahuja, A., Kapoor, S.: A quantum algorithm for finding the maximum. arXiv:quant-ph/9911082 (1999)
Berry, D.W., Childs, A.M., Kothari, R.: Hamiltonian simulation with nearly optimal dependence on all parameters. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 792–809. IEEE (2015)
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., Lloyd, S.: Quantum machine learning. Nature 549(7671), 195 (2017)
Brassard, G., Høyer, P., Tapp, A.: Quantum counting. In: International Colloquium on Automata, Languages, and Programming, pp. 820–831. Springer (1998)
Buhrman, H., Cleve, R., Watrous, J., De Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett. 87(16), 167902 (2001)
Businger, P., Golub, G.H.: Linear least squares solutions by householder transformations. Numer. Math. 7(3), 269–276 (1965)
Chakraborty, S., Gilyén, A., Jeffery, S.: The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. arXiv:1804.01973 (2018)
Childs, A.M., Wiebe, N.: Hamiltonian simulation using linear combinations of unitary operations. Quantum Inf. Comput. 12(11–12), 901–924 (2012)
Clader, B.D., Jacobs, B.C., Sprouse, C.R.: Preconditioned quantum linear system algorithm. Phys. Rev. Lett. 110(25), 250504 (2013)
Dawson, C.M., Nielsen, M.A.: The Solovay–Kitaev algorithm. Quantum Inf. Comput. 6(1), 81–95 (2006)
Gilyén, A., Su, Y., Low, G.H., Wiebe, N.: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193–204. ACM (2019)
Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15), 150502 (2009)
Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (2012)
Kerenidis, I., Prakash, A.: Quantum gradient descent for linear systems and least squares. arXiv:1704.04992 (2017)
Kerenidis, I., Prakash, A.: Quantum recommendation systems. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)
Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411 (2013)
Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum principal component analysis. Nat. Phys. 10(9), 631 (2014)
Nielsen, M.E., Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Parlett, B.N.: The QR algorithm. Comput. Sci. Eng. 2(1), 38 (2000)
Reichel, L.: Fast QR decomposition of vandermonde-like matrices and polynomial least squares approximation. SIAM J. Matrix Anal. Appl. 12(3), 552–564 (1991)
Schuld, M., Sinayskiy, I., Petruccione, F.: An introduction to quantum machine learning. Contemp. Phys. 56(2), 172–185 (2015)
Shao, C.: From linear combination of quantum states to Grover’s searching algorithm. arXiv:1807.09693 (2018)
Shao, C.: A quantum model for multilayer perceptron. arXiv:1808.10561 (2018)
Shao, C., Li, Y., Li, H.: Quantum algorithm design: techniques and applications. J. Syst. Sci. Complex. 32(1), 375–452 (2019)
Wang, C., Wossnig, L.: A quantum algorithm for simulating non-sparse Hamiltonians. arXiv:1803.08273 (2018)
Wossnig, L., Zhao, Z., Prakash, A.: Quantum linear system algorithm for dense matrices. Phys. Rev. Lett. 120(5), 050502 (2018)
Zhou, S., Loke, T., Izaac, J.A., Wang, J.B.: Quantum Fourier transform in computational basis. Quantum Inf. Process. 16(3), 82 (2017)
Acknowledgements
We thank the reviewers for their constructive and valuable suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
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).
Rights and permissions
About this article
Cite this article
Ma, G., Li, H. & Zhao, J. Quantum QR decomposition in the computational basis. Quantum Inf Process 19, 271 (2020). https://doi.org/10.1007/s11128-020-02777-4
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11128-020-02777-4