Quantum-inspired Methods for Finite-element Discretizations of the High-dimensional Poisson Equation

Jul 16, 2026

Upload by Asher

Quantum linear system algorithms have been applied to partial differential equations, especially in high-dimensional regimes, with reported exponential speedups in dimension. Randomized and quantum-inspired classical linear solvers have also emerged, often with complexity comparable to quantum methods. This paper analyzes quantum-inspired classical solvers for finite-element discretizations of high-dimensional Poisson problems, establishing matching upper and lower complexity bounds that rule out exponential speedup in dimension. The results confirm quantum algorithms maintain a decisive advantage for such PDE settings.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages21

Reading Time53 min

Introduction

Quantum algorithms for PDEs

Quantum-inspired classical solvers

Randomized coordinate descent and complexity bounds

arXiv :2607 .06533v1 [math .NA] 7 Jul 2026 QUANTUM-INSPIRED METHODS FOR FINITE-ELEMENT DISCRETIZATIONS OF THE HIGH-DIMENSIONAL POISSON EQUATION∗ XUE WANG†, JAMES H. ADLER‡, AND XIAOZHE HU‡ Abstract. In recent years, quantum linear system algorithms have been applied to partial differential equations (PDEs), particularly in high-dimensional settings, demonstrating an exponential speedup in dimension. Concurrently, randomized and quantum-inspired classical linear solvers have emerged, showing computational complexity comparable to their quantum counterparts in many application areas. In this paper, we investigate the applicability of these quantum-inspired classical algorithms to PDEs. We provide both upper and lower bounds on their computational complexity, proving that these methods cannot achieve exponential speedup in dimension for discretizations of high-dimensional Poisson problems. Our theoretical findings definitively demonstrate that quantuminspired classical algorithms are not competitive with quantum algorithms for solving PDEs, confirming that quantum methods retain a significant advantage for high-dimensional problems. Key words. quantum algorithm, quantum-inspired algorithm, randomized coordinate descent; high-dimensional PDEs; finite-element method MSC codes. 65D40; 65M30; 68Q12; 68Q25 1. Introduction. When solving a general partial differential equation (PDE) ind-dimensions, (1 . 1) Lu = f, in D ⊂ Rd , where L denotes a general elliptic second-order partial differential operator, most discretizations, such as finite-difference, finite-element, and finite-volume methods, lead to a discrete linear system of equations, (1.2) Au = f , where A is the so-called stiffness matrix. Solving (1.2) is challenging in practice because it is typically large-scale and ill-conditioned. In this work, we consider the Laplacian equation, i.e. , L = −∆, as an example. In this case, the condition number κ (A) grows as N 2/d where N is the total number of degrees of freedom used in the discretization. Thus, in practice, the most time-consuming part of solving PDEs is solving (1.2), especially when N gets larger and larger. Moreover, one must deal with the well-known “curse of dimensionality” as the problem size grows exponentially with respect to the dimension [33, 26] . Much work has been dedicated to overcoming these issues in the classical computing setting [2, 4] . One of the most successful approaches for solving (1.2) in PDE applications is the multigrid (MG) method. MG provides a preconditioner B such that κ (BA) is well-conditioned, providing an improved scaling of the computational complexity of the problem with N. However, as we highlight later, this still does not provide an improved scaling with dimension d. Therefore, we look to quantum computing algorithms instead. ∗ Submitted to the editors DATE. Funding: The work of the last two authors is partially supported by the National Science Foundation (NSF) under grant DMS-2513394 . †School of Mathematics, Shandong University, 250100 Jinan, China ([wangxsdu@mail.sdu.edu.cn](wangxsdu@mail.sdu.edu.cn)) .‡Department of Mathematics, Tufts University, Medford, 02155 MA, USA ([james.adler@tufts.edu](james.adler@tufts.edu)), ([xiaozhe.hu@tufts.edu](xiaozhe.hu@tufts.edu)). 2 X. WANG, J. H. ADLER, AND X. HU Recently, there has been extensive literature for solving PDEs using quantum algorithms, see [9, 3 , 22 , 8 , 20] . Here, we consider the application of quantum algorithms to the finite-element method (FEM) in particular. Following [22], the key idea of quantum FEM is to replace the classical algorithm for solving the linear system (1.2) with a quantum linear solver. There are many quantum linear solvers, i.e. ,[15, 29 , 8 , 30 , 1 , 5 , 18], including an approach proposed in [8], which is an improvement of the famous Harrow, Hassidim, and Lloyd (HHL) algorithm [15, 29] . For more recent developments of quantum linear solvers, we refer to the fol

FAQs

What problem does the paper study?

The paper studies how quantum-inspired classical linear solvers perform when applied to finite-element discretizations of high-dimensional Poisson problems.

What is the main theoretical result about complexity in dimension?

The paper provides upper and lower bounds showing these quantum-inspired methods cannot achieve exponential speedup in dimension for the considered high-dimensional Poisson discretizations.

How does the paper compare classical quantum-inspired methods with quantum algorithms?

It concludes that quantum-inspired classical algorithms are not competitive with quantum algorithms for solving these PDEs, while quantum methods retain a significant advantage in high-dimensional settings.

Jul 16, 2026

Upload by Asher