Implementing block-encoding with a decomposition of linear combination of unitaries
Lin‐Chun Wan, Chao‐Hua Yu, Shi‐Jie Pan, Yijie Shi, Su‐Juan Qin, Fei Gao, Qiaoyan Wen · arXiv (Cornell University) · 2019
The framework of block-encodings is designed to develop a variety of quantum algorithms by encoding a matrix as a block of a unitary. To harness the potential advantages of block-encoding, it is essential to implement the block-encodings with preferred parameters for various matrices. In this paper, we present a new approach to implement the block-encodings of $n\times n$ dense matrices by decomposing the matrices into linear combinations of displacement matrices. It is shown that our approach will generate a $(\chi;2\textrm{log}n;\epsilon)$-block-encoding if the displacement of the matrix has been stored in a quantum-accessible data structure, where $\chi$ is the $l_{1}$-norm of the displacement of the matrix and $\epsilon$ is a parameter related to precision. As applications, we also introduce quantum algorithms for solving linear systems with displacement structures, which are exponentially faster than their classical counterparts.