Quantum Circulant Preconditioner for Linear System of Equations

Changpeng Shao, Hua Xiang

Research output: Contribution to journalArticle (Academic Journal)peer-review

6 Citations (Scopus)
82 Downloads (Pure)


We consider the quantum linear solver for Ax = b with the circulant preconditioner C. The main technique is the singular value estimation (SVE) introduced in [Kerenidis and Prakash, Quantum recommendation system, in ITCS (2017)]. However, the SVE should be modified to solve the preconditioned linear system $C^{-1}Ax =
C^{-1}b$. Moreover, different from the preconditioned linear system considered in [Phys. Rev. Lett. 110, 250504 (2013)], the circulant preconditioner is easy to construct and can be directly applied to general dense non-Hermitian cases. The time complexity depends on the condition numbers of $C$ and $C^{-1}A$, as well as the Frobenius norm $\|A\|_F$ .
Original languageEnglish
Pages (from-to)062321
Number of pages9
JournalPhysical Review A
Publication statusPublished - 18 Dec 2018


Dive into the research topics of 'Quantum Circulant Preconditioner for Linear System of Equations'. Together they form a unique fingerprint.

Cite this