[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Quantum regularized least squares solver with parameter estimate

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

For ill-conditioned least squares problems, regularization techniques such as Tikhonov regularization are the key ingredients to obtain meaningful solutions, and the determination of the proper regularization parameter is the most difficult step. This paper focuses on the choice of regularization parameter on a quantum computer. We combine the classical L-curve or Hanke–Raus rule with the HHL algorithm and quantum amplitude estimation that compute the regularized solution and the corresponding residual and their norms. When a series of regularization parameters are tested, we then apply Grover’s search algorithm to find the best one that gives the meaningful solution. This yields a quadratic speedup in the number of regularization parameters.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Actually \(\tau =C\), since if \(\mu \) is small, then \(C=\tilde{\sigma }_{\min }/\sigma _{\max } =\sqrt{\sigma _{\min }^2+\mu ^2}/\sigma _{\max } \le 1\) generally.

  2. The linear system \(Ax=b\) arises from the example Shaw in the regularization tools [31], where the matrix A is of order 1000 and right-hand size b has a noise level \(10^{-2}\). Each cross-marker corresponds to a certain \(\mu \).

References

  1. Banks, H., Kunisch, K.: Parameter Estimation Techniques for Distributed Systems. Birkhäuser, Boston (1989)

    Book  Google Scholar 

  2. Engl, H.W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Kluwer, Dordrecht (1996)

    Book  Google Scholar 

  3. Hansen, P.C.: Discrete Inverse Problems, Insight and Applications. SIAM, Philadelphia (2010)

    Book  Google Scholar 

  4. Tikhonov, A., Arsenin, V.: Solutions of Ill-Posed Problems. Wiley, New York (1977)

    MATH  Google Scholar 

  5. Haykin, S.O.: Neural Networks and Learning Machine, 3rd edn. Pearson, London (2008)

    Google Scholar 

  6. Xiang, H., Zou, J.: Randomized algorithms for large-scale inverse problems with general Tikhonov regularizations. Inverse Prob. 31, 085008 (2015)

    Article  ADS  MathSciNet  Google Scholar 

  7. Hansen, P.C.: Analysis of discrete ill-posed problems by means of the L-curve. SIAM Rev. 34, 561–580 (1992)

    Article  MathSciNet  Google Scholar 

  8. Hansen, P.C., O’Leary, D.P.: The use of the L-curve in the regularization of discrete ill-posed problems. SIAM J. Sci. Comput. 14, 1487–1503 (1993)

    Article  MathSciNet  Google Scholar 

  9. Hanke, M., Raus, T.: A general heuristic for choosing the regularization parameter in ill-posed problems. SIAM J. Sci. Comput. 17, 956–972 (1996)

    Article  MathSciNet  Google Scholar 

  10. Golub, G.H., Heath, M., Wahba, G.: Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics 21, 215–223 (1979)

    Article  MathSciNet  Google Scholar 

  11. Xiang, H., Zou, J.: Regularization with randomized SVD for large-scale discrete inverse problems. Inverse Probl. 29, 085008 (2013)

    Article  ADS  MathSciNet  Google Scholar 

  12. Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for solving linear systems of equations. Phys. Rev. Lett. 15(103), 150502 (2009)

    Article  Google Scholar 

  13. Brassard, G., Høyer, P., Mosca, M.: Quantum amplitude amplification and estimation. Quantum Comput. Quantum Inf. 305, 53–74 (2002)

    MathSciNet  MATH  Google Scholar 

  14. Dürr, D., Høyer, P.: A quantum algorithm for finding the minimum. arXiv:quant-ph/9607014 (1996)

  15. Wiebe, N., Braun, D., Lloyd, S.: Quantum algorithm for data fitting. Phys. Rev. Lett. 109, 050505 (2012)

    Article  ADS  Google Scholar 

  16. Schuld, M., Sinayskiy, I., Petruccione, F.: Prediction by linear regression on a quantum computer. Phys. Rev. A 94, 022342 (2016)

    Article  ADS  Google Scholar 

  17. Chakraborty, S., Gilyén, A., Jeffery, S.: The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. in: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), pp. 33:1–33:14 (2019)

  18. Kerenidis, I., Prakash, A.: Quantum gradient descent for linear systems and least squares. arXiv:1704.04992v3 (2017)

  19. Wang, G.M.: Quantum algorithm for linear regression. Phys. Rev. A 96, 012335 (2017)

    Article  ADS  MathSciNet  Google Scholar 

  20. Liu, Y., Zhang, S.Y.: Fast quantum algorithms for least squares regression and statistic leverage scores. Theoret. Comput. Sci. 657, 38–47 (2017)

    Article  MathSciNet  Google Scholar 

  21. Li, G.X., Wang, Y.L., Luo, Y., Feng, Y.: Quantum data fitting algorithm for non-sparse matrices. arXiv:1907.06949 (2019)

  22. Yu, C.H., Gao, F., Wen, Q.Y: An improved quantum algorithm for ridge regression. arXiv:1707.09524 (2017)

  23. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)

    MATH  Google Scholar 

  24. Rieffel, E., Polak, W.: Quantum Computing—A Gentle Introduction. The MIT Press, Cambridge (2011)

    MATH  Google Scholar 

  25. Wossnig, L., Zhao, Z.K., Prakash, A.: A quantum linear system algorithm for dense matrices. Phys. Rev. Lett. 120, 050502 (2018)

    Article  ADS  MathSciNet  Google Scholar 

  26. Childs, A.M., Kothari, R., Somma, R.D.: Quantum linear systems algorithm with exponentially improved dependence on precision. SIAM J. Comput. 46, 1920–1950 (2017)

    Article  MathSciNet  Google Scholar 

  27. Clader, B.D., Jacobs, B.C., Sprouse, C.R.: Preconditioned quantum linear system algorithm. Phys. Rev. Lett. 110, 250504 (2013)

    Article  ADS  Google Scholar 

  28. Shao, C., Xiang, H.: Quantum circulant preconditioner for a linear system of equations. Phys. Rev. A 98, 062321 (2018)

    Article  ADS  Google Scholar 

  29. Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett. 87, 167902 (2001)

    Article  ADS  Google Scholar 

  30. Childs, A.M., Maslov, D., Nam, Y., Ross, N.J., Su, Y.: Toward the first quantum simulation with quantum speedup. arXiv:1711.10980 (2017)

  31. Hansen, P.C.: Regularization tools: a Matlab package for analysis and solution of discrete ill-posed problems. Numer. Algorithms 6, 1–15 (1994)

    Article  ADS  MathSciNet  Google Scholar 

  32. Gross, D., Liu, Y.K., Flammia, S.T., Becker, S., Eisert, J.: Quantum state tomography visa compressed sensing. Phys. Rev. Lett. 105, 150401 (2010)

    Article  ADS  Google Scholar 

  33. Shabani, A., Kosut, R.L., Mohseni, M., Rabitz, H., Broome, M.A., Almeida, M.P., Fedrizzi, A., White, A.G.: Efficient measurement of quantum dynamics visa compressive sensing. Phys. Rev. Lett. 106, 100401 (2011)

    Article  ADS  Google Scholar 

  34. Shabani, A., Mohseni, M., Lloyd, S., Kosut, R.L., Rabitz, H.: Estimation of many-body quantum Hamiltonians visa compressive sensing. Phys. Rev. A 84, 012107 (2011)

    Article  ADS  Google Scholar 

