Multiple linear regression assumes an imperative role in supervised machine learning. In 2009, Harrow et al. [Phys. Rev. Lett. 103, 150502 (2009)] showed that their Harrow Hassidim Lloyd (HHL) algorithm can be used to sample the solution of a linear system $A x = b$ exponentially faster than any existing classical algorithm. The entire field of quantum machine learning gained considerable traction after the discovery of this celebrated algorithm. However, effective practical applications and experimental implementations of HHL are still sparse in the literature. Here, the authors demonstrate a potential practical utility of HHL, in the context of regression analysis, using the remarkable fact that there exists a natural reduction of any multiple linear regression problem to an equivalent linear systems problem. They put forward a 7-qubit quantum circuit design, motivated from an earlier work by Cao et al. [Mol. Phys. 110, 1675 (2012)], to solve a three-variable regression problem, using only elementary quantum gates. They also implement the group leaders optimisation algorithm (GLOA) [Mol. Phys. 109 (5), 761 (2011)] and elaborate on the advantages of using such stochastic algorithms in creating low-cost circuit approximations for the Hamiltonian simulation. Further, they discuss their Qiskit simulation and explore certain generalisations to the circuit design.

References

1. 1)
  - 1. Nielsen, M.A., Chuang, I.L.: ‘Quantum computation and quantum information: 10th anniversary edition’ (Cambridge University Press, New York, USA, 2010).
2. 2)
  - 4. Harrow, A.W., Hassidim, A., Lloyd, S.: ‘Quantum algorithm for linear systems of equations’, Phys. Rev. Lett., 2009, 103, (15), p. 150502.
3. 3)
  - 27. Al-Mohy, A.H., Higham, N.J.: ‘A new scaling and squaring algorithm for the matrix exponential’, SIAM J. Matrix Anal. Appl., 2010, 31, pp. 970–989.
4. 4)
  - 30. The MathWorks Inc.: ‘Matlab Mathematics R2018b’ (2018).
5. 5)
  - 28. Higham, N.J.: ‘The scaling and squaring method for the matrix exponential revisited’, SIAM J. Matrix Anal. Appl., 2005, 26, (4), pp. 1179–1193.
6. 6)
  - 33. Kitaev, A.Y., Yu Kitaev, A.: ‘Quantum computations: algorithms and error correction’, Russian Math. Surv., 1997, 52, pp. 1191–1249.
7. 7)
  - 20. Ambainis, A.: ‘Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations’, arXiv 1010.4458 [quant-ph], 2010.
8. 8)
  - 16. Aaronson, S.: ‘Read the fine print’, Nat. Phys., 2015, 11, (4), pp. 291–293.
9. 9)
  - 35. Raeisi, S., Wiebe, N., Sanders, B.C.: ‘Quantum-circuit design for efficient simulations of many-body quantum dynamics’, New J. Phys., 2012, 14, (10), p. 103017.
10. 10)
  - 25. Jones, E., Oliphant, T., Peterson, P.: ‘Scipy: open source scientific tools for python’, 2001.
11. 11)
  - 31. Niesen, J., Wright, W.M.: ‘Algorithm 919’, ACM Trans. Math. Softw., 2012, 38, (3), pp. 1–19.
12. 12)
  - 14. Childs, A.M., Kothari, R., Somma, R.D.: ‘Quantum algorithm for systems of linear equations with exponentially improved dependence on precision’, SIAM J. Comput., 2017, 46, (6), pp. 1920–1950.
13. 13)
  - 8. Kandala, A., Mezzacapo, A., Temme, K., et al: ‘Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets’, Nature, 2017, 549, (7671), pp. 242–246.
14. 14)
  - 13. Biamonte, J., Wittek, P., Pancotti, N., et al: ‘Quantum machine learning’, Nature, 2017, 549, (7671), pp. 195–202.
15. 15)
  - 18. Pan, J., Cao, Y., Yao, X., et al: ‘Experimental realization of quantum algorithm for solving linear systems of equations’, Phys. Rev. A, 2014, 89, (2), p. 022313.
16. 16)
  - 9. Srinivasan, K., Satyajit, S., Behera, B.K., et al: ‘Efficient quantum algorithm for solving travelling salesman problem: an IBM quantum experience’, arXiv 1805.10928 [quant-ph], 2018.
