Efficient Quantum Jacobi Algorithm for Solving the Poisson Equation

This abstract has open access
Problem description and relevance

The simulation of fluid flow using Computational Fluid Dynamics (CFD) is a central tool in many areas of science and engineering, including aerodynamics, energy systems, and climate modeling. For numerical simulations, the underlying partial differential equations, such as the Navier–Stokes equations, are discretized, leading to large and sparse linear systems of equations. Solving these systems efficiently plays an important role in the overall computational cost of CFD simulations.

Quantum algorithms are promising for advancing fluid simulations by leveraging an exponentially growing state space in the number of qubits [1]. In particular, Quantum Linear System Solvers (QLSS), such as the HHL algorithm, promise significant speedups under certain assumptions [2]. These approaches rely on matrix inversion. However, in classical CFD simulations, iterative schemes, ranging from classical methods such as the Jacobi method, Gauss–Seidel iteration, and Successive Over-Relaxation (SOR) to more advanced Krylov subspace methods such as the Conjugate Gradient method, are typically employed instead [3].

Recent work has therefore explored the implementation of iterative solvers within a quantum computing framework [4]. There, the implementation of the Jacobi scheme via block encoding results in a qubit cost that scales linearly with the number of Jacobi iterations.

In this work, we present an alternative implementation of the Jacobi method based on Quantum Singular Value Transformation (QSVT) [5]. Using this polynomial-based approach, the number of required qubits becomes independent of the number of Jacobi iterations. This enables an efficient quantum implementation of the Jacobi scheme in terms of circuit width and depth.

Submission ID :
39
Methodology :

In order to achieve an efficient quantum implementation of the Jacobi method, we combine the scheme with Quantum Singular Value Transformation (QSVT). For the linear system Ax=b, the classical Jacobi method starts by splitting the matrix A into its diagonal part D and the off-diagonal part R. The approximation to the solution of the linear system is then obtained from the iterative scheme xk = D−1 (b − Rxk−1). 

We express the k-th approximation of the Jacobi algorithm in terms of a sum of matrix exponentials. This representation allows us to employ QSVT, which provides a systematic framework for implementing polynomial transformations of block-encoded matrices. The corresponding quantum circuit consists of three controlled QSVT subcircuits, which are combined via a Linear Combination of Unitaries (LCU). In total, the circuit requires three ancilla qubits in addition to those needed for the block encoding of the underlying matrix. 

The final state is obtained by postselection on the ancilla qubits, yielding a quantum state proportional to the approximate solution after a certain number of Jacobi iterations.

Practical demonstration :

For testing our quantum Jacobi algorithm, we consider the widely used benchmark of a lid-driven cavity. We employ Chorin's projection method [6], which gives rise to pressure Poisson equations that need to be solved at each pseudo time step. These equations define the linear systems that we use to test our approach.

The numerical test are performed on a noiseless quantum simulator. For Quantum Singular Value Transformation, one needs to find suitable phase angles in order to approximate the desired polynomial. It has been shown that these angles can be computed such that the resulting polynomial approximation reaches machine precision [7]. Our numerical results confirm that the use of QSVT does not introduce any additional error in practice.

In particular, our quantum Jacobi algorithm reproduces the classical solution with high precision, where the observed deviation remains within numerical precision. This demonstrates that the QSVT-based implementation accurately captures the classical Jacobi scheme for the considered pressure Poisson problem.

Application potential :

The proposed quantum Jacobi method allows for solving linear systems on a quantum computer with a number of qubits that scales logarithmically with the system size, while remaining independent of the number of Jacobi iterations k. The circuit depth scales linearly with k, reflecting the iterative structure of the Jacobi scheme. This qubit scaling suggests that the approach may become advantageous for large-scale problems where classical methods are limited by memory constraints.

The algorithm requires the efficient block encoding of the underlying matrix. This can be achieved for certain matrices [8], but remains challenging in general. The overall performance therefore depends on the availability of efficient, problem-specific encoding strategies.

In contrast to those quantum linear system solvers based on matrix inversion, the proposed approach directly implements an iterative scheme, providing an alternative that is more closely aligned with classical solver strategies. The presented approach therefore appears suitable for integration into larger CFD workflows, where it may serve as a building block within more advanced solution frameworks. In particular, combinations with multigrid methods or its use as a preconditioning routine are possible directions for extending the method towards practical applications.

Louisa Marie Piskol
PhD student
,
Volkswagen AG, TU Braunschweig
Thorsten Grahs
Senior researcher
,
Volkswagen AG
Stefan Langer
Scientific employee, Head of Project
,
German Aerospace Center
Prof. Oleksandr Kyriienko
University of Sheffield
18 visits