arXiv:2609.32262
Contour-integral and Fourier transform based multivariable quantum eigenvalue transformation for commuting matrices
Shan Jiang, Dong An
Abstract
We study the problem of implementing multivariable matrix-valued functions on a quantum computer and propose two quantum algorithms for multivariable matrix eigenvalue transformations acting on tuples of pairwise commuting matrices. The first algorithm is based on multivariable contour integrals and applies to arbitrary holomorphic functions on $\mathbb{C}^n$. The second algorithm is based on high-dimensional Fourier transforms and designed for smooth functions of commuting Hermitian matrices. For both algorithms, we discuss and analyze the complexity of their quantum implementation leveraging quantum singular value transformation, compression gadgets, and linear combination of unitaries. We additionally study their hybrid quantum--classical variants that reduce the number of required ancilla qubits to logarithmic dependence on the number of variables, at the cost of increased query complexity. As an application, we show that multivariable matrix polynomials can be implemented with no additional explicit degree dependence, depending only on global properties of the polynomials.
AI Summary
The paper studies how to implement $f(A_1,\ldots,A_n)$ on an input quantum state when the matrices commute and are supplied through block-encodings. It gives two integral-representation algorithms: multivariable contour integration for holomorphic functions of potentially non-Hermitian matrices, and Fourier inversion for smooth functions of commuting Hermitian matrices. The contour algorithm discretizes a product of contours, implements resolvents using QSVT, multiplies them with a compression gadget, and combines terms using LCU and amplitude amplification. Writing $q=\|f(\boldsymbol A)|\psi\rangle\|$, its query cost per matrix is approximately $\widetilde O((B\prod_r\gamma_r l_r/q)\gamma_j\alpha_j\log(1/\epsilon))$, suppressing constant-to-the-$n$ factors and contour-radius dependence. Here $B$ bounds the function on the contours, $l_r$ are contour lengths, and $\gamma_r$ bound resolvent norms. The Fourier algorithm instead combines Hamiltonian evolutions, with cost controlled by $(2\pi)^{-n/2}\|\widehat f\|_1/q$ and a frequency cutoff determined by derivative Fourier norms. Explicit truncation and discretization bounds establish accuracy under Sobolev regularity and integrability assumptions. Sampling-based variants estimate the unnormalized observable $\langle\psi|f^\dagger O f|\psi\rangle$ using $a+O(\log n)$ ancillas, trading coherent LCU for repetitions scaling as $O(\|O\|^2 C^4/\epsilon^2)$, up to confidence factors, where $C$ is the LCU normalization. Polynomial applications replace explicit degree and coefficient dependence with analytic norms, which can themselves grow with degree. Stated limitations include the commutativity restriction, potentially exponential dependence on the number of variables, and limited advantages for simple functions already implementable by combining univariate transformations.
Central claim may not hold: The coherent algorithms lack function-access assumptions guaranteeing efficient LCU coefficient-state preparation and Fourier-coefficient computation, and known integrability alone does not justify the claimed polylogarithmic preparation time. The hybrid algorithms assume classical sampling from multivariable coefficient distributions without establishing its computational cost, so their matrix-query and repetition bounds do not establish efficient total runtime. The contour analysis substitutes its coefficient-norm bound incorrectly into 1/epsilon', placing n in the denominator instead of the numerator and losing a factor n^2 in that displayed substitution.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 36 pages including appendix