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:2505.06866

Quantum preconditioning method for finite difference discretizations of the Poisson equation via Schrödingerization

Shi Jin, Nana Liu, Chuwen Ma, Yue Yu

Published May 11, 2025• 0 citations
arXivHTMLPDF

Abstract

We present a quantum preconditioning framework for solving linear systems arising from a finite difference discretization of the Poisson equation. It is based on the combination of the Schrödingerization technique \cite{JLY22b,JLYPRL24} and the BPX multilevel preconditioner in order to achieve near-optimal complexity. The Schrödingerization technique transforms linear partial and ordinary differential equations into Schrödinger-type systems with unitary evolution in one higher dimension, making them suitable for quantum simulation. A key contribution is a structure-aware construction of the block-encoding for the symmetrically preconditioned matrix $A_S = S^\top A S$, where $A$ is the stiffness matrix and $S$ encodes the BPX preconditioner in factored form. By establishing a novel commuting identity, we avoid the unfavorable normalization scaling that would otherwise arise from naive multiplication of block-encodings. This yields an exact block-encoding of $A_S$ with normalization $\mathcal{O}(d^2(L+1))$, where $d$ is the spatial dimension and $L$ is the number of levels. Combined with the Schrödingerization-based Hamiltonian simulation, the overall quantum algorithm achieves a query complexity of $\mathcal{O}\big(\mathrm{poly}(d)\varepsilon^{-1} \mathrm{polylog}(\varepsilon^{-1}) \big)$ for estimating linear functionals of the solution to a given tolerance $\varepsilon$.

DOI
10.48550/arxiv.2505.06866

Related papers

Schrödingerization based quantum algorithms for the fractional Poisson equation

Shi Jin, Nana Liu, Yue Yu

We develop a quantum algorithm for solving high-dimensional fractional Poisson equations. By applying the Caffarelli-Silvestre extension, the $d$-dimensional fractional equation is reformulated as a local partial differential equation in $d+1$ dimensions. We propose a quantum algorithm for the finite element discretization of this local problem, by capturing the steady-state of the corresponding differential equations using the Schrödingerization approach from \cite{JLY22SchrShort, JLY22SchrLong, analogPDE}. The Schrödingerization technique transforms general linear partial and ordinary differential equations into Schrödinger-type systems, making them suitable for quantum simulation. This is achieved through the warped phase transformation, which maps the equation into a higher-dimensional space. We provide detailed implementations of the method and conduct a comprehensive complexity analysis, which can show up to exponential advantage -- with respect to the inverse of the mesh size in high dimensions -- compared to its classical counterpart. Specifically, while the classical method requires $\widetilde{\mathcal{O}}(d^{1/2} 3^{3d/2} h^{-d-2})$ operations, the quantum counterpart requires $\widetilde{\mathcal{O}}(d 3^{3d/2} h^{-2.5})$ queries to the block-encoding input models, with the quantum complexity being independent of the dimension $d$ in terms of the inverse mesh size $h^{-1}$. Numerical experiments are conducted to verify the validity of our formulation.

arXiv:2505.01602•May 2, 2025•0 citations

Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity

Yin Yang, Yue Yu, Long Zhang

Quantum linear systems algorithms (QLSAs) aim to solve linear systems $A\bb{x}=\bb{b}$ exponentially faster than classical methods under certain conditions. In this work, we develop quantum algorithms for solving linear algebraic equations from an ODE-based perspective. Inspired by the linear combination of Hamiltonian simulation (LCHS) representation in the Fourier approach \cite{Childs2017QLSA}, we express the solution $\bb{x}$ as a linear combination of solutions to a system of linear convection equations, which become Schrödinger-type equations with unitary evolutions in the Fourier domain. We refer to this representation as LC-Schrödingerization. Based on this result, we construct an LCHS-based quantum algorithm with two LCHS instances: one for time-marching and one for numerical integration. The key construction uses the derivative of a Gaussian-smoothed hat function and recovers the solution over a fixed auxiliary interval. This permits a truncation time independent of the target accuracy and avoids the loss in success probability from selecting a single grid point. Periodization and explicit Fourier coefficients provide the corresponding projection error bounds. Under the stated oracle assumptions and given a constant-factor estimate of the solution norm, direct simulation of the select operators and block preconditioning achieve the optimal matrix-query complexity $\mathcal{O}(κ_A\log\frac1\varepsilon)$ without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.