Download references

Acknowledgements

HX is supported by the Natural Science Foundation of China under Grants 11571265 and NSFC-RGC No. 11661161017. CS was supported by the QuantERA ERA-NET Cofund in Quantum Technologies implemented within the European Union’s Horizon 2020 Programme (QuantAlgo Project), and EPSRC Grants EP/L021005/1 and EP/R043957/1. No new data were created during this study.

Author information

Authors and Affiliations

  1. School of Mathematics, University of Bristol, Bristol, BS8 1UG, UK

    Changpeng Shao

  2. School of Mathematics and Statistics, Wuhan University, Wuhan, 430072, China

    Hua Xiang

  3. Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan, 430072, China

    Hua Xiang

Authors
  1. Changpeng Shao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hua Xiang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hua Xiang.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

Appendix A: The procedure of HHL algorithm to generate state (12)

Suppose the SVD of \({\widetilde{A}}_\mu =\sum _j \tilde{\sigma }_j|\tilde{u}_j\rangle \langle \tilde{u}_j|\), and the smallest nonzero singular value is represented by \(\tilde{\sigma }_{\min }\). We formally decompose \(|\tilde{b}\rangle =\sum _j \tilde{\beta }_j |\tilde{u}_j\rangle \). Then by QPE, we obtain

$$\begin{aligned} \sum _j \tilde{\beta }_j |\tilde{u}_j\rangle |\tilde{\sigma }_j\rangle . \end{aligned}$$

