PaperlayerView exact revision on arXiv

Source-linked AI summary

High-precision quantum algorithms for partial differential equations

Andrew M. Childs, Jin-Peng Liu, Aaron Ostrander

arXiv:2002.07868v2quant-phmath.NA

TL;DR

Prior high-precision quantum PDE algorithms had polynomial dependence on inverse error tolerance, limiting precision scaling for linear PDEs. This paper combines adaptive-order finite differences and spectral methods with high-precision QLSAs, achieving polynomial dependence on dimension and logarithmic dependence on inverse precision for targeted elliptic PDEs.

  • Problem

    Previous quantum algorithms for linear PDEs had complexity poly(1/ϵ), unlike established high-precision quantum algorithms for linear ODEs.

  • Method

    The paper applies high-precision QLSAs to adaptive-order finite-difference systems for Poisson’s equation and spectral systems for more general second-order elliptic PDEs.

  • Results

    poly(d, log(1/ϵ)) complexity is obtained for both approaches, including d^2 poly(log(1/ϵ)) for general second-order elliptic PDEs with Dirichlet boundaries.

  • Takeaways & Limitations

    The algorithms provide the best known dependence on ϵ for Poisson equations with homogeneous boundary conditions and improve dimension dependence for several elliptic-PDE settings.

  • Takeaways & Limitations

    The adaptive FDM is limited to Poisson’s equation with homogeneous boundary conditions, while the spectral algorithm is limited to second-order elliptic PDEs with Dirichlet conditions.

Abstract

from arXiv · show

Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity $\mathrm{poly}(1/ε)$, where $ε$ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be $\mathrm{poly}(d, \log(1/ε))$, where $d$ is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.

1 Introduction

High-dimensional PDEs are difficult for classical methods because their complexity can grow exponentially with dimension, while prior quantum PDE algorithms retained polynomial dependence on inverse precision. This paper introduces adaptive finite-difference and spectral quantum algorithms that achieve polynomial dependence on dimension and logarithmic dependence on inverse precision.

  • Motivation: Classical grid-based methods can require exponential complexity in spatial dimension, whereas quantum states encode solution vectors using only logarithmic space in their length.Classical methods output explicit values, while quantum algorithms output a more compact state representation with more limited direct access to the solution.
  • Prior quantum approaches: Previous quantum FDM, FEM, and FVM approaches had total complexity poly(1/ϵ) because fixed-order discretization errors remained in addition to QLSA or simulation costs.Some earlier circuits used poly(log(1/ϵ)) gates but had poly(1/ϵ) success probability or did not quantify finite-difference approximation errors.
  • Problem and scope: The paper targets quantum states whose amplitudes are proportional to PDE solutions at grid points, rather than estimating a function of the solution.The stated problem concerns linear PDEs on the unit hypercube and assumes global strict diagonal dominance for the elliptic equations considered.
  • Methods: The quantum adaptive FDM varies truncation order with ϵ, while the spectral method uses global basis functions and high-precision QLSAs for the resulting linear systems.Increasing finite-difference order brings matrix eigenvalues closer to those of the continuous Laplacian, improving approximation precision.
  • Results: poly(d, log(1/ϵ)) complexity is achieved by both approaches, improving precision dependence over previous quantum PDE algorithms and dimension dependence over classical methods.The algorithms account for condition numbers and QLSA approximation errors; their complexity also depends logarithmically on high-order derivatives and inhomogeneity.

2 Linear PDEs

Linear PDEs are defined through linear differential operators acting on unknown functions, with ellipticity determined by the highest-order terms. The paper focuses on second-order elliptic boundary-value systems satisfying global strict diagonal dominance and specified oracle-access assumptions.

  • Linear PDEs: A linear PDE has the form L[u](x)=f(x), where L is a linear differential operator combining the solution and its derivatives.The operator order h bounds the total derivative order appearing in its terms.
  • Linear PDEs: For d≥2 the problem is called a multidimensional PDE, while d=1 reduces it to a system of linear ODEs.The spatial variable is a d-dimensional vector.
  • Second-order equations: Second-order linear PDE systems include first- and second-derivative terms, with the Poisson equation as a well-known example.The coefficients and inhomogeneity are functions of the spatial variables.
  • Ellipticity: A linear PDE is elliptic when its highest-order differential operator satisfies the stated ellipticity condition; for second order, this means the leading coefficient matrix is positive- or negative-definite.The Poisson equation is a second-order elliptic PDE.
  • Assumptions: The considered boundary-value problem assumes global strict diagonal dominance, a strengthening of standard strict diagonal dominance that Poisson’s equation satisfies with C=1.The domain is the d-dimensional hypercube, with smooth scalar solution data and boundary conditions.
  • Quantum PDE problem: The quantum task uses coefficient oracles and state-preparation access for boundary data and inhomogeneity to output a state proportional to the solution at interpolation nodes.A weak solution is assumed to exist for the boundary-value problem.

