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

• URL: http://arxiv.org/abs/2606.01270v1
• Date: Sun, 31 May 2026 14:47:58 GMT
• Title: Toward Efficient End-to-End Quantum Elliptic PDE Solvers: a Multilevel Correction Algorithm for Direct Observable Estimation
• Abstract summary: 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.
• Score: 3.3636842548621275
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A central test case for quantum linear system algorithms (QLSA) is elliptic PDEs after a finite element discretization. Most existing analyses focus on preparing a normalized solution state. But an end-to-end quantum PDE solver must also extract physical quantities of interest, such as fluxes, currents, tractions, and energy. These outputs require quantum measurement, and their observable norms may grow like $h^{-χ} $ with mesh size $h $, creating a readout bottleneck even when a quantum preconditioner reduces the condition-number dependence on $h$. We present a multilevel framework for this readout problem, motivated by the variance-reduction mechanism of multilevel Monte Carlo (MLMC), which is naturally compatible with a multi-level finite element discretization. Instead of estimating the full fine-grid observable directly, the method estimates a telescoping sum of interlevel corrections, so that the fine-coarse cancellation is exposed before quantum measurement. Our algorithm is based on Schur-complement factorization of the corrected Green's operator through a Ritz-complement map. For quantities of interest with readout order $χ\leq 2$, the multilevel estimator removes the polynomial $h$-dependent readout overhead. With amplitude estimation, the remaining statistical dependence is $ \widetilde{O}(1/\varepsilon)$, i.e., Heisenberg scaling in the inference precision up to logarithmic factors and with direct sampling, the complexity is reduced to standard Monte Carlo scaling $\widetilde{O}(1/ε^2)$.

Related papers

• 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)
• Exponential Reduction of Mesh Dependence in Quantum Estimation of Parabolic PDE Observables [3.3636842548621275]
  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.
  arXiv  Detail & Related papers  (2026-07-20T16:09:24Z)
• A Residual-Based Quantum Linear System Algorithm with Dynamic Stopping and Applications to Elliptic PDEs [3.3636842548621275]
  Quantum linear-system algorithms (QLSAs) have rigorous worst-case complexity guarantees, but their runtimes are often chosen from spectral information assumed in advance.<n>What is largely lacking is an a posteriori progress flag: most QLSA, unlike the classical counterparts, do not provide a built-in mechanism to signal whether a particular instance has already converged.<n>We design an augmented dynamics with residual variables, in which measuring a residual register gives an on-the-fly convergence indicator.
  arXiv  Detail & Related papers  (2026-05-07T15:22:55Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Towards End-to-End Quantum Estimation of Non-Hermitian Pseudospectra [7.8040425216185225]
  Non-Hermitian many-body systems can be spectrally unstable, so small perturbations may induce large eigenvalue shifts.<n>The pseudospectrum quantifies this instability and provides a perturbation-robust diagnostic.<n>We show that deciding whether a point $zinmathbbC$ is $$-close to the spectrum is PSPACE-hard for $5$-local operators.
  arXiv  Detail & Related papers  (2026-03-17T07:44:04Z)
• Heisenberg-limited adaptive gradient estimation for multiple observables [0.39102514525861415]
  In quantum mechanics, measuring the expectation value of a general observable has an inherent statistical uncertainty.<n>We provide an adaptive quantum algorithm for estimating the expectation values of $M$ general observables within root mean squared error.<n>Our method paves a new way to precisely understand and predict various physical properties in complicated quantum systems using quantum computers.
  arXiv  Detail & Related papers  (2024-06-05T14:16:47Z)
• 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)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  We present quantum algorithms for sampling from nonlogconcave probability distributions. $f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
  arXiv  Detail & Related papers  (2023-10-17T17:55:32Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Differentially Quantized Gradient Methods [53.3186247068836]
  We show that Differentially Quantized Gradient Descent (DQ-GD) attains a linear contraction factor of $maxsigma_mathrmGD, rhon 2-R$. No algorithm within a certain class can converge faster than $maxsigma_mathrmGD, 2-R$.
  arXiv  Detail & Related papers  (2020-02-06T20:40:53Z)

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.