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

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

Yin Yang, Yue Yu, Long Zhang

Published Oct 4, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2610.06987

Related papers

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

Shi Jin, Nana Liu, Chuwen Ma +1 more

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$.

arXiv:2505.06866•May 11, 2025•0 citations

Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation

Xiantao Li

Spatial derivatives pose a basic challenge for quantum algorithms for partial differential equations: their standard discretizations have operator norms that grow as the mesh is refined, leading to large block-encoding normalization factors. Even when preconditioning improves access to the solution, estimating derivative-dependent physical observables can reintroduce polynomial dependence on the inverse mesh width. We develop a multilevel quantum algorithm for estimating linear and quadratic observables of elliptic equations that addresses this readout cost. The algorithm decomposes the output into corrections across nested discretizations and realizes fine--coarse cancellation coherently, before measurement. A Ritz-complement factorization connects the $O(h^2)$ size of the corrected response with a block encoding at the same scale, allowing this decay to offset growing readout normalizations. Under efficient quantum access to the corrected coordinates, input data, and readouts, observables with readout scale $O(h^{-χ})$, $0\leχ\le2$, can be estimated to additive accuracy $ε$ at cost $\widetilde O(ε^{-1})$ using amplitude estimation or $\widetilde O(ε^{-2})$ using direct sampling, with only polylogarithmic dependence on the inverse finest mesh width $h_L^{-1}$. We give explicit constructions of the required operator oracles for one-dimensional piecewise linear finite elements with diffusion piecewise constant on a fixed coarsest partition, and for Fourier spectral hierarchies. Output-specific bias estimates connect the discrete results to continuum accuracy.

quant-pharXiv:2606.01270•Jun 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

Quantum realization of the finite element method

M. Deiml, Daniel Peterseim

This paper presents a quantum algorithm for the solution of prototypical second-order linear elliptic partial differential equations discretized by d d -linear finite elements on Cartesian grids of a bounded d d -dimensional domain. An essential step in the construction is a BPX preconditioner, which transforms the linear system into a sufficiently well-conditioned one, making it amenable to quantum computation. We provide a constructive proof demonstrating that, for any fixed dimension, our quantum algorithm can compute suitable functionals of the solution to a given tolerance t o l \mathtt {tol} with an optimal complexity of order t o l − 1 \mathtt {tol}^{-1} up to logarithmic terms, significantly improving over existing approaches. Notably, this approach does not rely on the regularity of the solution and achieves a quantum advantage over classical solvers already in two dimensions, whereas prior quantum methods required at least four dimensions for asymptotic benefits. We further detail the design and implementation of a quantum circuit capable of executing our algorithm, present simulator results, and report numerical experiments on current quantum hardware, confirming the feasibility of preconditioned finite element methods for near-term quantum computing.

arXiv:2403.19512•Mathematics of Computation•Aug 14, 2025•3 citations

Exponential Reduction of Mesh Dependence in Quantum Estimation of Parabolic PDE Observables

Xiantao Li

Can a quantum PDE algorithm avoid the polynomial cost of resolving a fine spatial mesh? For standard fixed-order discretizations, direct classical methods require work polynomial in $h^{-1}$, or equivalently in the number of spatial degrees of freedom $N_h=Θ(h^{-d})$. Direct quantum implementations of a parabolic semigroup still have coherent complexity $\widetilde{\mathcal O}(\sqrt{T}/h)$, and gradient-dependent observables such as heat flux and dissipation introduce additional mesh dependence. Decay of the solution norm will further suppress the postselection probability for preparing a normalized final state. We develop a multilevel quantum algorithm that estimates linear and quadratic observables $directly$ and places the fine--coarse cancellation inside the circuit before measurement. A contour-based LCU reconstructs each target-time correction from a coherent family of shifted resolvent differences. Rather than block encoding the fine and coarse inverses separately, we encode their difference through a shifted Ritz--Schur factorization, exposing its $\mathcal O(h_\ell^2)$ two-grid normalization. For Fourier hierarchies, the corresponding SELECT oracle consists of a quantum Fourier or sine transform, a spectral-band selector, and reversible diagonal arithmetic. We also give a non-Fourier realization based on energy-orthogonal dyadic midpoint details in one dimension, together with structured tensor-product extensions under fixed-rank coefficient and access assumptions. For readouts with derivative order $0\leχ\le2$, optimized amplitude estimation removes $all$ polynomial dependence on the finest mesh size. Under the stated access assumptions, both linear and quadratic observables can be estimated with complexity $\widetilde{\mathcal O}(1+(Tε)^{-1})$, with only polylogarithmic dependence on $h^{-1}$.

quant-pharXiv:2607.18113•Jul 21, 2026•0 citations

Quantum Algorithms for Heterogeneous PDEs: The Neutron Diffusion Eigenvalue Problem

Andrew M. Childs, Lincoln Johnston, Brian Kiedrowski +2 more

We develop a quantum algorithm to solve a type of linear reaction-diffusion equation, the neutron diffusion (generalized) k-eigenvalue problem that establishes nuclear criticality. The algorithm handles an equation with piecewise constant coefficients, describing a problem in a heterogeneous medium. We apply uniform finite elements and show that the quantum algorithm provides significant polynomial end-to-end speedup over classical uniform finite element methods in the cases tested, although nonuniform classical methods can perform much better than uniform ones. Our work leverages recent advances in quantum linear systems--fast inversion and quantum preconditioning--and uses Hamiltonian simulation as a subroutine. Our results suggest that quantum algorithms may provide speedups for heterogeneous PDEs, though the extent of this advantage over the fastest classical algorithm depends on the effectiveness of other classical approaches such as nonuniform or adaptive meshing for a given problem instance.

