Skip to Main content Skip to Navigation
Journal articles

Block-encoding-based quantum algorithm for linear systems with displacement structures

Abstract : Matrices with the displacement structures of circulant, Toeplitz, and Hankel types as well as matrices with structures generalizing these types are omnipresent in computations of sciences and engineering. In this paper we present efficient and memory-reduced quantum algorithms for solving linear systems with such structures by devising an approach to implement the block-encodings of these structured matrices. More specifically, by decomposing n×n dense matrices into linear combinations of displacement matrices, we first deduce the parametrized representations of the matrices with displacement structures so that they can be treated similarly. With such representations, we then construct ε-approximate block-encodings of these structured matrices in two different data access models, i.e., the black-box model and the quantum random access memory (QRAM) data structure model. It is shown the quantum linear system solvers based on the proposed block-encodings provide a quadratic speedup with respect to the dimension over classical algorithms in the black-box model and an exponential speedup in the QRAM data structure model. In particular, these linear system solvers subsume known results with significant improvements and also can motivate new instances where there was no specialized quantum algorithm before. As an application, one of the quantum linear system solvers is applied to the linear prediction of time series, which justifies the claimed quantum speedup is achievable for problems of practical interest.
Document type :
Journal articles
Complete list of metadata
Contributor : SCD EHESP Connect in order to contact the contributor
Submitted on : Monday, December 13, 2021 - 11:55:48 AM
Last modification on : Tuesday, January 25, 2022 - 6:56:09 PM

Links full text




Lin-Chun Wan, Chao-Hua Yu, Shi-Jie Pan, Su-Juan Qin, Fei Gao, et al.. Block-encoding-based quantum algorithm for linear systems with displacement structures. Physical Review A, American Physical Society 2021, 104 (6), ⟨10.1103/PhysRevA.104.062414⟩. ⟨hal-03477026⟩



Record views