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.

Many problems in linear algebra-such as those arising from non-Hermitian physics, transcorrelated quantum chemistry and differential equations-can be solved on a quan-tum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited to this task, as 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 super-position 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$n$Fourier coefficients with 0 (poly log ($n$)) gates compared to prior approaches with linear cost.

We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our algorithm simulates the time evolution of such a Hamiltonian on $n$ qubits for time $T$ up to error $\epsilon$ using ${\mathcal O}( nT {polylog} (nT/\epsilon))$ gates with depth ${\mathcal O}(T { polylog} (nT/\epsilon))$. Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in $nT$ and polylogarithmic in $1/\epsilon$. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires ${\widetilde{\Omega}}(nT)$ gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To the best of our knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb--Robinson bounds. In the appendix, we prove a Lieb--Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb--Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.

An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.

We present a quantum algorithm for approximating the real time evolution e−iHt of an arbitrary d-sparse Hamiltonian to error є, given black-box access to the positions and b-bit values of its non-zero matrix entries. The query complexity of our algorithm is O((t√d||H||1 → 2)1+o(1)/єo(1)) with respect to the largest Euclidean row norm ||H||1 → 2, which is shown to be optimal up to subpolynomial factors through a matching lower bound, and it uses a factor O(b) more gates. This provides a polynomial speedup in sparsity for the common case where the spectral norm is known, and generalizes previous approaches which achieve optimal scaling, but with respect to more restrictive parameters. By exploiting knowledge of the spectral norm, our algorithm solves the black-box unitary implementation problem – O(d1/2+o(1)) queries suffice to approximate any d-sparse unitary in the black-box setting, which matches the quantum search lower bound of Ω(√d) queries and improves upon prior art [Berry and Childs, QIP 2010] of Õ(d2/3) queries. Combined with known techniques, we also solve systems of sparse linear equations with condition number κ using O((κ √d)1+o(1)/єo(1)) queries, which is a quadratic improvement in sparsity.

We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and encompasses all physically reasonable Hamiltonians. Our algorithm simulates the time evolution of such a Hamiltonian on n qubits for time T up to error ε using O(T polylog(nT/ε)) gates with depth O(T polylog(nT/ε)). Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in nT and polylogarithmic in 1/ε. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires (nT) gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To our best knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.