Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation
Abstract
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) 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≤χ≤2, can be estimated to additive accuracy ε at cost Õ(ε−1) using amplitude estimation or Õ(ε−2) using direct sampling, with only polylogarithmic dependence on the inverse finest mesh width 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.
Related
- Efficient preparation of spin-squeezed states with Grover's algorithm
- Efficient Quantum Error Correction from Three Dimensional Qubit Control
- Joint-decoupled iterative CBCT reconstruction with hybrid scatter estimation and voxel-adaptive beam hardening correction
- Compiling the 2D Fermi-Hubbard ground-state energy estimation algorithm for active volume quantum architectures
- A Matrix-Based Sensor Fusion Algorithm for Nine-D.o.F. IMU Attitude Estimation
BibTeX
@misc{li2026toward,
title = {{Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation}},
author = {Xiantao Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.01270},
eprint = {2606.01270},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.01270},
}
RIS
TY - UNPB
TI - Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation
AU - Xiantao Li
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2606.01270
UR - https://arxiv.org/abs/2606.01270
AB - 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≤χ≤2, can be estimated to additive accuracy ε at cost Õ(ε^−1) using amplitude estimation or Õ(ε^−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.
ER -