Quantum eigenvalue processing
arXiv:2401.06240 · doi:10.1137/24M1689363
Abstract
Many problems in linear algebra -- such as those arising from non-Hermitian physics 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, 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 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 Fourier coefficients with gates compared to prior approaches with linear cost.
114 pages, 3 figures. Tabulated common measures of non-normality (Jordan condition number, numerical range, pseudospectrum) and the corresponding cost of eigenvalue processors. Improved complexity of initial state preparation using the block preconditioning technique from arXiv:2410.18178. Enhanced version of the paper presented at FOCS 2024 and published in SICOMP
References in corpus (34)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum algorithm for solving linear systems of equations
- Quantum metrology
- Non-Hermitian Physics
- Hamiltonian Simulation by Qubitization
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Synthesis of Quantum Logic Circuits
- Toward the first quantum simulation with quantum speedup
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- On the relationship between continuous- and discrete-time quantum walk
- Faster than Hermitian Quantum Mechanics
- A random compiler for fast Hamiltonian simulation
- Even more efficient quantum computations of chemistry through tensor hypercontraction
- Quantum computing enhanced computational catalysis
- General optimality of the Heisenberg limit for quantum metrology
- Fixed-point quantum search with an optimal number of queries
- Exponential improvement in precision for simulating sparse Hamiltonians
- Quantum algorithm for linear differential equations with exponentially improved dependence on precision
- Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
- Near-optimal ground state preparation
- Faster quantum simulation by randomization
- Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
- Preparing ground states of quantum many-body systems on a quantum computer
- Black-box quantum state preparation without arithmetic
- Time-dependent Hamiltonian simulation with -norm scaling
- Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- Improved quantum algorithms for linear and nonlinear differential equations
- A randomized quantum algorithm for statistical phase estimation
- Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
- Quantum simulation of electronic structure with a transcorrelated Hamiltonian: improved accuracy with a smaller footprint on the quantum computer
- Time-marching based quantum solvers for time-dependent linear differential equations
- Hamiltonian simulation with random inputs
- Quantum and classical query complexities of functions of matrices