quant-pharXiv:2609.19676•Sep 18, 2026•0 citations

A structure-aware construction of quantum BPX preconditioners for Q1 finite element discretizations of reaction-diffusion problems

Yin Yang, Yue Yu, Long Zhang

We present a structure-aware construction of quantum BPX preconditioners for Q1 finite element discretizations of constant-coefficient reaction--diffusion equations on the unit cube, including the Poisson equation. Building on existing quantum finite element and finite difference methods, we express the preconditioned operator through explicit one-dimensional maps, tensor products, and norm-preserving interlevel transfers. Symmetric preconditioning gives multilevel coefficients, and its favorable conditioning alone does not ensure efficient recovery of a state in the original finite element nodal basis. We instead use the local $L^2$-orthonormal basis underlying the construction as the output representation of the same finite element function. Its coefficient norm equals the continuous $L^2$ norm. Assuming direct access to the preconditioned right-hand side, we prepare this orthonormal coefficient state with a represented function error at most $\varepsilon$. The expected query complexity is \[ \mathcal{O}\!\Big(dL^3\frac{\|f\|_{L^2}}{\|u\|_{L^2}} \log\!\Big(2+\frac{L\|f\|_{L^2}}{\varepsilon}\Big)\Big), \] where $u$ is the exact solution, $f$ is the right-hand side, $d$ is the spatial dimension, and $L=\log_2(1/h)$ for mesh width $h$. The bound holds for $0<\varepsilon\le\|u\|_{L^2}/2$ and depends only polylogarithmically on mesh refinement for fixed continuous data. We also analyze linear-functional estimation and illustrate the construction and continuous error bounds with a one-dimensional UnitaryLab experiment.

arXiv:2610.06987•Oct 4, 2026•0 citations

Schrödingerization for quantum linear systems problems with near-optimal dependence on matrix queries

Yin Ping Yang, Yue Yu, Long Zhang

We develop a quantum algorithm for linear algebraic equations $ A\bb{x} = \bb{b} $ from the perspective of Schrödingerization-form problems, which are characterized by a system of linear convection equations in one higher dimension. When $ A $ is positive definite, the solution $ \bb{x} $ can be interpreted as the steady-state solution to a system of linear ordinary differential equations (ODEs). This ODE system can be solved by using the linear combination of Hamiltonian simulation (LCHS) method in \cite{ACL2023LCH2}, which serves as the continuous implementation of the Fourier transform in the Schrödingerization method from \cite{JLY22SchrShort, JLY22SchrLong}. Schrödingerization transforms linear partial differential equations (PDEs) and ODEs with non-unitary dynamics into Schrödinger-type systems via the so-called warped phase transformation that maps the equation into one higher dimension. When $ A $ is a general Hermitian matrix, the inverse matrix can still be represented in the LCHS form in \cite{ACL2023LCH2}, but with a kernel function based on the Fourier approach in \cite{Childs2017QLSA}. Although this LCHS form provides the steady-state solution to a system of linear ODEs associated with the least-squares equation, applying Schrödingerization to this least-squares system is not appropriate, as it results in a much larger condition number. We demonstrate that in both cases, the solution $ \bb{x} $ can be expressed as the LCHS of Schrödingerization-form problems. We provide a detailed implementation and error analysis. Furthermore, we incorporate a block preconditioning technique to achieve nearly linear scaling in the condition number, thereby attaining near-optimal query complexity.

arXiv:2508.13510•Aug 19, 2025•0 citations

Quantum algorithms for the fractional Poisson equation via rational approximation

Yin Yang, Yue Yu, Long Zhang +1 more

