Reversible Walk on Spheres: A Quantum Algorithm for Elliptic PDEs with Complex Boundary Conditions

Elliptic PDE solvers are widely used for computational tasks in plasma physics and related fields, both in modelling physical processes via electro- and magnetostatics, and as part of more complicated calculations -- for example, the computation of Taylor-relaxed states, solutions to the Grad-Shafranov equation, electrostatic particle-in-cell methods, and coil shape optimization for stellarators. Quantum algorithms can prepare a quantum state representing the solution to elliptic PDEs exponentially faster than the corresponding classical algorithms. However, existing quantum algorithms are limited to simple boundary conditions that may not be expressive enough to model practical problems. In this work, we introduce a quantum algorithm based on a classical Monte Carlo method known as the Walk on Spheres. Our algorithm solves a family of linear elliptic PDEs with arbitrary Dirichlet boundary conditions, while matching the asymptotic performance of the best existing quantum algorithms based on quantum linear system solvers.