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_\theta = \cos\theta L+\sin\theta H$, the Weyl LCHM formula expresses $g(A)$ via integrating $g(\mathrm{e}^{\mathrm{i}\theta} (X_\theta\pm\mathrm{i}(I-X_\theta^2)^{1/2}))$. For the matrix power $g(A)=A^m$, the Fourier projection of Weyl LCHM gives \[ A^m=\frac{2}{\pi}\int_0^\pi \text{e}^{\text{i} m\theta}T_m(X_\theta) \text{d}\theta = \frac{2}{N}\sum_{j=0}^{N-1} \text{e}^{\text{i} m\theta_j}T_m(X_{\theta_j}),\quad\theta_j=\frac{\pi j}{N},\quad \text{for every } N>m \] with Chebyshev polynomial of Hermitian $T_m(X_\theta)$ 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 $|\psi\rangle$, our QET algorithm can achieve optimal $\Theta(d)$ circuit depth and optimal $\mathcal{O}(||p_d||_{\infty}/||p_d(A)|\psi\rangle||)$ post-selection repetitions. LCHM-based QETs unify various quantum linear algebraic problems with near-optimal $\mathcal{\widetilde O}(d\log(d/\epsilon))$ Clifford$+T$ gates, including driven ODEs (reduced to standard LCHS), iterative methods, resolvents, $\log(I+A)$, $(\lambda I+A)^\nu$, Sign and ReLU transforms, and Faber approximation on noncircular domains.

arXiv:2607.25812 [quant-ph]

(or arXiv:2607.25812v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2607.25812 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.