This paper presents a quantum algorithm for solving the fractional Poisson equation \((-Δ)^s u = f\) with \(s \in (0,1)\) on bounded domains. The proposed approach combines rational approximation techniques with quantum linear system solvers to achieve exponential quantum advantage. The rational approximation represents the inverse fractional Laplacian as a weighted sum of standard resolvents, transforming the original nonlocal problem into a collection of shifted integer-order partial differential equations. These equations are consolidated into a single large linear system through a modified right-hand side construction that simplifies the quantum implementation. To enable practical implementation, we develop explicit quantum circuits via the Schrödingerization technique, which converts the non-unitary dynamics of the linear system into a higher-dimensional Schrödinger-type equation, allowing the use of standard Hamiltonian simulation. The circuit construction leverages the decomposition of shift operators to realize the discrete Laplacian and employs controlled operations to implement the select oracle. Under finite difference discretization, we provide detailed algorithmic procedures utilizing block-encoding techniques for the coefficient matrices. A comprehensive complexity analysis demonstrates that the quantum algorithm achieves a dependence on the inverse mesh size \(h^{-1}\) that is independent of the spatial dimension \(d\), in stark contrast to classical methods which suffer from exponential growth in high dimensions. This establishes an exponential quantum advantage for high-dimensional fractional problems, effectively overcoming the curse of dimensionality that limits classical approaches.

quant-pharXiv:2604.00603•Apr 2, 2026•0 citations

Quantum Domain Decomposition for Preconditioning the Finite Element Method

Elise Fressart, Michel Nowak, Nicole Spillane

Even in cases where quantum linear solvers provide significant speedup compared to their classical counterparts, their performance depends on some of the same parameters. In particular, the condition number of the matrix which is to be inverted is a decisive parameter. A well known classical, and now quantum, remedy is to precondition the linear system $A x = b$ by premultiplying it by a matrix $H$ in such a way that the condition number of $HA$ is significantly smaller than the condition number of $A$. In this work, we focus on a family of preconditioners called domain decomposition. First, we prove that it is feasible to apply quantum domain decomposition. We provide upper bounds for the block-encoding parameters of the Poisson problem discretized by the finite element method and preconditioned by the two-level Additive Schwarz preconditioner (one of the most fundamental domain decomposition techniques). From these bounds, we deduce the complexity of the quantum linear system solver. Second, we focus on a particular choice of local solver within the domain decomposition preconditioner by applying recent work by [Deiml and Peterseim, \textit{Math. Comput.}, 2025] on the Bramble--Pasciak--Xu (BPX) preconditioner. Finally, we provide details on how the operators are implemented.

