Source-linked AI summary
Quantum algorithm and circuit design solving the Poisson equation
Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph Traub, Sabre Kais
TL;DR
The paper addresses the challenge of solving the Poisson equation in high dimensions, where classical numerical costs grow exponentially with dimension. It develops a quantum algorithm and scalable circuit based on discretization, quantum linear-system solving, and structured Hamiltonian simulation. The resulting circuit has almost-linear dependence on d and polylogarithmic dependence on ε−1, while producing a quantum-state encoding of the solution.
Problem
Classical algorithms for solving the Poisson equation with error ε have costs growing as ε−αd, yielding exponential dependence on dimension d.
Method
The paper discretizes the Poisson equation, applies a quantum linear-system algorithm, and exploits Poisson-matrix structure for Hamiltonian simulation and circuit construction.
Results
The circuit uses almost linearly many quantum operations in d and polylogarithmically many in ε−1, with explicit qubit and operation bounds.
Takeaways & Limitations
The algorithm breaks the curse of dimensionality in d, and its circuit modules can be reused in other quantum algorithms and structured problems.
Takeaways & Limitations
The method assumes a quantum state encoding a superposition of right-hand-side function evaluations and does not account for preparing that state.
Abstract
from arXiv · showhide
The Poisson equation occurs in many areas of science and engineering. Here we focus on its numerical solution for an equation in d dimensions. In particular we present a quantum algorithm and a scalable quantum circuit design which approximates the solution of the Poisson equation on a grid with error \varepsilon. We assume we are given a supersposition of function evaluations of the right hand side of the Poisson equation. The algorithm produces a quantum state encoding the solution. The number of quantum operations and the number of qubits used by the circuit is almost linear in d and polylog in \varepsilon^{-1}. We present quantum circuit modules together with performance guarantees which can be also used for other problems.
1. Introduction
The paper develops a quantum algorithm and scalable circuit for solving the Poisson equation, motivated by its broad scientific and engineering importance and the classical curse of dimensionality. The approach combines linear-system solving with Hamiltonian simulation and reusable quantum circuit modules.
- The Poisson equation is fundamental in computational fluid dynamics, solvation, electrostatics, Markov chains, and electronic-structure calculations.
- Classical algorithms for error ε face costs growing as ε−αd, producing exponential dependence on dimension d.
- The quantum algorithm uses almost linearly many quantum operations in d and polylogarithmically many in ε−1.
- The algorithm outputs a quantum state encoding the grid solution rather than a bit string, making it suited to computing functions of that solution.
- The input assumption is access to a quantum state containing a superposition of right-hand-side function evaluations, whose preparation cost is not analyzed.
- The method discretizes the equation on a regular Cartesian grid, solves the resulting linear system, and explicitly simulates the Poisson matrix Hamiltonian.
- The implementation supplies accuracy and cost guarantees plus modules for trigonometric functions, eigenvalue reciprocals, and controlled inverse-trigonometric rotations.
2. Overview
The overview discretizes the d-dimensional Poisson equation into a structured linear system and contrasts its classical dimensional dependence with a scalable quantum circuit. The circuit uses polylogarithmic accuracy dependence, while success probability is amplified through repetition.
- The problem is posed with Dirichlet boundary conditions for a d-dimensional Poisson equation and a sufficiently smooth right-hand side.
- Finite-difference discretization on a Cartesian grid produces a symmetric positive-definite linear system from sampled function values.
- For error O(ε), the discretized matrix has dimension proportional to ε−αd × ε−αd, with α determined by solution smoothness.
- Classical solution costs include ε−αd−α log ε−1, and any direct or iterative method requires at least ε−αd operations because it must determine all unknowns.
- The quantum circuit uses max{d, log2 ε−1}(log2 d + log2 ε−1)^2 qubits and max{d, log2 ε−1}(log2 d + log2 ε−1)^3 quantum operations.
- The construction exploits Kronecker-product structure and tensor-product Hamiltonian evolution, with efficient diagonalization and eigenvalue approximation supporting simulation.
3. Discretization
The paper discretizes the Poisson equation on regular grids, reducing it to structured linear systems whose matrices extend naturally from one to d dimensions.
- 3.1. One dimension: The one-dimensional problem uses mesh size h = 1/M and approximates the solution at M+1 grid points xi = ih.The grid values are ui = u(xi) and fi = f(xi), while v denotes the approximate solution.
- 3.1. One dimension: Finite differences replace the second derivative, producing h^-2(−v_i−1 + 2v_i − v_i+1) = f_i for interior points.The truncation error is O(h^2||d^4u/dx^4||∞) when f has a uniformly bounded fourth derivative.
- 3.1. One dimension: With zero boundary values, the discretized one-dimensional system has M − 1 equations and unknowns and uses a tridiagonal matrix L_h.The boundary conditions are v_0 = 0 and v_M = 0.
- 3.2. Two dimensions: In two dimensions, finite differences combine x- and y-direction second-derivative approximations into the discretized Laplacian −∆_h.Interior grid values satisfy a five-point stencil, with boundary values set to zero.
- 3.2. Two dimensions: The two-dimensional system has (M − 1)^2 unknowns, and its matrix A is Hermitian with a block structure independent of M.A is built from L_h, identity blocks, and Kronecker products.
- 3.3. d dimensions: In d dimensions, the discretized Laplacian is −∆_h = h^-2A, where A sums d Kronecker-product terms containing L_h and identity matrices.The matrix A has size (M − 1)^d × (M − 1)^d and is symmetric positive definite after scaling.
4. Quantum circuit
The circuit prepares the right-hand-side state, estimates eigenvalues, computes their reciprocals, applies a controlled rotation, and uncomputes auxiliary registers. The construction yields an O(ε) solution state while controlling eigenvalue, rotation, and implementation errors.
- Circuit steps: The algorithm assumes the right-hand-side vector is prepared as a quantum state |fh⟩ in register B and decomposed in eigenstates of −∆h.The coefficients are βj = ⟨uj|fh⟩.
- Circuit steps: Phase estimation uses e−2πi∆h/E to encode approximations of the eigenvalues in a top register.The top register uses n = O(log(E/ε)) qubits.
- Circuit steps: The INV module computes ε-accurate approximations of reciprocal eigenvalues in a b = 3⌈log ε−1⌉-qubit register using Newton iteration.Each Newton step maps |x̂i⟩|v⟩ to |x̂i+1⟩|v⟩ using addition and multiplication circuits.
- Circuit steps: A controlled rotation, followed by uncomputation and ancilla measurement, produces the normalized linear-system solution when the measurement outcome is 1.Outcome 0 indicates failure and requires repetition; amplitude amplification is mentioned as an alternative but is not treated.
- Multidimensional construction: For d > 1, the eigenvalues of −∆h are sums of one-dimensional eigenvalues, enabling multidimensional circuit construction from the one-dimensional structure.The eigenvalues are bounded by E, with E = 2⌈log2 d⌉4M^2 when M is a power of two.
- Error analysis: Setting ν = ⌈log2(17E/ε)⌉ gives error ε(1+o(1)), while the algorithm uses O(log2(E/ε)) matrix exponentials.The implementation accuracy of the eigenvalues determines the accuracy of the system solution.
- Circuit cost: The reciprocal-computation modules require O(log ε−1) qubits and a low-degree polynomial number of gates.These modules use fixed-precision arithmetic throughout their iterative steps.
5. Hamiltonian simulation of the Poisson matrix
The Poisson matrix is simulated by diagonalizing its one-dimensional structure with sine transforms and approximating its eigenvalues, then extending the construction across dimensions.
- The simulation implements e^{ih−2L_hγ} through the sine-transform spectral decomposition and an approximation of the diagonal eigenvalue matrix.
- The one-dimensional matrix L_h is diagonalized by the sine transform, with eigenvalues 4 sin^2(jπ/(2M)).
- Eigenvalue approximation uses a second-order Taylor approximation of e^{ix/r}, repeated squaring, fixed-point arithmetic, and extraction of the sine component.
- The encoded eigenvalue phase is applied using CNOT-based transformations and phase kickback.
6. Total cost
The total circuit cost combines multidimensional Poisson-matrix simulation with reciprocal-eigenvalue computation and conditional rotation, while the mesh size must track the target accuracy.
- The Poisson matrix simulation requires d·O(n^3) quantum operations and d·O(n^2) qubits, with n = O(log2 d + m + log2 ε−1).
- The complete circuit requires order d·O(n^3) + (log2 ε1−1)^4 quantum operations and d·O(n^2) + (log2 ε1−1)^3 qubits.
- The mesh size M must depend on ε to balance discretization error against unnecessary matrix growth.
- A number of repetitions proportional to ε−4α yields a success probability arbitrarily close to one, independently of d.
- Classical deterministic algorithms have cost exponential in d, with a lower bound proportional to ε−d/r for error ε.
7. Conclusion and future directions
The paper presents a scalable quantum Poisson solver whose dimension dependence breaks the classical curse of dimensionality, while its circuit modules extend beyond this application.
- The quantum algorithm and circuit approximate the d-dimensional Poisson solution and achieve exponential speedup relative to classical algorithms in d.
- Efficient diagonalization exploits the Poisson Hamiltonian structure, and reciprocal-eigenvalue and trigonometric-approximation modules are reusable in other problems.
- Hamiltonian simulation techniques can combine with the solver to extend applicability to PDEs, signal processing, time series analysis, and other areas.
Appendix 1
Appendix 1 defines the Pauli and identity matrices, the Hadamard gate, and the Walsh-Hadamard notation used for circuit components.
- X, Y, and Z denote the Pauli matrices σx, σy, and σz, while I denotes the identity matrix.
- H denotes the Hadamard gate, and W denotes applying H to every qubit in an n-qubit register.
- The appendix supplies matrix representations for the other quantum gates used in the paper.
Appendix 2
Appendix 2 establishes fixed-precision error bounds for Newton iteration and repeated-squaring approximations used to compute sine values and discretized Poisson eigenvalues. The bounds specify precision requirements in terms of iteration depth, mesh size, and accuracy parameters.
- Newton iteration: Newton iteration approximates v^-1 using s steps, starting from ˆx0 = 2^-p when 2^(p-1) < v ≤ 2^p.The implementation assumes b-bit inputs and outputs with fixed-precision internal arithmetic.
- Newton iteration: The Newton error satisfies εN ≥ 2^-2s, requiring s ≥ ⌈log2 log2 εN^-1⌉ iterations for target error εN.Intermediate results are truncated to b bits, so the total error also includes truncation effects.
- Sine approximation: For x ∈ [π/(2M), π/2), the method approximates e^ix through powers of W and obtains sin x from the imaginary part.Repeated squaring keeps the approximations inside the unit disk and bounds error propagation through the squaring map.
- Sine approximation: s = max{2ν + 9, 11 + ν + log2 M} bits and r = 2ν + 7 provide the stated approximation guarantee for sin x.The precision condition depends on the mesh size 1/M and the parameter ν.
- Discrete Poisson operator: The resulting sine approximations yield error bounds for the eigenvalues of h^-2Lh with mesh size h = 1/M.In d dimensions, the eigenvalues of the discretized negative Laplacian are sums of one-dimensional eigenvalues.