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

• URL: http://arxiv.org/abs/2607.18113v1
• Date: Mon, 20 Jul 2026 16:09:24 GMT
• Title: Exponential Reduction of Mesh Dependence in Quantum Estimation of Parabolic PDE Observables
• Abstract summary: We develop a quantum PDE algorithm that estimates linear and quadratic observables and places fine-coarse cancellation inside the circuit before measurement.<n>We also give a non-Fourier realization based on energyorthogonal dyadic midpoint details in one dimension.
• Score: 3.3636842548621275
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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}$.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Poisson-Compiled Quantum Singular Value Transformation for Power-Exponential Dissipation [2.1496959255800188]
  We study quantum implementations of the contraction $exp(T H)$ for $H=Hdaggersucceq0$ and $>0$.<n>Nearest-neighbor Laplacians give a unit-normalized shifted signal.<n>We establish a noncommutative Weyl-Poisson identity compatible with LCHS quadrature bounds.
  arXiv  Detail & Related papers  (2026-08-04T22:49:03Z)
• A Provable Oracle-Free Quantum Algorithm for Nonlinear Dynamics on Hybrid Oscillator-Qubit Processors [14.814423713691623]
  We develop a hybrid qubit-qumode algorithm for nonlinear ordinary differential equations of the form $dotmathbfx=mathbff(mathbfx)$ with warped degree$L$.<n>The algorithm propagates the state density and returns the trajectory as the peak of that density in the small-noise limit.
  arXiv  Detail & Related papers  (2026-07-30T17:10:47Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Efficient Quantum Circuits for Coherent Conversion Between General First- and Second-Quantized Many-Body Representations [1.6089851562703383]
  We construct an explicit $Q$, with inverse $Qdagger$, that maps a first-quantized state to its fixed-$N$ occupation-number form.<n>The conversion is symmetry-agnostic at the input yet fully resolved at the output, and it applies uniformly to bosonic, fermionic, and parastatistical sectors.
  arXiv  Detail & Related papers  (2026-06-23T18:00:04Z)
• Is Spurious Correlation Removal Always Learnable? [56.28155520961125]
  Invariant learning can fail even when the structure is statistically identifiable.<n>We show a conditional computational barrier: under a black-box samplable supervised sparse recovery primitive, there exist emphamplable multi-dimensional environments.<n>Synthetic and real datasets illustrate the predicted gaps and transitions and motivate simple diversity diagnostics.
  arXiv  Detail & Related papers  (2026-06-11T05:49:43Z)
• Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation [3.3636842548621275]
  A central test case for quantum linear system algorithms (QLSA) is elliptic PDEs after a finite element discretization.<n>We present a multilevel framework for this readout problem, motivated by the variance-reduction mechanism of multilevel Monte Carlo.<n>Our algorithm is based on Schur-complement factorization of the corrected Green's operator through a Ritz-complement map.
  arXiv  Detail & Related papers  (2026-05-31T14:47:58Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Transmutation based Quantum Simulation for Non-unitary Dynamics [35.35971148847751]
  We present a quantum algorithm for simulating dissipative diffusion dynamics generated by positive semidefinite operators of the form $A=Ldagger L$.<n>Our main tool is the Kannai transform, which represents the diffusion semigroup $e-TA$ as a Gaussian-weighted superposition of unitary wave propagators.
  arXiv  Detail & Related papers  (2026-01-07T05:47:22Z)
• A Quantum Algorithm for the Finite Element Method [0.0]
  finite element method (FEM) is a cornerstone numerical technique for solving partial differential equations (PDEs)<n>We present $textbfQu-FEM$, a fault-tolerant era quantum algorithm for the finite element method.
  arXiv  Detail & Related papers  (2025-10-20T23:00:12Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems.<n>Our framework provides a streamlined approach for constructing coresets and offers significant runtime improvements in applications such as clustering, regression, and low-rank approximation.
  arXiv  Detail & Related papers  (2025-09-20T20:18:49Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.