Quantum algorithms and the finite element method

Ashley Montanaro; Sam Pallister

Source-linked AI summary

Quantum algorithms and the finite element method

Ashley Montanaro, Sam Pallister

arXiv:1512.05903v2Dec 18, 2015quant-ph

TL;DR

The paper asks how much the finite element method can be accelerated by quantum linear-equation algorithms, addressing prior claims of exponential speedup that omitted total accuracy costs. It compares quantum and conjugate-gradient approaches for computing a linear functional of a boundary-value solution. The resulting advantage is polynomial, growing with PDE dimension, while fixed-dimensional smooth problems do not support super-polynomial speedup under the paper's evidence.

Problem
Prior work claimed exponential quantum speedups for finite element problems without fully combining the classical and quantum runtimes needed to reach a predetermined solution accuracy.
Method
The paper compares worst-case quantum linear-equation and standard classical algorithms for approximating a linear functional of an elliptic PDE boundary-value solution via the finite element method.
Results
The quantum algorithm achieves at most polynomial speedup for fixed-dimensional smooth solutions, while its accuracy scaling can outperform the classical algorithm as dimension increases.
Takeaways & Limitations
Potentially substantial quantum advantages remain concentrated in higher-dimensional problems or problems whose solutions have large higher-order derivatives.

Abstract

from arXiv · show

The finite element method is used to approximately solve boundary value problems for differential equations. The method discretises the parameter space and finds an approximate solution by solving a large system of linear equations. Here we investigate the extent to which the finite element method can be accelerated using an efficient quantum algorithm for solving linear equations. We consider the representative general question of approximately computing a linear functional of the solution to a boundary value problem, and compare the quantum algorithm's theoretical performance with that of a standard classical algorithm -- the conjugate gradient method. Prior work had claimed that the quantum algorithm could be exponentially faster, but did not determine the overall classical and quantum runtimes required to achieve a predetermined solution accuracy. Taking this into account, we find that the quantum algorithm can achieve a polynomial speedup, the extent of which grows with the dimension of the partial differential equation. In addition, we give evidence that no improvement of the quantum algorithm could lead to a super-polynomial speedup when the dimension is fixed and the solution satisfies certain smoothness properties.

I. INTRODUCTION

The paper evaluates whether quantum linear-equation algorithms can accelerate finite element computations when total accuracy costs are included. It finds polynomial rather than generally exponential advantages, with benefits increasing in problem dimension but limited for fixed-dimensional smooth solutions.

I. INTRODUCTION: The finite element method produces sparse linear systems for boundary value problems, making it a natural target for quantum linear-equation algorithms and relevant to applications including mechanics, thermal physics, and fluid dynamics.The systems are generated algorithmically, reducing quantum data-access concerns, and sparsity is typically required for quantum speedup.
I. INTRODUCTION: The study compares quantum and classical worst-case runtimes for approximating a linear functional of an elliptic PDE boundary-value solution.This representative output matches what the quantum algorithm can extract from its encoded solution state.
I. INTRODUCTION: With fixed spatial dimension and sufficiently smooth solutions, the quantum speedup is at most polynomial; in d = 4, the maximal advantage is approximately quadratic.In sufficiently small dimensions with sufficiently smooth solutions, the quantum runtime can be worse than the classical runtime.
I. INTRODUCTION: Large higher-order derivatives and high-dimensional problems are the main regimes identified for potentially substantial quantum advantages.The quantum runtime can depend only on a Sobolev 1-norm under optimal preconditioning, while the classical runtime depends on a higher-order Sobolev seminorm.
I. INTRODUCTION: For accuracy ϵ in dimension d, the classical runtime scales as ϵ^-O(d), whereas the quantum runtime's ϵ-scaling does not depend on d.The resulting advantage can become very significant for higher-dimensional problems, although dimension-dependent constants may be large.
I. INTRODUCTION: Including the accuracy-dependent cost of discretisation and solution extraction can substantially reduce the apparent exponential advantage claimed by prior work.Larger systems reduce discretisation error, while quantum measurement-based extraction has worse accuracy scaling than the classical method.

C. Organisation and notation

The finite element method converts boundary-value PDE problems into finite-dimensional linear systems by using weak formulations, meshes, and basis functions. The framework extends from one-dimensional Poisson problems to more complicated PDEs, domains, and boundary conditions.

Finite element construction: The FEM approximates boundary-value PDE solutions by restricting the weak formulation to a finite-dimensional subspace.The approximate solution and test functions are commonly chosen as piecewise polynomial functions.
Finite element construction: A basis expansion converts the approximate solution into an N-dimensional linear system.Basis functions are selected to satisfy the boundary conditions, and their coefficients determine the approximate solution.
Higher-dimensional generalisation: In higher dimensions, regular domain divisions become meshes of polygons or polyhedra, such as triangles.Each mesh element carries basis functions used to represent the solution.
Scope: The analysis restricts attention to elliptic second-order PDEs while covering examples including electrostatics, subsonic fluid dynamics, and linear elasticity.The restriction avoids technical complications while retaining physically relevant cases.