3 Finite difference method

The quantum finite difference method discretizes Poisson’s equation into a high-order linear system and uses a QLSA to produce a quantum state encoding the solution. Adaptive truncation controls approximation error, while condition-number bounds yield polynomial dependence on dimension and logarithmic dependence on inverse error.

  • Complexity: Theorem 1 establishes a quantum algorithm that outputs an ε-close solution state, with its runtime obtained from QLSA complexity, Hamiltonian simulation, and oracle-query bounds.The QLSA uses Fourier-series methods and QFT-based simulation; the supplied passages state the resulting complexity expression only partially.
  • Algorithm: The algorithm applies a quantum finite difference approximation to Poisson’s equation and solves the resulting linear system with a QLSA.It analyzes periodic, Dirichlet, and Neumann boundary conditions.
  • Discretization: The finite difference formula discretizes the domain on a rectangular lattice and approximates derivatives using nearby uniformly spaced values.A central formula of order 2k is used for second derivatives.
  • Linear system: The resulting periodic-boundary matrix is circulant, enabling diagonalization and Hamiltonian simulation with the quantum Fourier transform.The multidimensional operator is constructed as a sum of tensor-product Laplacians.
  • Error analysis: The solution-state vector matches the target quantum state directly, so no post-processing is needed after solving the finite-difference system.The analysis separates finite-difference error from QLSA error and assumes perfect preparation of states proportional to the forcing function.
  • Condition number: κ(L) = O(n2) for the one-dimensional circulant Laplacian, while the d-dimensional operator has κ(L′) = O(dn2).The stated condition-number bound holds when k < (6/π2)1/3n2/3.
  • Adaptive parameters: Adaptive FDM chooses the lattice size n and truncation order 2k based on ε, taking k as large as allowed by the conditioning assumptions.This choice is inspired by classical adaptive finite difference methods.

4 Multi-dimensional spectral method

The paper develops a quantum pseudo-spectral method for multidimensional second-order elliptic PDEs, using basis expansions and transforms to construct a sparse linear system. For smooth solutions, the approximation reaches error ε with n polynomial in log(1/ε).

  • Quantum algorithm: Theorem 2 produces a quantum state whose amplitudes are proportional to the solution at interpolation nodes and are ε-close to the exact solution state.The result covers periodic and non-periodic Dirichlet boundary conditions.
  • Basis construction: The method approximates the PDE solution with Fourier bases for periodic boundaries and Chebyshev polynomials for non-periodic boundaries.The basis choice is tied to the boundary conditions used by the algorithm.
  • Basis construction: The spectral coefficients are determined by enforcing the PDE and boundary conditions at interpolation nodes.The interpolation nodes are uniform grid nodes for periodic conditions and Chebyshev-Gauss-Lobatto nodes for non-periodic conditions.
  • Approximation: For C∞ solutions, achieving approximation error ε requires n = poly(log(1/ε)), whereas C^(r+1) solutions require n = poly(1/ε).The multidimensional expansion contains (n + 1)^d terms.
  • Quantum algorithm: The quantum algorithm restores sparsity in the PDE linear system using quantum transforms before applying quantum linear-system techniques.The underlying multidimensional spectral linear system is otherwise non-sparse.

4.1 Quantum shifted Fourier transform and quantum cosine transform

