Guang Hao Low

Guang Hao Low, Yuan Su

Quantum algorithms for linear systems produce the solution state $A^{-1}|b\rangle$ by querying two oracles: $O_A$ that block encodes the coefficient matrix and $O_b$ that prepares the initial state. We present a quantum linear system algorithm making $\mathbfΘ\left(1/\sqrt{p}\right)$ queries to $O_b$, which is optimal in the success probability, and $\mathbf{O}\left(κ\log\left(1/p\right)\left(\log\log\left(1/p\right)+\log\left({1}/ε\right)\right)\right)$ queries to $O_A$, nearly optimal in all parameters including the condition number and accuracy. Notably, our complexity scaling of initial state preparation holds even when $p$ is not known $\textit{a priori}$. This contrasts with recent results achieving $\mathbf{O}\left(κ\log\left({1}/ε\right)\right)$ complexity to both oracles, which, while optimal in $O_A$, is highly suboptimal in $O_b$ as $κ$ can be arbitrarily larger than $1/\sqrt{p}$. In various applications such as solving differential equations, preparing ground states of operators with real spectra, and estimating and transforming eigenvalues of non-normal matrices, we can further improve the dependence on $p$ using a block preconditioning scheme to nearly match or outperform best previous results based on other methods, which also furnishes an extremely simple quantum linear system algorithm with an optimal query complexity to $O_A$. Underlying our results is a new Variable Time Amplitude Amplification algorithm with Tunable thresholds (Tunable VTAA), which fully characterizes generic nested amplitude amplifications, improves the $\ell_1$-norm input cost scaling of Ambainis to an $\ell_{\frac{2}{3}}$-quasinorm scaling, and admits a deterministic amplification schedule for the quantum linear system problem.

Guang Hao Low, Yuan Su

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 $n$ Fourier coefficients with $\mathbf{O}(\mathrm{polylog}(n))$ gates compared to prior approaches with linear cost.