Quantum algorithm for matrix functions by Cauchy's integral formula
| Autor: | Takahira, Souichi, Ohashi, Asuka, Sogabe, Tomohiro, Usuda, Tsuyoshi Sasaki |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Quantum Information and Computation, Vol.20, No.1&2, pp.14-36, (Feb. 2020) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.26421/QIC20.1-2-2 |
| Popis: | For matrix $A$, vector $\boldsymbol{b}$ and function $f$, the computation of vector $f(A)\boldsymbol{b}$ arises in many scientific computing applications. We consider the problem of obtaining quantum state $\lvert f \rangle$ corresponding to vector $f(A)\boldsymbol{b}$. There is a quantum algorithm to compute state $\lvert f \rangle$ using eigenvalue estimation that uses phase estimation and Hamiltonian simulation $\mathrm{e}^{\mathrm{{\bf i}} A t}$. However, the algorithm based on eigenvalue estimation needs $\textrm{poly}(1/\epsilon)$ runtime, where $\epsilon$ is the desired accuracy of the output state. Moreover, if matrix $A$ is not Hermitian, $\mathrm{e}^{\mathrm{{\bf i}} A t}$ is not unitary and we cannot run eigenvalue estimation. In this paper, we propose a quantum algorithm that uses Cauchy's integral formula and the trapezoidal rule as an approach that avoids eigenvalue estimation. We show that the runtime of the algorithm is $\mathrm{poly}(\log(1/\epsilon))$ and the algorithm outputs state $\lvert f \rangle$ even if $A$ is not Hermitian. Comment: 23 pages, 1 figure |
| Databáze: | arXiv |
| Externí odkaz: |
|