Quantum algorithm for matrix functions by Cauchy's integral formula

Abstract

For matrix $A$, vector $\mathbf{b}$ and function $f$, the computation of vector $f(A)\mathbf{b}$ arises in many scientific computing applications. We consider the problem of obtaining quantum state $|f⟩$ corresponding to vector $f(A)\mathbf{b}$. There is a quantum algorithm to compute state $|f⟩$ using eigenvalue estimation that uses phase estimation and Hamiltonian simulation ${\mathrm{e}}^{\mathbf{i}At}$. However, the algorithm based on eigenvalue estimation needs $\text{poly}(1/\epsilon )$ runtime, where $\epsilon$ is the desired accuracy of the output state. Moreover, if matrix $A$ is not Hermitian, ${\mathrm{e}}^{\mathbf{i}At}$ 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 $|f⟩$ even if $A$ is not Hermitian.

arXiv comment23 pages, 1 figure

Cited by in corpus (5)

• Time-marching based quantum solvers for time-dependent linear differential equations
• Quantum algorithms for matrix operations and linear systems of equations
• Quantum linear system algorithm with optimal queries to initial state preparation
• Computation of operator exponentials using the Dunford-Cauchy integral
• Energy-filtered excited states and real-time dynamics served in a contour integral