A Caltech Library Service

Near-term quantum algorithms for linear systems of equations with regression loss functions

Huang, Hsin-Yuan and Bharti, Kishor and Rebentrost, Patrick (2021) Near-term quantum algorithms for linear systems of equations with regression loss functions. New Journal of Physics, 23 (11). Art. No. 113021. ISSN 1367-2630. doi:10.1088/1367-2630/ac325f.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


Solving linear systems of equations is essential for many problems in science and technology, including problems in machine learning. Existing quantum algorithms have demonstrated the potential for large speedups, but the required quantum resources are not immediately available on near-term quantum devices. In this work, we study near-term quantum algorithms for linear systems of equations, with a focus on the two-norm and Tikhonov regression settings. We investigate the use of variational algorithms and analyze their optimization landscapes. There exist types of linear systems for which variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, suffer from a different plateau problem. To circumvent this issue, we design near-term algorithms based on a core idea: the classical combination of variational quantum states (CQS). We exhibit several provable guarantees for these algorithms, supported by the representation of the linear system on a so-called ansatz tree. The CQS approach and the ansatz tree also admit the systematic application of heuristic approaches, including a gradient-based search. We have conducted numerical experiments solving linear systems as large as 2³⁰⁰ × 2³⁰⁰ by considering cases where we can simulate the quantum algorithm efficiently on a classical computer. Our methods may provide benefits for solving linear systems within the reach of near-term quantum devices.

Item Type:Article
Related URLs:
URLURL TypeDescription
Huang, Hsin-Yuan0000-0001-5317-2613
Bharti, Kishor0000-0002-7776-6608
Additional Information:© 2021 The Author(s). Published by IOP Publishing Ltd on behalf of the Institute of Physics and Deutsche Physikalische Gesellschaft. Original content from this work may be used under the terms of the Creative Commons Attribution 4.0 licence. Any further distribution of this work must maintain attribution to the author(s) and the title of the work, journal citation and DOI. Received 18 December 2020.Revised 20 September 2021. Accepted 22 October 2021. Published 15 November 2021. We would like to thank Fernando Brandao, Yudong Cao, Richard Kueng, John Preskill, Ansis Rosmanis, Miklos Santha, Thomas Vidick, and Zhikuan Zhao for valuable discussions. HH is supported by the Kortschak Scholars Program and thanks the hospitality of the Centre for Quantum Technologies. KB acknowledges the CQT Graduate Scholarship. PR acknowledges support from the Singapore National Research Foundation, the Prime Minister's Office, Singapore, the Ministry of Education, Singapore under the Research Centres of Excellence programme under research Grant No. R 710-000-012-135, and Baidu-NUS Research Project No. 2019-03-07. Author contribution. All authors contributed to the research conducted in this work and the writing of the manuscript. KB performed the numerical calculations for the variational method. HH performed the numerical calculations for the CQS approach. Data availability. The data that support the findings of this study are available upon reasonable request from the authors. The authors declare no competing financial or non-financial interests.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Kortschak Scholars ProgramUNSPECIFIED
Centre for Quantum TechnologiesUNSPECIFIED
Ministry of Education (Singapore)R 710-000-012-135
National University of Singapore2019-03-07
Subject Keywords:linear systems, quantum computing, near-term quantum algorithms
Issue or Number:11
Record Number:CaltechAUTHORS:20211203-204703162
Persistent URL:
Official Citation:Hsin-Yuan Huang et al 2021 New J. Phys. 23 113021
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:112218
Deposited By: George Porter
Deposited On:03 Dec 2021 22:41
Last Modified:12 Jul 2022 19:51

Repository Staff Only: item control page