Optimal Quantum Eigenvalue Transformation via Linear Combinations of Hermitian Matrices

Abstract

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+\mathrm{i}H$ with Hermitian $L$ and $H$, the vanilla LCHM formula represents $g(A)$ as a kernel integral of $g(\mathrm{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_{\hat{I}}¸=\cos \hat{I}¸L+\sin \hat{I}¸H$, the Weyl LCHM formula expresses $g(A)$ via integrating $g({\mathrm{e}}^{\mathrm{i}\hat{I}¸}(X_{\hat{I}}¸\pm \mathrm{i}(I-X_{\hat{I}}{¸}^2{)}^{1/2}))$. For the matrix power $g(A)=A^m$, the Fourier projection of Weyl LCHM gives \[ A^m=\frac{2}π\int_0^π\text{e}^{\text{i} mθ}T_m(X_θ) \text{d}θ= \frac{2}{N}\sum_{j=0}^{N-1} \text{e}^{\text{i} mθ_j}T_m(X_{θ_j}),\quadθ_j=\frac{πj}{N},\quad \text{for every } N>m \] with Chebyshev polynomial of Hermitian $T_m(X_{\hat{I}}¸)$ and $N$ samples. The discrete formula is exact, introduces no truncation and angular quadrature error, and offers $\mathcal{O}(1)$ post-selection weights. LCHM formulas lead to new quantum eigenvalue transformation (QET) algorithms. For a degree-$d$ polynomial $p_d(A)$ on $|\ddot{I}ˆ⟩$, our QET algorithm can achieve optimal $\hat{I}˜(d)$ circuit depth and optimal $\mathcal{O}(||p_d|{|}_{\infty }/||p_d(A)|\ddot{I}ˆ⟩||)$ post-selection repetitions. LCHM-based QETs unify various quantum linear algebraic problems with near-optimal $\tilde{\mathcal{O}}(d\log (d/\hat{I}\mu ))$ Clifford$+T$ gates, including driven ODEs (reduced to standard LCHS), iterative methods, resolvents, $\log (I+A)$, $(\hat{I}»I+A{)}^{\hat{I}}½$, Sign and ReLU transforms, and Faber approximation on noncircular domains.

60 pages, 3 tables

Topics & keywords