The section introduces quantum shifted Fourier and cosine transforms as multidimensional tensor-product transforms. Their gate complexities scale linearly with spatial dimension and nearly linearly with the logarithm of the discretization size.

  • QSFT: The QSFT is defined as a quantum analogue of the shifted discrete Fourier transform and is extended to multiple dimensions by tensor products.The multidimensional transform acts across the d registers corresponding to spatial coordinates.
  • QSFT: The multidimensional QSFT has gate complexity O(d log n log log n).The transform is implemented by applying the one-dimensional QSFT to each register.
  • Implementations: The one-dimensional QFT and QCT implementations use decompositions into efficient transforms, permutations, and additional constant-cost operations.These decompositions yield O(log n log log n) complexity for each one-dimensional transform.
  • QCT: The QCT is a quantum analogue of the discrete cosine transform and maps an (n + 1)-dimensional quantum state to another quantum state.It is used for cosine/Chebyshev-type representations.
  • QCT: The multidimensional QCT has gate complexity O(d log n log log n), improving on the classical DCT’s Θ(n log n) gate cost.The multidimensional transform is implemented as a tensor product of one-dimensional QCTs.

4.2 Linear system

The algorithm encodes the differential equation and boundary conditions into a combined linear system, using Fourier or Chebyshev representations and quantum transforms. The resulting system has a unique solution and is designed for quantum linear-system solution.

  • System construction: The quantum PDE solver constructs a linear system encoding the pseudo-spectral approximation of the PDE.QSFT and QCT operations are used to ensure sparsity.
  • Boundary conditions: Fourier and Chebyshev pseudo-spectral representations support periodic and non-periodic Dirichlet boundary conditions, respectively.The solution state is transformed between coefficient and interpolation-node bases using inverse and forward quantum transforms.
  • Approximation: The spectral approximation is ε-close to the exact solution when n = poly(log(1/ε)).The encoded state represents solution values at boundary-condition-appropriate interpolation nodes.
  • System construction: The system combines A x = f for the differential equation with B x = g for the boundary conditions into one system L x = f + g.The boundary conditions are imposed on the boundary faces of the unit hypercube.
  • Well-posedness: The combined matrix L has full rank, so the system has a unique solution that satisfies both the differential equation and boundary conditions.The paper also bounds the condition number of L.

4.3 Condition number

The paper bounds the condition numbers of the linear systems used by its quantum PDE algorithms. The analysis first treats Poisson’s equation and then extends the bounds to general elliptic PDEs.

  • General analysis: The condition-number analysis bounds singular values of the matrices appearing in the combined spectral linear system.The proof handles tensor sums, tensor products, matrix exponentials, and matrix logarithms.
  • Poisson equation: The Poisson system receives a dedicated condition-number bound for Dirichlet boundary conditions when n ≥ 4.The bound is derived from estimates on the extreme singular values of the second-order differential matrices.
  • General elliptic PDEs: The general elliptic-PDE system also has a condition-number bound for n ≥ 4 under the stated Dirichlet-boundary assumptions.The bound depends on coefficient conditions including global strict diagonal dominance.
  • General analysis: The analysis decomposes the system matrix into terms whose singular values can be bounded separately.One term is handled as a tensor sum, while the other is bounded using tensor-product structure.

4.4 State preparation

The state-preparation procedure constructs the right-hand-side state needed by the linear system, using oracle calls, inverse Fourier or cosine transforms, and amplitude amplification. Its total gate and query complexity is O(qd^2 log n log log n).

  • State preparation: The procedure combines the oracles Of and Ox with a d-dimensional inverse QSFT or inverse QCT.The inverse QSFT applies for periodic boundary conditions, while the inverse QCT applies for non-periodic conditions.
  • Amplitude amplification: Amplitude amplification raises the probability of preparing the target state from 1/q^2 to close to 1 using O(q) steps.The target is obtained by measuring the first register in a basis containing the uniform superposition.
  • State preparation: O(qd^2 log n log log n) gates and queries suffice for state preparation.The procedure uses amplitude amplification after a measurement succeeds with probability 1/q^2.
  • Implementation alternative: Direct preparation of |B⟩ may remove the factor q from the overall complexity.This is an alternative implementation condition rather than the default procedure.

4.5 Main result