Denote \({\widetilde{C}}\) as a lower bound of \(\sigma _{\min }\), and define \(f(z) = \arccos ({\widetilde{C}}/z)\), then apply \(U_f\) to the above state to get

$$\begin{aligned} \sum _j \tilde{\beta }_j |\tilde{u}_j\rangle \left| \tilde{\sigma }_j\right\rangle \left| \arccos \left( {\widetilde{C}}/\tilde{\sigma }_j\right) \right\rangle . \end{aligned}$$

Now use control rotation to generate

$$\begin{aligned} \sum _j \tilde{\beta }_j |\tilde{u}_j\rangle \left| \tilde{\sigma }_j\right\rangle \left| \arccos \left( {\widetilde{C}}/ \tilde{\sigma }_j\right) \right\rangle \left[ \frac{{\widetilde{C}}}{\tilde{\sigma }_j}|0\rangle + \sqrt{1- \frac{{\widetilde{C}}^2}{\tilde{\sigma }^2_j}} |1\rangle \right] . \end{aligned}$$

At last, undo \(U_f\) and QPE, then we have

$$\begin{aligned} \sum _j \tilde{\beta }_j |\tilde{u}_j\rangle \left[ {\widetilde{C}}\tilde{\sigma }_j^{-1}|0\rangle + \sqrt{1- {\widetilde{C}}^2\tilde{\sigma }_j^{-2}} |1\rangle \right] = {\widetilde{C}} \Vert x_\mu \Vert |x_\mu \rangle |0\rangle + P_1 |\phi _1\rangle |1\rangle . \end{aligned}$$

Appendix B: Multiply A on state (12)

Denote the SVD of \(A=\sum _j \sigma _j |u_j\rangle \langle v_j|\), then the eigenvalue decomposition of \({\widetilde{A}} = \left( \begin{array}{c@{\quad }c} 0 &{} A \\ A^\dag &{} 0 \\ \end{array} \right) \) is \(\sum _j \pm \sigma _j |w_j^\pm \rangle \langle w_j^{\pm }|\), where \(|w_j^\pm \rangle = \frac{1}{\sqrt{2}}(|0\rangle |u_j\rangle \pm |1\rangle |v_j\rangle )\).

Formally, we can rewrite \(|1,x_\mu \rangle = \sum _j x_{\mu ,j}|1,v_j\rangle = \sum _j \frac{x_{\mu ,j} }{\sqrt{2}}(|w_j^+\rangle -|w_j^-\rangle )\). Then

$$\begin{aligned} |1,X_\mu \rangle = {\widetilde{C}} \Vert x_\mu \Vert \sum _j \frac{x_{\mu ,j} }{\sqrt{2}}\left( |w_j^+\rangle -|w_j^-\rangle \right) |0\rangle + P_1 |0,\phi _1\rangle |1\rangle . \end{aligned}$$

