Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

quant-phSubmitted Sep 25, 2026• Announced Sep 28, 2026• 0 citations• Revised Oct 19, 2026 (v2)
v1 · Sep 25, 2026v2 · Oct 19, 2026
arXivHTMLPDF

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.

Related papers

Efficient quantum circuits for dense circulant and circulant like operators

Sisi Zhou, Jingbo B. Wang

Circulant matrices are an important family of operators, which have a wide range of applications in science and engineering-related fields. They are, in general, non-sparse and non-unitary. In this paper, we present efficient quantum circuits to implement circulant operators using fewer resources and with lower complexity than existing methods. Moreover, our quantum circuits can be readily extended to the implementation of Toeplitz, Hankel and block circulant matrices. Efficient quantum algorithms to implement the inverses and products of circulant operators are also provided, and an example application in solving the equation of motion for cyclic systems is discussed.

Royal Society Open Science•May 1, 2017•22 citations

QUANTUM ALGORITHMS FOR DIFFERENTIAL EQUATIONS

Aaron Ostrander

This thesis describes quantum algorithms for Hamiltonian simulation, ordinary differential equations (ODEs), and partial differential equations (PDEs). Product formulas are used to simulate Hamiltonians which can be expressed as a sum of terms which can each be simulated individually. By simulating each of these terms in sequence, the net effect approximately simulates the total Hamiltonian. We find that the error of product formulas can be improved by randomizing over the order in which the Hamiltonian terms are simulated. We prove that this approach is asymptotically better than ordinary product formulas and present numerical comparisons for small numbers of qubits. The ODE algorithm applies to the initial value problem for time-independent first order linear ODEs. We approximate the propagator of the ODE by a truncated Taylor series, and we encode the initial value problem in a large linear system. We solve this linear system with a quantum linear system algorithm (QLSA) whose output we perform a post-selective measurement on. The resulting state encodes the solution to the initial value problem. We prove that our algorithm is asymptotically optimal with respect to several system parameters. The PDE algorithms apply the finite difference method (FDM) to Poisson's equation, the wave equation, and the Klein-Gordon equation. We use high order FDM approximations of the Laplacian operator to develop linear systems for Poisson's equation in cubic volumes under periodic, Neumann, and Dirichlet boundary conditions. Using QLSAs, we output states encoding solutions to Poisson's equation. We prove that our algorithm is exponentially faster with respect to the spatial dimension than analogous classical algorithms. We also consider how high order Laplacian approximations can be used for simulating the wave and Klein-Gordon equations. We consider under what conditions it suffices to use Hamiltonian simulation for time evolution, and we propose an algorithm for these cases that uses QLSAs for state preparation and post-processing.

•Jan 1, 2019•0 citations

Boundary-Aware QFT Block-Encoding of Fractional Laplacians

Younes Javanmard, Sina Kazemian

We study the quantum Fourier transform (QFT) block-encoding of the semi-discrete fractional Laplacian on bounded domains with open, zero-extension boundary conditions. In the notation of the main construction, the target operator is the finite Toeplitz truncation \(A^{(N)}_{α,h}\) obtained from the full-lattice semi-discrete operator with symbol \(|ξ|^α\). A finite QFT register, however, diagonalizes circulant matrices rather than Toeplitz truncations. The native QFT circuit therefore implements a periodic surrogate \(\widetilde A^{(N)}_{α,h}\), not the open-boundary operator. We identify this mismatch through an exact Toeplitz-to-circulant aliasing identity. To recover the open-boundary action, we zero-pad the state into a larger \(M\)-point QFT register, apply the same Fourier-symbol block-encoding, and compress back to the physical subspace. The resulting compressed block satisfies \(P_{N\to M}^{\dagger}\widetilde A^{(M)}_{α,h}P_{N\to M} = A^{(N)}_{α,h}+E^{(M)}\), where \(E^{(M)}\) is controlled by the tail of the semi-discrete convolution kernel. Thus, the QFT layer implements the fractional symbol, while zero-padding supplies the open-boundary geometry. The construction is an operator-compilation primitive for boundary-aware quantum simulation rather than a complete PDE solver.

quant-pharXiv:2605.16749•May 19, 2026•0 citations

Efficient quantum circuits for dense and non-unitary operators

Sisi Zhou, J. B. Wang

Circulant matrices are an important family of operators, which have a wide range of applications in science and engineering related fields. They are in general non-sparse and non-unitary. In this paper, we present efficient quantum circuits to implement circulant operators using fewer resources and with lower complexity than existing methods. Moreover, our quantum circuits can be readily extended to the implementation of Toeplitz, Hankel, and block circulant matrices. Efficient quantum algorithms to implement the inverses and products of circulant operators are also provided.

