Title:Accelerating large-scale linear algebra using variational quantum imaginary time evolution

Abstract:Graph partitioning techniques enhance the efficiency of solving large-scale linear systems in the context of Finite Element Analysis (FEA). Even for systems of linear equations that are highly sparse, their direct solution via factorization methods, such as LU or Cholesky decomposition, is computationally expensive due to the introduction of non-zero elements, or ``fill-in.'' We introduce a quantum approach to the graph partitioning problem based on the variational quantum imaginary time evolution algorithm (VarQITE), allowing to solve the combinatorial optimization problem of reordering of sparse matrices to minimize the fill-in. We develop a hybrid quantum/classical pipeline to accelerate Finite Element solvers by integrating the VarQITE algorithm into the production workflow of Ansys' industrial software LS-DYNA. This allows to study multiple different types of FEA problems, ranging from mechanical engineering to computational fluid dynamics.
We prove out that VarQITE positively impacts LS-DYNA workflows by measuring the wall-clock time to solution of FEA problems when compared against the classical heuristic graph partitioning solver in LS-DYNA. The selected instances cover a range of FEA problems, including simulation of blood pumps, roof crushing of cars, and vibration analysis of cars. We report performance results for our hybrid quantum-accelerated workflow on FEA meshes of up to 5.9M vertices and 55 million edges. We find that the wall clock time of the heuristics solutions used in the industry-grade solver is improved by up to 12\%. We also execute the VarQITE algorithm on quantum hardware (IonQ Aria and IonQ Forte) and find that the results are comparable to noiseless and noisy simulations. Finally, we introduce a hybrid technique for post-processing the found solutions with classical refinement heuristics such as Fiduccia-Mattheyses.