A. Comparing quantum and classical algorithms for the FEM

The paper compares quantum and classical FEM algorithms through the task of approximating a linear functional of a boundary-value problem's solution. It separates discretisation and solver errors and relates mesh refinement to solution smoothness and accuracy.

Comparison task: The representative task is computing a linear functional of the PDE solution rather than recovering the full solution.The functional is defined using a known function r, and accuracy is measured through the L2 norm.
Approximation errors: The approximate solution has two error sources: discretisation error and error from the iterative linear-system solver.Splitting the target error between these sources provides a sufficient accuracy condition for the final functional estimate.
Approximation errors: A sufficiently fine mesh makes the discretised solution close to the exact solution under fixed dimension, basis degree, mesh regularity, and derivative-existence assumptions.The bound applies to progressively finer triangulated meshes with edge length tending to zero.
Approximation errors: The FEM approximation error obeys ∥u − ũ∥ ≤ C h^(k+1)|u|_(k+1) when the relevant Sobolev seminorm is defined.Here h is the greatest mesh edge length and k is the total degree of the basis polynomials.
Approximation errors: Estimating the required mesh can be difficult because the higher-order Sobolev seminorm |u|_(k+1) may be unknown for complicated boundary-value problems.In the simple example, this quantity equals ∥f∥ and can be calculated explicitly.

C. Classical complexity of the FEM

The classical FEM cost is governed by system size, sparsity, condition number, and solver accuracy. Conjugate gradient yields a runtime polynomial in inverse accuracy for fixed dimension and solution smoothness, with preconditioning improving the condition-number dependence.

Classical solver: Conjugate gradient solves the sparse positive-semidefinite FEM system in time O(Ns√κ log 1/ϵ_CG).Here N is system size, s is the number of nonzeros per row, and κ is the condition number.
Conditioning: For regular FEM meshes, the matrix has s = O(1), λ_max(M) = O(1), λ_min(M) = Ω(N^(-2/d)), and κ = O(N^(2/d)).These scalings determine the unpreconditioned classical runtime.
Preconditioning: Preconditioning replaces M with M′ = PM and can reduce condition-number scaling, although worst-case improvement is not guaranteed.The analysis considers no preconditioning and maximally successful preconditioning as extreme cases.
Preconditioning: The preconditioned matrix may become nonsymmetric, making conjugate gradient's condition-number dependence quadratically worse in general.Under the assumed best-case κ = O(1), this does not change the stated complexity.
Accuracy dependence: For fixed |u|_(k+1) and dimension d, the optimized classical complexity is polynomial in 1/ϵ.The bound is obtained by optimizing over allowed polynomial basis degrees k.

III. SOLVING THE FEM WITH A QUANTUM ALGORITHM

The quantum approach applies a sparse quantum linear-equation algorithm to the FEM system and must also prepare the input state and extract the desired quantity. Efficient state preparation depends on concise, efficiently computable expressions for FEM-derived weights, which are available only in restricted settings.

Quantum linear solver: The Childs–Kothari–Somma algorithm produces |x⟩ for a sparse Hermitian system given matrix-entry and input-state oracles.Its runtime matches the query complexity up to poly(log N) factors.
Quantum FEM complexity: The quantum FEM runtime depends on oracle costs for matrix entries, approximate input-state preparation, condition number, sparsity, and quantity extraction.These components inherit dependence on the desired output accuracy.
Input preparation: Preparing the FEM input state efficiently requires computing weights associated with basis-function integrals in poly(log N) time.The paper uses a state-production scheme based on Zalka, Grover–Rudolph, and Kaye–Mosca rather than assuming quantum RAM.
Input preparation: For polynomial f on a suitably regular mesh, the required sums S(a,b) can have concise explicit forms, including polynomial dependence on a and b in one dimension.Similar efficiency can occur when f is supported on only a few basis elements.
Input-preparation limitation: Efficient weight computation appears challenging for general functions f, and the subsequent bounds assume perfect input-state preparation in poly(log N) time.The paper notes that this general limitation may be unavoidable and treats exact preparation as an assumption for simplicity.

B. Solving the system of linear equations

The QLE algorithm can solve FEM linear systems when matrix and input-state access are efficient, but preconditioning introduces additional quantum-state preparation costs and parameter dependencies.