17. 17)
  - 19. Hestenes, M.R., Stiefel, E.: ‘Methods of conjugate gradients for solving linear systems’, J. Res. Natl. Bur. Stand., 1952, 49, (6), pp. 409–436.
18. 18)
  - 36. Somma, R.D.: ‘A Trotter-Suzuki approximation for lie groups with applications to Hamiltonian simulation’, J. Math. Phys., 2016, 57, (6), p. 062202.
19. 19)
  - 11. Maji, R., Behera, B.K., Panigrahi, P.K.: ‘Solving linear systems of equations by using the concept of Grover's search algorithm: an IBM quantum experience’, arXiv 1801.00778 [quant-ph], 2017.
20. 20)
  - 15. Dervovic, D., Herbster, M., Mountney, P., et al: ‘Quantum linear systems algorithms: a primer’, arXiv 1802.08227 [quant-ph], 2018.
21. 21)
  - 2. Lloyd, S.: ‘Universal quantum simulators’, Science, 1996, 273, (5278), pp. 1073–1078.
22. 22)
  - 7. Peruzzo, A., McClean, J., Shadbolt, P., et al: ‘A variational eigenvalue solver on a photonic quantum processor’, Nat. Commun., 2014, 5, (1), pp. 4213–4219.
23. 23)
  - 21. Wossnig, L., Zhao, Z., Prakash, A.: ‘Quantum linear system algorithm for dense matrices’, Phys. Rev. Lett., 2018, 120, (5), p. 050502.
24. 24)
  - 5. Hallgren, S., Hales, L.: ‘Proceedings 41st annual symposium on foundations of computer science’. Proc. 41st Annual Symp. on Foundations of Computer Science, Redondo Beach, USA, 2000, pp. 515–525.
25. 25)
  - 24. Daskin, A., Kais, S.: ‘Group leaders optimization algorithm’, Mol. Phys., 2011, 109, (5), pp. 761–772.
26. 26)
  - 26. Nocedal, J., Wright, S.J.: ‘Numerical optimization’ in: ‘Research and financial Engineering' (Springer, New York, NY, USA, 2006, 2nd edn.).
27. 27)
  - 3. Aharonov, D., Ta-Shma, A.: ‘Adiabatic quantum state generation and statistical zero knowledge’. ‘STOC ‘03: Proc. of the thirty-fifth annual ACM symp. on Theory of Computing’, San Diego, USA, June 2003, pp. 20–29.
28. 28)
  - 12. Hastie, T., Friedman, J., Tibshirani, R.: ‘The elements of statistical learning’ (Springer Series in Statistics, New York, USA, 2001).
29. 29)
  - 34. Suzuki, M.: ‘Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations’, Phys. Lett. A, 1990, 146, (6), pp. 319–323.
30. 30)
  - 22. Bühlmann, P., van de Geer, S.: ‘Statistics for high-dimensional data: methods, theory and applications’ (Springer-Verlag Berlin Heidelberg, Germany, 2011).
31. 31)
  - 29. Moler, C., Van Loan, C.: ‘Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later’, SIAM Rev., 2003, 45, pp. 3–49.
32. 32)
  - 10. Dash, A., Sarmah, D., Behera, B.K., et al: ‘Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer’, arXiv 1805.10478 [quant-ph], 2018.
33. 33)
  - 6. Farhi, E., Goldstone, J., Gutmann, S.: ‘A quantum approximate optimization algorithm’, arXiv 1411.4028 [quant-ph], 2014.
34. 34)
  - 32. Al-Mohy, A.H., Higham, N.J.: ‘Computing the action of the matrix exponential, with an application to exponential integrators’, SIAM J. Sci. Comput., 2011, 33, (2), pp. 488–511.
35. 35)
  - 17. Cao, Y., Daskin, A., Frankel, S., et al: ‘Quantum circuit design for solving linear systems of equations’, Mol. Phys., 2012, 110, (15-16), pp. 1675–1680.
36. 36)
  - 23. Suau, A.: ‘Working 4 × 4 HHL implementation’, Zenodo, 2018. Available at https://doi.org/10.5281/zenodo.1480660.

Quantum circuit design methodology for multiple linear regression

References

Related content