arXiv:1607.07149•Jul 25, 2016•2 citations

Block encoding of sparse matrices with a periodic diagonal structure

Alessandro Andrea Zecchi, Claudio Sanavio, Luca Cappelli +3 more

Block encoding is a successful technique used in several powerful quantum algorithms. In this work we provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure. The proposed methodology is based on the linear combination of unitaries (LCU) framework and on an efficient unitary operator used to project the complex exponential at a frequency $ω$ multiplied by the computational basis into its real and imaginary components. We demonstrate a distinct computational advantage with a $\mathcal{O}(\text{poly}(n))$ gate complexity, where $n$ is the number of qubits, in the worst-case scenario used for banded matrices, and $\mathcal{O}(n)$ when dealing with a simple diagonal matrix, compared to the exponential scaling of general-purpose methods for dense matrices. Various applications for the presented methodology are discussed in the context of solving differential problems such as the advection-diffusion-reaction (ADR) dynamics, using quantum algorithms with optimal scaling, e.g., quantum singular value transformation (QSVT). Numerical results are used to validate the analytical formulation.

quant-pharXiv:2602.10589•Feb 12, 2026•0 citations

Quantum algorithm for solving differential equations using SLAC derivatives

Rakshit M. Gharat, Gopikrishnan Muraleedharan, Dominic W. Berry +1 more

In numerical approaches to solving differential equations on a lattice, a representation of the derivative operator that correctly matches the continuum behaviour of functions of momentum up to the band limit must be non-local. We present the construction of efficient linear-combination-of-unitaries ($\mathrm{LCU}$)-based block-encodings for the first-order derivative and Laplacian operators in the non-local \(N=2^n\)-dimensional SLAC representation. We use state-preparation techniques designed for smoothly decaying functions to prepare the dense $\mathrm{LCU}$ amplitudes with high success probability and low gate cost. Furthermore, we demonstrate how Shannon wavelet transforms can be applied to these block-encodings to obtain multiscale representations of the SLAC derivative operators. We then show how to apply a diagonal preconditioner that reduces the condition number of these matrices in the multiscale wavelet basis to a small constant. This enables the solution of partial differential equations (PDEs) with SLAC-discretised derivative operators on a finite lattice using the quantum linear solving algorithm ($\mathrm{QLSA}$). For a $d$-dimensional PDE, after projection away from the nullspace, the resulting quantum linear-system algorithm has overall gate complexity ${O}(dn^3α^{(k)}\log(1/\varepsilon))$, where $α^{(k)}$ is the subnormalisation factor of the order-$k$ SLAC block-encoding and $\varepsilon$ denotes the algorithmic approximation error.

