Abstract. Eigenvalue transformations, which include solving time-dependent differential equations as a special case, have a wide range of applications in scientific and engineering computation. While quantum algorithms for singular value transformations are well studied, eigenvalue transformations are distinct, especially for nonnormal matrices. We propose an efficient quantum algorithm for performing a class of eigenvalue transformations that can be expressed as a certain type of matrix Laplace transformation. This allows us to significantly extend the recently developed linear combination of Hamiltonian simulation method [D. An, J.-P. Liu, and L. Lin, Phys. Rev. Lett., 131 (2023), 150603; D. An, A. M. Childs, and L. Lin, Commun. Math. Phys. 407, 19 (2026)] to represent a wider class of eigenvalue transformations, such as powers of the matrix inverse, [Formula: see text], and the exponential of the matrix inverse, [Formula: see text]. The latter can be interpreted as the solution of a mass-matrix differential equation of the form [Formula: see text]. We demonstrate that our eigenvalue transformation approach can solve this problem without explicitly inverting [Formula: see text], thereby reducing the computational complexity.
Abstract. Eigenvalue transformations, which include solving time-dependent differential equations as a special case, have a wide range of applications in scientific and engineering computation. While quantum algorithms for singular value transformations are well studied, eigenvalue transformations are distinct, especially for nonnormal matrices. We propose an efficient quantum algorithm for performing a class of eigenvalue transformations that can be expressed as a certain type of matrix Laplace transformation. This allows us to significantly extend the recently developed linear combination of Hamiltonian simulation method [D. An, J.-P. Liu, and L. Lin, Phys. Rev. Lett., 131 (2023), 150603; D. An, A. M. Childs, and L. Lin, Commun. Math. Phys. 407, 19 (2026)] to represent a wider class of eigenvalue transformations, such as powers of the matrix inverse, [Formula: see text], and the exponential of the matrix inverse, [Formula: see text]. The latter can be interpreted as the solution of a mass-matrix differential equation of the form [Formula: see text]. We demonstrate that our eigenvalue transformation approach can solve this problem without explicitly inverting [Formula: see text], thereby reducing the computational complexity.
Eigenvalue transformations, which include solving time-dependent differential equations as a special case, have a wide range of applications in scientific and engineering computation. While quantum algorithms for singular value transformations are well studied, eigenvalue transformations are distinct, especially for non-normal matrices. We propose an efficient quantum algorithm for performing a class of eigenvalue transformations that can be expressed as a certain type of matrix Laplace transformation. This allows us to significantly extend the recently developed linear combination of Hamiltonian simulation (LCHS) method [An, Liu, Lin, Phys. Rev. Lett. 131, 150603, 2023; An, Childs, Lin, arXiv:2312.03916] to represent a wider class of eigenvalue transformations, such as powers of the matrix inverse, A−k, and the exponential of the matrix inverse, e−A−1. The latter can be interpreted as the solution of a mass-matrix differential equation of the form Au′(t)=−u(t). We demonstrate that our eigenvalue transformation approach can solve this problem without explicitly inverting A, reducing the computational complexity.
We discover two complementary linear-combination-of-Hermitian-matrices (LCHM) formulations to achieve a general non-normal matrix eigenvalue transformation g(A). Firstly, for A=L+iH with Hermitian L and H, the vanilla LCHM formula represents g(A) as a kernel integral of g(i(H+kL)), and it contains linear-combination-of-Hamiltonian-simulation (LCHS) [An, Liu, Lin, Phys. Rev. Lett. 2023] as the special case for matrix exponentials. Secondly, for the angular Hermitian Xθ=cosθL+sinθH, the Weyl LCHM formula expresses g(A) via integrating g(eiθ(Xθ±i(I−Xθ2)1/2)). For the matrix power g(A)=Am, the Fourier projection of Weyl LCHM gives Am=π2∫0πeimθTm(Xθ)dθ=N2∑j=0N−1eimθjTm(Xθj),θj=Nπj,for every N>m with Chebyshev polynomial of Hermitian Tm(Xθ) and N samples. The discrete formula is exact, introduces no truncation and angular quadrature error, and offers O(1) post-selection weights.
LCHM formulas lead to new quantum eigenvalue transformation (QET) algorithms. For a degree-d polynomial pd(A) on ∣ψ⟩, our QET algorithm can achieve optimal Θ(d) circuit depth and optimal O(∣∣pd∣∣∞/∣∣pd(A)∣ψ⟩∣∣) post-selection repetitions. LCHM-based QETs unify various quantum linear algebraic problems with near-optimal O(dlog(d/ε)) Clifford+T gates, including driven ODEs (reduced to standard LCHS), iterative methods, resolvents, log(I+A), (λI+A)ν, Sign and ReLU transforms, and Faber approximation on noncircular domains.
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 O(logε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 dtdψ(t)=−A(t)ψ(t), for which we achieve a 2.1× cost reduction over prior art.
Abstract. Many problems in linear algebra—such as those arising from non-Hermitian physics, transcorrelated quantum chemistry, and differential equations—can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited for this task because eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum superposition of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate [Formula: see text] Fourier coefficients with [Formula: see text] gates compared to prior approaches with linear cost.
We introduce a quantum algorithm to perform the Laplace transform on quantum computers. Already, the quantum Fourier transform (QFT) is the cornerstone of many quantum algorithms, but the Laplace transform or its discrete version has not seen any efficient implementation on quantum computers due to its dissipative nature and hence non-unitary dynamics. However, a recent work has shown an efficient implementation for certain cases on quantum computers using the Taylor series. Unlike previous work, our work provides a completely different algorithm for doing Laplace Transform using Quantum Eigenvalue Transformation and Lap-LCHS, very efficiently at points which form an arithmetic progression. Our algorithm can implement N×N discrete Laplace transform in gate complexity that grows as O((logN)3), ignoring the state preparation cost, where N=2n and n is the number of qubits, which is a superpolynomial speedup in number of gates over the best classical counterpart that has complexity O(N⋅logN) for the same cases. Also, the circuit width grows as O(logN). Quantum Laplace Transform (QLT) may enable new Quantum algorithms for cases like solving differential equations in the Laplace domain, developing an inverse Laplace transform algorithm on quantum computers, imaginary time evolution in the resolvent domain for calculating ground state energy, and spectral estimation of non-Hermitian matrices.
Eigenvalue transformations appear ubiquitously in scientific computation, ranging from matrix polynomials to differential equations, and are beyond the reach of the quantum singular value transformation framework. In this work, we study the efficiency of quantum algorithms based on contour integral representation for eigenvalue transformations from both theoretical and practical aspects. Theoretically, we establish a complete complexity analysis of the contour integral approach proposed in [Takahira, Ohashi, Sogabe, and Usuda. Quant. Inf. Comput., 22, 11\&12, 965--979 (2021)]. Moreover, we combine the contour integral approach and the sampling-based linear combination of unitaries to propose a quantum algorithm for estimating observables of eigenvalue transformations using only 3 additional qubits. Practically, we design contour integral based quantum algorithms for linear ordinary differential equations, φ-functions, Fréchet derivatives of matrix functions, and matrix functions. In particular, we show that the contour integral algorithm can outperform all the existing quantum algorithms in the case of solving asymptotically stable differential equations.