Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation: A Weyl Calculus Approach
For quantum algorithm designers, this work provides a theoretically optimal and practically efficient method for implementing a broad class of matrix functions, with a concrete improvement over prior art in a specific application.
This paper develops a Weyl calculus approach to linear combination of Hamiltonian simulation (LCHS) for computing analytic matrix functions on quantum computers, achieving optimal O(log(1/ε)) query complexity for eigenvalue transformation. It also provides an optimization framework that yields a 2.1× cost reduction for simulating time-dependent dissipative ODEs.
Linear combination of Hamiltonian simulation (LCHS) provides an efficient method for implementing matrix exponentials $e^{-tA}$ on quantum computers. In this paper, we develop LCHS formulas for computing general matrix functions $f(A)$ when $f$ is analytic on the numerical range of $A$, with $A$ possibly non-normal. The essential technical tool is Weyl calculus, which reduces the construction of LCHS formulas for noncommuting operators to scalar Fourier approximation problems. Our construction yields a quantum eigenvalue transformation algorithm with optimal $\mathcal{O}(\log\frac{1}ε)$ query complexity scaling. Furthermore, our Weyl-calculus-based theory gives rise to an ansatz-free convex optimization framework that directly produces discrete LCHS formulas. This circumvents the inefficiencies of traditional quadrature rules and yields formulas highly optimized for coherent implementation on quantum computers. In addition, both our theory and optimization framework apply to the simulation of time-dependent dissipative ODE $\frac{\mathrm{d}}{\mathrm{d} t} ψ(t) = -A(t)ψ(t)$, for which we achieve a $2.1\times$ cost reduction over prior art.