quant-pharXiv:2605.04861•May 7, 2026•0 citations
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.
Circulant matrices are an important family of operators, which have a wide range of applications in science and engineering-related fields. They are, in general, non-sparse and non-unitary. In this paper, we present efficient quantum circuits to implement circulant operators using fewer resources and with lower complexity than existing methods. Moreover, our quantum circuits can be readily extended to the implementation of Toeplitz, Hankel and block circulant matrices. Efficient quantum algorithms to implement the inverses and products of circulant operators are also provided, and an example application in solving the equation of motion for cyclic systems is discussed.
This thesis describes quantum algorithms for Hamiltonian simulation, ordinary differential equations (ODEs), and partial differential equations (PDEs). Product formulas are used to simulate Hamiltonians which can be expressed as a sum of terms which can each be simulated individually. By simulating each of these terms in sequence, the net effect approximately simulates the total Hamiltonian. We find that the error of product formulas can be improved by randomizing over the order in which the Hamiltonian terms are simulated. We prove that this approach is asymptotically better than ordinary product formulas and present numerical comparisons for small numbers of qubits. The ODE algorithm applies to the initial value problem for time-independent first order linear ODEs. We approximate the propagator of the ODE by a truncated Taylor series, and we encode the initial value problem in a large linear system. We solve this linear system with a quantum linear system algorithm (QLSA) whose output we perform a post-selective measurement on. The resulting state encodes the solution to the initial value problem. We prove that our algorithm is asymptotically optimal with respect to several system parameters. The PDE algorithms apply the finite difference method (FDM) to Poisson's equation, the wave equation, and the Klein-Gordon equation. We use high order FDM approximations of the Laplacian operator to develop linear systems for Poisson's equation in cubic volumes under periodic, Neumann, and Dirichlet boundary conditions. Using QLSAs, we output states encoding solutions to Poisson's equation. We prove that our algorithm is exponentially faster with respect to the spatial dimension than analogous classical algorithms. We also consider how high order Laplacian approximations can be used for simulating the wave and Klein-Gordon equations. We consider under what conditions it suffices to use Hamiltonian simulation for time evolution, and we propose an algorithm for these cases that uses QLSAs for state preparation and post-processing.
We study the quantum Fourier transform (QFT) block-encoding of the semi-discrete fractional Laplacian on bounded domains with open, zero-extension boundary conditions. In the notation of the main construction, the target operator is the finite Toeplitz truncation Aα,h(N)A^{(N)}_{α,h}Aα,h(N)​ obtained from the full-lattice semi-discrete operator with symbol ∣ξ∣α|ξ|^α∣ξ∣α. A finite QFT register, however, diagonalizes circulant matrices rather than Toeplitz truncations. The native QFT circuit therefore implements a periodic surrogate A~α,h(N)\widetilde A^{(N)}_{α,h}Aα,h(N)​, not the open-boundary operator. We identify this mismatch through an exact Toeplitz-to-circulant aliasing identity. To recover the open-boundary action, we zero-pad the state into a larger MMM-point QFT register, apply the same Fourier-symbol block-encoding, and compress back to the physical subspace. The resulting compressed block satisfies PN→M†A~α,h(M)PN→M=Aα,h(N)+E(M)P_{N\to M}^{\dagger}\widetilde A^{(M)}_{α,h}P_{N\to M} = A^{(N)}_{α,h}+E^{(M)}PN→M†​Aα,h(M)​PN→M​=Aα,h(N)​+E(M), where E(M)E^{(M)}E(M) is controlled by the tail of the semi-discrete convolution kernel. Thus, the QFT layer implements the fractional symbol, while zero-padding supplies the open-boundary geometry. The construction is an operator-compilation primitive for boundary-aware quantum simulation rather than a complete PDE solver.
Circulant matrices are an important family of operators, which have a wide range of applications in science and engineering related fields. They are in general non-sparse and non-unitary. In this paper, we present efficient quantum circuits to implement circulant operators using fewer resources and with lower complexity than existing methods. Moreover, our quantum circuits can be readily extended to the implementation of Toeplitz, Hankel, and block circulant matrices. Efficient quantum algorithms to implement the inverses and products of circulant operators are also provided.
Block encoding is a successful technique used in several powerful quantum algorithms. In this work we provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure. The proposed methodology is based on the linear combination of unitaries (LCU) framework and on an efficient unitary operator used to project the complex exponential at a frequency ωωω multiplied by the computational basis into its real and imaginary components. We demonstrate a distinct computational advantage with a O(poly(n))\mathcal{O}(\text{poly}(n))O(poly(n)) gate complexity, where nnn is the number of qubits, in the worst-case scenario used for banded matrices, and O(n)\mathcal{O}(n)O(n) when dealing with a simple diagonal matrix, compared to the exponential scaling of general-purpose methods for dense matrices. Various applications for the presented methodology are discussed in the context of solving differential problems such as the advection-diffusion-reaction (ADR) dynamics, using quantum algorithms with optimal scaling, e.g., quantum singular value transformation (QSVT). Numerical results are used to validate the analytical formulation.
In numerical approaches to solving differential equations on a lattice, a representation of the derivative operator that correctly matches the continuum behaviour of functions of momentum up to the band limit must be non-local. We present the construction of efficient linear-combination-of-unitaries (LCU\mathrm{LCU}LCU)-based block-encodings for the first-order derivative and Laplacian operators in the non-local N=2nN=2^nN=2n-dimensional SLAC representation. We use state-preparation techniques designed for smoothly decaying functions to prepare the dense LCU\mathrm{LCU}LCU amplitudes with high success probability and low gate cost. Furthermore, we demonstrate how Shannon wavelet transforms can be applied to these block-encodings to obtain multiscale representations of the SLAC derivative operators. We then show how to apply a diagonal preconditioner that reduces the condition number of these matrices in the multiscale wavelet basis to a small constant. This enables the solution of partial differential equations (PDEs) with SLAC-discretised derivative operators on a finite lattice using the quantum linear solving algorithm (QLSA\mathrm{QLSA}QLSA). For a ddd-dimensional PDE, after projection away from the nullspace, the resulting quantum linear-system algorithm has overall gate complexity O(dn3α(k)log⁡(1/ε)){O}(dn^3α^{(k)}\log(1/\varepsilon))O(dn3α(k)log(1/ε)), where α(k)α^{(k)}α(k) is the subnormalisation factor of the order-kkk SLAC block-encoding and ε\varepsilonε denotes the algorithmic approximation error.