The main result establishes high-precision quantum algorithms that output states encoding PDE solutions by applying a high-precision QLSA to discretized systems. The resulting complexity bounds include explicit dimension, precision, conditioning, and state-preparation factors.

  • Theorem 2: Theorem 2 produces a quantum state whose amplitudes are proportional to u(x) at interpolation nodes and whose normalized state is ϵ-close to the target.The nodes are uniform-grid nodes for periodic conditions and Chebyshev-Gauss-Lobatto nodes for non-periodic conditions.
  • Linear-system formulation: The algorithm applies a high-precision QLSA to a linear system with dimension (n + 1)^d and boundary-condition-dependent sparsity.The condition number of the system matrix L is bounded by ∥A∥Σ C∥A∥∗(2n)^4.
  • Complexity: The query and gate complexities are given by the bounds established after selecting n to meet the approximation error.The gate complexity exceeds the query complexity by a factor poly(log(d∥A∥Σ/ϵ)).
  • Special case: For Poisson equations with homogeneous boundary conditions, state preparation becomes d poly(log(g′/gϵ)) because transform applications and uniform-superposition postselection can be removed.In this case, ∥A∥Σ = ∥A∥∗ = d and C = 1.

5 Discussion and open problems

The discussion highlights logarithmic dependence on precision and high-order derivatives, while identifying broader PDE classes, boundary conditions, time dependence, dimensional scaling, and practical use as open problems.

  • Summary: The algorithms improve linear-PDE complexity from poly(d, 1/ϵ) to poly(d, log(1/ϵ)).They use high-precision QLSAs together with finite-difference and spectral methods.
  • Scope boundaries: The adaptive FDM is limited to Poisson’s equation with homogeneous boundary conditions, while the spectral algorithm uses second-order elliptic PDEs with Dirichlet conditions.The authors ask whether these methods can extend to other equations and boundary conditions.
  • Open problems: Time- and space-dependent PDEs remain challenging because the quantum Fourier transform cannot be directly applied to ensure sparsity.The discussion also asks whether the dependence on d can be improved.
  • Derivative dependence: Logarithmic dependence on high-order derivatives keeps the algorithms efficient for highly oscillatory solutions with exponentially large derivatives.The discussion states this dependence for both adaptive FDM and spectral methods.
  • Practical application: The practical value of quantum PDE algorithms remains unresolved because useful measurements and efficient oracle implementations require further study.The paper identifies these technical questions as part of determining how the algorithms should be applied.

A An example for solving Poisson’s equation

The appendix illustrates the Poisson-equation algorithms in two dimensions by forming discretized Fourier and Chebyshev linear systems and completing them with boundary conditions. Quantum Fourier or cosine transforms prepare the systems for QLSA solution.

  • Poisson discretization: The two-dimensional appendix example constructs discretized Poisson linear systems and uses boundary conditions to complete them.The completed systems include additional equations and, in the stated example, can be made full rank.
  • Periodic boundary conditions: For periodic conditions, the example uses a truncated Fourier series, a uniform-grid state, an inverse QSFT, and QLSA.The right-hand-side coefficients are prepared at the uniform grid nodes before solving the linear system.
  • Non-periodic boundary conditions: For non-periodic conditions, the example uses a truncated Chebyshev series, Chebyshev-Gauss-Lobatto nodes, an inverse QCT, and QLSA.The Chebyshev difference matrix represents derivatives, and boundary equations complete the system.
  • Chebyshev representation: The Chebyshev construction represents second derivatives with a truncation order reduced by two.The coefficients of the second derivative are determined by higher-order coefficients of the original series.

B Singular values of second-order differential matrices

This section proves singular-value bounds for second-order differential matrices under periodic and non-periodic boundary conditions. The proofs use direct norm calculations and auxiliary linear systems relating vectors x and y.

  • Periodic boundary conditions: The periodic-boundary matrix D^(2)_n has largest and smallest singular values characterized for n ≥ 4.The result is identified through equations (4.59)–(4.62), although the supplied passage does not include the numerical bounds.
  • Periodic boundary conditions: Direct calculations of the l∞ norm, inverse, and Frobenius norm establish the periodic-case singular-value result.The inverse is given entrywise away from the middle index, with entries involving ((k − floor(n/2))π)^2.
  • Non-periodic boundary conditions: For non-periodic boundary conditions, the largest and smallest singular values of D^(2)_n are likewise bounded through direct Frobenius-norm calculations.The proof begins by calculating the Frobenius norm of the matrix defined in (4.60).
  • Non-periodic boundary conditions: The non-periodic proof reduces a full-rank system for x to a partial system involving only coordinates b_0 through b_{n−2}.The coordinates x_2 through x_n are determined from those components, leading to the displayed partial system.
Loading 2002.07868v2…