math.NACross-listedarXiv:2605.26090•May 26, 2026•0 citations
We present a quantum preconditioning framework for solving linear systems arising from a finite difference discretization of the Poisson equation. It is based on the combination of the Schrödingerization technique \cite{JLY22b,JLYPRL24} and the BPX multilevel preconditioner in order to achieve near-optimal complexity. The Schrödingerization technique transforms linear partial and ordinary differential equations into Schrödinger-type systems with unitary evolution in one higher dimension, making them suitable for quantum simulation. A key contribution is a structure-aware construction of the block-encoding for the symmetrically preconditioned matrix AS=S⊤ASA_S = S^\top A SAS​=S⊤AS, where AAA is the stiffness matrix and SSS encodes the BPX preconditioner in factored form. By establishing a novel commuting identity, we avoid the unfavorable normalization scaling that would otherwise arise from naive multiplication of block-encodings. This yields an exact block-encoding of ASA_SAS​ with normalization O(d2(L+1))\mathcal{O}(d^2(L+1))O(d2(L+1)), where ddd is the spatial dimension and LLL is the number of levels. Combined with the Schrödingerization-based Hamiltonian simulation, the overall quantum algorithm achieves a query complexity of O(poly(d)ε−1polylog(ε−1))\mathcal{O}\big(\mathrm{poly}(d)\varepsilon^{-1} \mathrm{polylog}(\varepsilon^{-1}) \big)O(poly(d)ε−1polylog(ε−1)) for estimating linear functionals of the solution to a given tolerance ε\varepsilonε.
We develop a quantum algorithm for solving high-dimensional fractional Poisson equations. By applying the Caffarelli-Silvestre extension, the ddd-dimensional fractional equation is reformulated as a local partial differential equation in d+1d+1d+1 dimensions. We propose a quantum algorithm for the finite element discretization of this local problem, by capturing the steady-state of the corresponding differential equations using the Schrödingerization approach from \cite{JLY22SchrShort, JLY22SchrLong, analogPDE}. The Schrödingerization technique transforms general linear partial and ordinary differential equations into Schrödinger-type systems, making them suitable for quantum simulation. This is achieved through the warped phase transformation, which maps the equation into a higher-dimensional space. We provide detailed implementations of the method and conduct a comprehensive complexity analysis, which can show up to exponential advantage -- with respect to the inverse of the mesh size in high dimensions -- compared to its classical counterpart. Specifically, while the classical method requires O~(d1/233d/2h−d−2)\widetilde{\mathcal{O}}(d^{1/2} 3^{3d/2} h^{-d-2})O(d1/233d/2h−d−2) operations, the quantum counterpart requires O~(d33d/2h−2.5)\widetilde{\mathcal{O}}(d 3^{3d/2} h^{-2.5})O(d33d/2h−2.5) queries to the block-encoding input models, with the quantum complexity being independent of the dimension ddd in terms of the inverse mesh size h−1h^{-1}h−1. Numerical experiments are conducted to verify the validity of our formulation.
Quantum linear systems algorithms (QLSAs) aim to solve linear systems $A\bb{x}=\bb{b}$ exponentially faster than classical methods under certain conditions. In this work, we develop quantum algorithms for solving linear algebraic equations from an ODE-based perspective. Inspired by the linear combination of Hamiltonian simulation (LCHS) representation in the Fourier approach \cite{Childs2017QLSA}, we express the solution $\bb{x}$ as a linear combination of solutions to a system of linear convection equations, which become Schrödinger-type equations with unitary evolutions in the Fourier domain. We refer to this representation as LC-Schrödingerization. Based on this result, we construct an LCHS-based quantum algorithm with two LCHS instances: one for time-marching and one for numerical integration. The key construction uses the derivative of a Gaussian-smoothed hat function and recovers the solution over a fixed auxiliary interval. This permits a truncation time independent of the target accuracy and avoids the loss in success probability from selecting a single grid point. Periodization and explicit Fourier coefficients provide the corresponding projection error bounds. Under the stated oracle assumptions and given a constant-factor estimate of the solution norm, direct simulation of the select operators and block preconditioning achieve the optimal matrix-query complexity O(κAlog⁡1ε)\mathcal{O}(κ_A\log\frac1\varepsilon)O(κA​logε1​) without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.
We present a structure-aware construction of quantum BPX preconditioners for Q1 finite element discretizations of constant-coefficient reaction--diffusion equations on the unit cube, including the Poisson equation. Building on existing quantum finite element and finite difference methods, we express the preconditioned operator through explicit one-dimensional maps, tensor products, and norm-preserving interlevel transfers. Symmetric preconditioning gives multilevel coefficients, and its favorable conditioning alone does not ensure efficient recovery of a state in the original finite element nodal basis. We instead use the local L2L^2L2-orthonormal basis underlying the construction as the output representation of the same finite element function. Its coefficient norm equals the continuous L2L^2L2 norm. Assuming direct access to the preconditioned right-hand side, we prepare this orthonormal coefficient state with a represented function error at most ε\varepsilonε. The expected query complexity is O ⁣(dL3∥f∥L2∥u∥L2log⁡ ⁣(2+L∥f∥L2ε)), \mathcal{O}\!\Big(dL^3\frac{\|f\|_{L^2}}{\|u\|_{L^2}} \log\!\Big(2+\frac{L\|f\|_{L^2}}{\varepsilon}\Big)\Big), O(dL3∥u∥L2​∥f∥L2​​log(2+εL∥f∥L2​​)), where uuu is the exact solution, fff is the right-hand side, ddd is the spatial dimension, and L=log⁡2(1/h)L=\log_2(1/h)L=log2​(1/h) for mesh width hhh. The bound holds for 0<ε≤∥u∥L2/20<\varepsilon\le\|u\|_{L^2}/20<ε≤∥u∥L2​/2 and depends only polylogarithmically on mesh refinement for fixed continuous data. We also analyze linear-functional estimation and illustrate the construction and continuous error bounds with a one-dimensional UnitaryLab experiment.
We develop a quantum algorithm for linear algebraic equations $ A\bb{x} = \bb{b} $ from the perspective of Schrödingerization-form problems, which are characterized by a system of linear convection equations in one higher dimension. When $ A $ is positive definite, the solution $ \bb{x} $ can be interpreted as the steady-state solution to a system of linear ordinary differential equations (ODEs). This ODE system can be solved by using the linear combination of Hamiltonian simulation (LCHS) method in \cite{ACL2023LCH2}, which serves as the continuous implementation of the Fourier transform in the Schrödingerization method from \cite{JLY22SchrShort, JLY22SchrLong}. Schrödingerization transforms linear partial differential equations (PDEs) and ODEs with non-unitary dynamics into Schrödinger-type systems via the so-called warped phase transformation that maps the equation into one higher dimension. When $ A $ is a general Hermitian matrix, the inverse matrix can still be represented in the LCHS form in \cite{ACL2023LCH2}, but with a kernel function based on the Fourier approach in \cite{Childs2017QLSA}. Although this LCHS form provides the steady-state solution to a system of linear ODEs associated with the least-squares equation, applying Schrödingerization to this least-squares system is not appropriate, as it results in a much larger condition number. We demonstrate that in both cases, the solution $ \bb{x} $ can be expressed as the LCHS of Schrödingerization-form problems. We provide a detailed implementation and error analysis. Furthermore, we incorporate a block preconditioning technique to achieve nearly linear scaling in the condition number, thereby attaining near-optimal query complexity.
This paper presents a quantum algorithm for solving the fractional Poisson equation (−Δ)su=f(-Δ)^s u = f(−Δ)su=f with s∈(0,1)s \in (0,1)s∈(0,1) on bounded domains. The proposed approach combines rational approximation techniques with quantum linear system solvers to achieve exponential quantum advantage. The rational approximation represents the inverse fractional Laplacian as a weighted sum of standard resolvents, transforming the original nonlocal problem into a collection of shifted integer-order partial differential equations. These equations are consolidated into a single large linear system through a modified right-hand side construction that simplifies the quantum implementation. To enable practical implementation, we develop explicit quantum circuits via the Schrödingerization technique, which converts the non-unitary dynamics of the linear system into a higher-dimensional Schrödinger-type equation, allowing the use of standard Hamiltonian simulation. The circuit construction leverages the decomposition of shift operators to realize the discrete Laplacian and employs controlled operations to implement the select oracle. Under finite difference discretization, we provide detailed algorithmic procedures utilizing block-encoding techniques for the coefficient matrices. A comprehensive complexity analysis demonstrates that the quantum algorithm achieves a dependence on the inverse mesh size h−1h^{-1}h−1 that is independent of the spatial dimension ddd, in stark contrast to classical methods which suffer from exponential growth in high dimensions. This establishes an exponential quantum advantage for high-dimensional fractional problems, effectively overcoming the curse of dimensionality that limits classical approaches.
Even in cases where quantum linear solvers provide significant speedup compared to their classical counterparts, their performance depends on some of the same parameters. In particular, the condition number of the matrix which is to be inverted is a decisive parameter. A well known classical, and now quantum, remedy is to precondition the linear system Ax=bA x = bAx=b by premultiplying it by a matrix HHH in such a way that the condition number of HAHAHA is significantly smaller than the condition number of AAA. In this work, we focus on a family of preconditioners called domain decomposition. First, we prove that it is feasible to apply quantum domain decomposition. We provide upper bounds for the block-encoding parameters of the Poisson problem discretized by the finite element method and preconditioned by the two-level Additive Schwarz preconditioner (one of the most fundamental domain decomposition techniques). From these bounds, we deduce the complexity of the quantum linear system solver. Second, we focus on a particular choice of local solver within the domain decomposition preconditioner by applying recent work by [Deiml and Peterseim, \textit{Math. Comput.}, 2025] on the Bramble--Pasciak--Xu (BPX) preconditioner. Finally, we provide details on how the operators are implemented.