quant-pharXiv:2604.05098•Apr 8, 2026•0 citations
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 [ \mathcal{O}!\Big(dL^3\frac{|f|{L^2}}{|u|{L^2}} \log!\Big(2+\frac{L|f|_{L^2}}{\varepsilon}\Big)\Big), ] 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 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ε.
Spatial derivatives pose a basic challenge for quantum algorithms for partial differential equations: their standard discretizations have operator norms that grow as the mesh is refined, leading to large block-encoding normalization factors. Even when preconditioning improves access to the solution, estimating derivative-dependent physical observables can reintroduce polynomial dependence on the inverse mesh width. We develop a multilevel quantum algorithm for estimating linear and quadratic observables of elliptic equations that addresses this readout cost. The algorithm decomposes the output into corrections across nested discretizations and realizes fine--coarse cancellation coherently, before measurement. A Ritz-complement factorization connects the O(h2)O(h^2)O(h2) size of the corrected response with a block encoding at the same scale, allowing this decay to offset growing readout normalizations. Under efficient quantum access to the corrected coordinates, input data, and readouts, observables with readout scale O(h−χ)O(h^{-χ})O(h−χ), 0≤χ≤20\leχ\le20≤χ≤2, can be estimated to additive accuracy εεε at cost O~(ε−1)\widetilde O(ε^{-1})O(ε−1) using amplitude estimation or O~(ε−2)\widetilde O(ε^{-2})O(ε−2) using direct sampling, with only polylogarithmic dependence on the inverse finest mesh width hL−1h_L^{-1}hL−1​. We give explicit constructions of the required operator oracles for one-dimensional piecewise linear finite elements with diffusion piecewise constant on a fixed coarsest partition, and for Fourier spectral hierarchies. Output-specific bias estimates connect the discrete results to continuum accuracy.
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.
This paper presents a quantum algorithm for the solution of prototypical second-order linear elliptic partial differential equations discretized by d d -linear finite elements on Cartesian grids of a bounded d d -dimensional domain. An essential step in the construction is a BPX preconditioner, which transforms the linear system into a sufficiently well-conditioned one, making it amenable to quantum computation. We provide a constructive proof demonstrating that, for any fixed dimension, our quantum algorithm can compute suitable functionals of the solution to a given tolerance t o l \mathtt {tol} with an optimal complexity of order t o l − 1 \mathtt {tol}^{-1} up to logarithmic terms, significantly improving over existing approaches. Notably, this approach does not rely on the regularity of the solution and achieves a quantum advantage over classical solvers already in two dimensions, whereas prior quantum methods required at least four dimensions for asymptotic benefits. We further detail the design and implementation of a quantum circuit capable of executing our algorithm, present simulator results, and report numerical experiments on current quantum hardware, confirming the feasibility of preconditioned finite element methods for near-term quantum computing.
Can a quantum PDE algorithm avoid the polynomial cost of resolving a fine spatial mesh? For standard fixed-order discretizations, direct classical methods require work polynomial in h−1h^{-1}h−1, or equivalently in the number of spatial degrees of freedom Nh=Θ(h−d)N_h=Θ(h^{-d})Nh​=Θ(h−d). Direct quantum implementations of a parabolic semigroup still have coherent complexity O~(T/h)\widetilde{\mathcal O}(\sqrt{T}/h)O(T​/h), and gradient-dependent observables such as heat flux and dissipation introduce additional mesh dependence. Decay of the solution norm will further suppress the postselection probability for preparing a normalized final state. We develop a multilevel quantum algorithm that estimates linear and quadratic observables directlydirectlydirectly and places the fine--coarse cancellation inside the circuit before measurement. A contour-based LCU reconstructs each target-time correction from a coherent family of shifted resolvent differences. Rather than block encoding the fine and coarse inverses separately, we encode their difference through a shifted Ritz--Schur factorization, exposing its O(hℓ2)\mathcal O(h_\ell^2)O(hℓ2​) two-grid normalization. For Fourier hierarchies, the corresponding SELECT oracle consists of a quantum Fourier or sine transform, a spectral-band selector, and reversible diagonal arithmetic. We also give a non-Fourier realization based on energy-orthogonal dyadic midpoint details in one dimension, together with structured tensor-product extensions under fixed-rank coefficient and access assumptions. For readouts with derivative order 0≤χ≤20\leχ\le20≤χ≤2, optimized amplitude estimation removes allallall polynomial dependence on the finest mesh size. Under the stated access assumptions, both linear and quadratic observables can be estimated with complexity O~(1+(Tε)−1)\widetilde{\mathcal O}(1+(Tε)^{-1})O(1+(Tε)−1), with only polylogarithmic dependence on h−1h^{-1}h−1.
We develop a quantum algorithm to solve a type of linear reaction-diffusion equation, the neutron diffusion (generalized) k-eigenvalue problem that establishes nuclear criticality. The algorithm handles an equation with piecewise constant coefficients, describing a problem in a heterogeneous medium. We apply uniform finite elements and show that the quantum algorithm provides significant polynomial end-to-end speedup over classical uniform finite element methods in the cases tested, although nonuniform classical methods can perform much better than uniform ones. Our work leverages recent advances in quantum linear systems--fast inversion and quantum preconditioning--and uses Hamiltonian simulation as a subroutine. Our results suggest that quantum algorithms may provide speedups for heterogeneous PDEs, though the extent of this advantage over the fastest classical algorithm depends on the effectiveness of other classical approaches such as nonuniform or adaptive meshing for a given problem instance.