2020/02/01 by Souichi Takahira, Asuka Ohashi, Tomohiro Sogabe +2 · 1 voice · 1 citation
Computer Science · Physics and Astronomy · #Matrix Theory and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #quant-ph
paper · pdf · doi:10.26421/qic20.1-2-2
published as Quantum Information and Computation, Vol.20, No.1&2, pp.14-36, (Feb. 2020) · 23 pages, 1 figure
openalex publication_date 2020/02/01 · openalex created_date 2020/04/03 · arxiv created 2021/06/15 · arxiv updated 2021/06/16 · openalex updated_date 2026/07/28
For matrix A, vector \boldsymbolb and function f, the computation of vector f(A)\boldsymbolb arises in many scientific computing applications. We consider the problem of obtaining quantum state | f ⟩ corresponding to vector f(A)\boldsymbolb. There is a quantum algorithm to compute state | f ⟩ using eigenvalue estimation that uses phase estimation and Hamiltonian simulation e\bf i A t. However, the algorithm based on eigenvalue estimation needs \textrmpoly(1/ε) runtime, where ε is the desired accuracy of the output state. Moreover, if matrix A is not Hermitian, e\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 poly(log(1/ε)) and the algorithm outputs state | f ⟩ even if A is not Hermitian.