Efficient sparse-entry access is available for suitably regular finite element meshes, including regular triangulations with efficiently indexed neighboring elements.The matrix-entry oracle can list nonzero locations and values when mesh elements and their neighbors are efficiently mapped and enumerated.
If |f̃⟩ is prepared with ℓ2 error ϵ, the output-state error imposes a stricter preparation requirement of O(N^-2/dϵ) without preconditioning.Exact preparation avoids this particular issue in examples where the input state can be produced exactly.
Preconditioning replaces M with M′ = PM, where a sparse approximate inverse P is chosen to approximate M^-1 and reduce the condition number.The SPAI approach seeks a sparse P, but sparsity of P or PM is not guaranteed while achieving a favorable condition number.
Preparing the preconditioned quantum input requires implementing the nonunitary operation P on |f̃⟩, typically using probabilistic techniques such as a Chebyshev quantum walk.The procedure maps |ψ⟩ to P|ψ⟩/∥P|ψ⟩∥ upon success, with amplification overhead depending on κ(P) and sparsity.
The preconditioned quantum runtime depends on the condition number of P M, the cost of computing P's entries, its sparsity, and the condition number of P.The paper uses optimistic assumptions to obtain a best-case comparison because these parameters can be difficult to estimate beforehand.

C. Measuring the output

The paper extracts a classical linear functional from the QLE output by estimating an inner product, then combines state-preparation, solver, normalization, and measurement errors into an overall runtime.

C. Measuring the output: The representative output task is approximating the L2 inner product ⟨u,r⟩ between the FEM solution and a fixed function r.A state |r⟩ is constructed so that ⟨ũ|r⟩ represents the desired inner product up to an overall scaling factor; uniform r yields a regional average.
C. Measuring the output: Hadamard testing and amplitude estimation estimate ⟨ũ|r⟩ to accuracy ϵ using O(1/ϵ) preparations of |ũ⟩ and |r⟩.This measurement stage is the source of the polynomial accuracy dependence after the QLE state has been produced.
C. Measuring the output: The algorithm estimates ∥ũ∥, prepares copies of |ũ⟩, estimates ⟨r|ũ⟩, and outputs α eN eR as the estimate of R.The total error includes normalization, linear-system, and output-estimation errors.
C. Measuring the output: To achieve overall accuracy ϵ∥r∥, the component accuracies can be chosen as ϵD = O(ϵ), ϵN = O(min{∥eũ∥, ϵ∥ũ∥/∥u∥}), and ϵL, ϵout = O(ϵ∥r∥/(α∥ũ∥)).
D. Overall complexity: The overall runtime combines all algorithmic components, including estimating ∥ũ∥, producing QLE states, and performing amplitude estimation.The resulting bounds depend on discretization, sparsity, condition numbers, solution norms, and preconditioning.
D. Overall complexity: With preconditioning, the quantum runtime has only polylogarithmic dependence on |u|k+1, while without preconditioning its dependence is polynomially better for sufficiently large d.
D. Overall complexity: The accuracy-dependent quantum runtime no longer depends on dimension d, whether or not preconditioning is used, yielding larger speedups for small ϵ and large d.The authors caution that dependence on the discretization constant prevents calling this an exponential speedup in d.
D. Overall complexity: In four dimensions, optimal preconditioning gives better accuracy scaling and a less stringent solution-smoothness requirement than the classical comparison.Without preconditioning, whether quantum outperforms classical depends on ϵ and several norms of the solution.

IV. QUANTUM LOWER BOUNDS

The paper concludes that QLE-based FEM algorithms can provide polynomial quantum speedups, while studying whether stronger speedups are possible.

Polynomial quantum speedups are achievable for FEM, but the paper investigates whether polynomial speedup is the largest possible in fixed dimension with smooth solutions.

A. A general quantum lower bound

The paper develops lower bounds for algorithms that use QLE as a black-box state-producing subroutine, showing that extracting information from nearby output states requires repeated subroutine use.

QLE can produce a well-conditioned sparse-system solution state in polylog(1/ϵ) time, but estimating natural properties of that state may require O(1/ϵ) uses.This motivates lower bounds for the measurement component rather than for state preparation alone.
The query-complexity argument applies to algorithms approximating functions of QLE outputs without using the internal structure of the QLE algorithm.This encompasses the FEM uses of QLE discussed for output extraction.
The lower-bound framework treats QLE as an unknown-state oracle Aψ that maps |0⟩ to |ψ⟩, with arbitrary interspersed unitaries and limited structural knowledge.The FEM interpretation takes |ψ⟩ to be the QLE output state for one approximate BVP solution.
Replacing Aψ by Aφ at each of T oracle calls bounds the final-state distinguishability by accumulating the per-call operator difference.The proof uses the triangle inequality and invariance of Euclidean distance under unitaries.
An algorithm distinguishing input states separated by ϵ must use the QLE subroutine at least Ω(1/ϵ) times to succeed with probability 2/3.

B. Replacing the QLE subroutine with a classical algorithm

