arXiv:2609.31372
Quantum algorithms for the exponentiation of Toeplitz matrices and applications in partial differential equations
Xabier Gutiérrez, Nicola Mariella, Javier González-Conde, Sergiy Zhuk, Mikel Sanz
Abstract
We present quantum algorithms to approximate the exponential of banded Toeplitz matrices. These matrices have central importance in many PDE related problems, but their quantum implementation is hindered by their possibly large norms. Constructing directly the exponential we can circumvent this limitation. By relating the lower/upper shift operators to circulant and skewcirculant generators, which are diagonalised by the QFT, we construct (i) an LCU-based block encoding of banded Toeplitz matrices, (ii) an efficient, controllably truncated Pauli-string decomposition of the circulant eigenphases with a closed-form error bound, and (iii) a specialized QFT-Trotter product formula. As an application we build a block encoding of the propagator of the discretised heat equation with periodic, Dirichlet and Neumann boundary conditions, using a frequency cutoff.
AI Summary
The paper studies direct quantum implementations of $e^{tT}$ for banded Toeplitz matrices, motivated by PDE discretizations whose generator norms grow with grid refinement. It combines circulant structure, Fourier diagonalization, and product formulas rather than applying polynomial transformations to a normalized generator. Upper and lower shifts are expressed through circulant and skew-circulant generators, yielding an LCU block encoding of $T$ and a decomposition into two QFT-diagonalizable terms. Truncating small eigenphase gates gives closed-form normalized Frobenius-error expressions and an operator-norm bound, up to an optimized global phase, of $\pi |k|/2^\delta$ for the $k$th generator power. A commuting Pauli-$Z$ expansion supplies circuits for skew-Hermitian exponentials. Under contractivity assumptions, the stated QFT–Trotter error after $c$ steps is $O(t^2\|\alpha\|_1^2/c)+O(\pi tm\|\alpha\|_1/2^\delta)$, where $m$ is the half-bandwidth. For the one-dimensional heat equation, the proposed frequency cutoff is $k_c=O(L\sqrt{t^{-1}\log(1/\epsilon)})$. The retained generator has norm $O(\log(1/\epsilon)/t)$, avoiding grid-spacing dependence; LCHS is then claimed to require $O(\log^2(1/\epsilon))$ Hamiltonian-simulation calls. Periodic boundaries use the QFT, with sine/cosine-transform embeddings discussed for Dirichlet and Neumann boundaries. The paper explicitly leaves rigorous selection and size bounds for the retained Pauli-string subset open, and notes exponential prefactors for non-contractive coefficients. The heat cutoff presentation also distinguishes imperfectly between truncating the propagator and zeroing generator eigenvalues: the displayed construction leaves discarded modes as identity, whereas the stated cutoff-error estimate assumes those propagator modes are removed.
Central claim may not hold: The general Toeplitz construction has contractivity restrictions and coefficient-norm-dependent costs, so it does not establish unrestricted avoidance of the large-generator-norm bottleneck. The additional heuristic selection of a Pauli-string subset Omega has no proved error-versus-size guarantee, although retaining the full truncated basis avoids that particular gap. The heat-equation construction sets discarded generator eigenvalues to zero and thus preserves discarded modes with propagator eigenvalue one, invalidating its claimed exponentially small cutoff error. The displayed low-frequency heat blocks use Gamma_m phases with denominator 2^m instead of 2^n, producing the wrong spectrum and restoring a generator norm of order delta_x^(−2). The claimed boundary-condition embedding cannot yield the stated Dirichlet Laplacian, as trace invariance rules it out and the appendix instead produces endpoint diagonal entries −3.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.