By viewing \(|0\rangle \) in the third register as control qubit, we perform QPE to \(\hbox {e}^{\mathbf{i}t_0 {\widetilde{A}}}\) with initial state \(|1,X_\mu \rangle \), then we obtain

$$\begin{aligned} {\widetilde{C}} \Vert x_\mu \Vert \sum _j \frac{x_{\mu ,j} }{\sqrt{2}}(|w_j^+\rangle |\sigma _j\rangle -|w_j^-\rangle |-\sigma _j\rangle ) |0\rangle + P_1 |0,\phi _1\rangle |1\rangle . \end{aligned}$$

Denote \(f(z) = \arccos (z/{\widehat{C}})\), where \({\widehat{C}}\) is a upper bound of \(\sigma _{\max }\). Apply \(U_f\) to the above state to prepare

$$\begin{aligned} {\widetilde{C}} \Vert x_\mu \Vert \sum _j \frac{x_{\mu ,j} }{\sqrt{2}}\left( |w_j^+\rangle |\sigma _j\rangle \left| \arccos \left( \frac{\sigma _j}{{\widehat{C}}}\right) \right\rangle - |w_j^-\rangle |-\sigma _j\rangle \left| \arccos \left( -\frac{\sigma _j}{{\widehat{C}}}\right) \right\rangle \right) |0\rangle + P_1 |0,\phi _1\rangle |1\rangle . \end{aligned}$$

Now apply control rotation to generate

$$\begin{aligned}&\displaystyle {\widetilde{C}} \Vert x_\mu \Vert \sum _j \frac{x_{\mu ,j} }{\sqrt{2}}\left( |w_j^+\rangle |\sigma _j\rangle \left| \arccos \left( \frac{\sigma _j}{{\widehat{C}}}\right) \right\rangle \otimes \left[ \frac{\sigma _j}{{\widehat{C}}} |0\rangle + \sqrt{1- \frac{\sigma _j^2}{{\widehat{C}}^2}} |1\rangle \right] \right. \\&\quad \left. \displaystyle -\, |w_j^-\rangle |-\sigma _j\rangle \left| \arccos \left( -\frac{\sigma _j}{{\widehat{C}}}\right) \right\rangle \otimes \, \left[ -\frac{\sigma _j}{{\widehat{C}}} |0\rangle + \sqrt{1- \frac{\sigma _j^2}{{\widehat{C}}^2}} |1\rangle \right] \right) |0\rangle + P_1 |0,\phi _1\rangle |1\rangle . \end{aligned}$$

Finally, undo \(U_f\) and QPE we obtain

$$\begin{aligned}&\displaystyle \frac{{\widetilde{C}}}{{\widehat{C}}} \Vert x_\mu \Vert \sum _j \frac{x_{\mu ,j}}{\sqrt{2}} \sigma _j (|w_j^+\rangle +|w_j^-\rangle ) |0,0\rangle + {\text {orthogonal terms}} \nonumber \\&\quad = \displaystyle \frac{{\widetilde{C}}}{{\widehat{C}}} \Vert x_\mu \Vert \sum _j x_{\mu ,j} \sigma _j |0,u_j\rangle |0,0\rangle + \, {\text {orthogonal terms}} \nonumber \\&\quad = \displaystyle \frac{{\widetilde{C}}}{{\widehat{C}}} \Vert x_\mu \Vert |0\rangle A |x_\mu \rangle |0,0\rangle + \, \mathrm{orthogonal~terms}. \end{aligned}$$
(22)

Therefore, there is a unitary that maps \(|1,X_\mu \rangle \) to state (22). The first qubit \(|0\rangle \) is ancillary.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shao, C., Xiang, H. Quantum regularized least squares solver with parameter estimate. Quantum Inf Process 19, 113 (2020). https://doi.org/10.1007/s11128-020-2615-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-020-2615-9

Keywords