The paper argues that, under fixed spatial dimension and sufficient smoothness, QLE-based FEM subroutines can be replaced classically with at most polynomial slowdown. A modified classical procedure reproduces the quantum states efficiently, so any remaining speedup is not from quantum acceleration of FEM.

Classical replacement: Fixed dimension and bounded Sobolev norms allow each FEM instance to be approximately solved classically using a mesh of size poly(1/ϵ).The construction considers T FEM instances in spatial dimension d = O(1), with relevant Sobolev norms bounded by O(1).
Classical replacement: The replacement solves each instance at accuracy max{γ/T, ϵ}, constructs the corresponding quantum state, and maps it from a coarser mesh M′ to the finer mesh M.The mapping is essentially the classical task of expressing each element of M′ in terms of elements of M.
State comparison: Each modified subroutine remains within Euclidean distance O(1/T) of the corresponding original QLE state.The argument uses the accuracy guarantee for the original and new FEM solutions together with the triangle inequality.
Complexity: The modified subroutines run in polynomial time because FEM solving, state preparation, and mesh mapping are all efficient under the stated regularity assumptions.FEM solving uses time poly(T) and a mesh of size poly(T); state construction takes poly(T) time, while mapping is polynomial in the qubit count when meshes are suitably regular.
Complexity: Because the original algorithm solves T instances and acts on n qubits, its runtime is at least max{T, n}, making the replacement at most polynomially slower.The replacement contains no quantum FEM-solving subroutines, so any speedup it retains does not originate from quantum acceleration of FEM.

C. Solving oracular FEM instances

The paper constructs an oracle-accessed FEM instance whose simple solution property encodes unstructured search. Approximating that property therefore inherits quantum and classical query lower bounds, showing that nonsmooth black-box inputs prevent efficient FEM solving.

Hard instance: An oracle-accessed trivial PDE instance asks for the integral ∫_0^1 u(x)^2dx, with f restricted to N possible functions.The construction encodes unstructured search into the input function while keeping the differential equation itself simple.
Hard instance: A smooth bump function f0 is shifted into one of N intervals according to the unique marked oracle index y0.The resulting function, and hence u, is nonzero only on the interval associated with y0.
Reduction: If y0 < N/2, the squared-integral property is at least a positive constant, whereas the opposite half yields the contrasting case.Thus sufficiently accurate integral estimation determines whether the marked index lies below or above N/2.
Lower bounds: The reduction requires Ω(√N) quantum queries and Ω(N) classical queries to the oracle function.The classical lower bound does not contradict the paper’s smooth-solution bound because the constructed solution has large derivative norms.

V. CONCLUSIONS

A fair end-to-end comparison can eliminate an apparent exponential quantum advantage for FEM, while substantial advantages may remain for high derivatives or high spatial dimension. The conclusions are qualified by the simplicity of the classical baseline and practical limits of adaptive schemes.

Conclusions: Accounting for every step needed to produce the desired accurate classical output can make an apparent exponential quantum advantage disappear.The comparison concerns the full complexity of approximately solving the FEM, not only the linear-system subroutine.
Classical baseline: The comparison uses a simple classical FEM algorithm, while adaptive meshes can substantially improve convergence near complex or important regions.The authors suspect advanced classical FEM methods might remove the quantum advantage for solutions with large higher-order derivatives.
Adaptive methods: Perfect adaptive schemes have better discretisation-error scaling when the domain dimension is small and fixed, but achieving that scaling effectively in practice is not always apparent.The quantum algorithm might also be substantially improved using similar adaptive schemes.

Appendix A: Use of HHL for approximating the norm of the solution

The appendix sketches how HHL complexity for approximating the solution norm depends on acceptance-probability estimation and repeated subroutines. Later quantum linear-equation algorithms improve some parameters for producing |x⟩, but their benefit for norm estimation is unclear.

HHL setup: HHL approximates ∥x∥ to relative accuracy ϵ for an s-sparse Hermitian system with eigenvalues bounded by 1 and condition number κ.The acceptance probability of the subroutine Psim is approximately p := ∥A^-1|b⟩∥^2/κ^2.
HHL complexity: Estimating Psim’s acceptance probability to additive error O(ϵp) requires O((sκ/ϵ) poly log(sκ/ϵ)) uses of the matrix-entry procedure PA.The runtime has the same scaling up to polylogarithmic factors in N, s, κ, and ϵ.
HHL complexity: The number of uses of Pb is O(κ/ϵ) in the norm-estimation procedure.This contributes directly to the dependence on condition number and target accuracy.
Scope: Subsequent quantum linear-equation algorithms improve dependence on κ, ϵ, or both for producing |x⟩, but improved norm-estimation accuracy is not obvious.The appendix therefore does not directly establish a better complexity for approximating ∥x∥ using those later algorithms.