Evaluating Quantum Algorithms for Linear Solver Workflows

EasyChair Preprint 9887

Abstract

We normally think of implicit Mechanical Computer Aided Engineering (MCAE) as being a resource intensive process, dominated by multifrontal linear solvers that scale super linearly in complexity as the problem size grows. However, as the processor count increases, the reordering that reduces the storage and operation count for the sparse linear solver is emerging as the biggest computational bottleneck. Reordering is NP-complete, and the nested dissection heuristic is generally preferred for MCAE problems. Nested dissection in turn rests on graph partitioning, another NP-complete problem. There are quantum computing algorithms which provide new heuristics for NP-complete problems, and the rapid growth of today's NISQ era quantum computers leads us to consider them as possible accelerators for reordering. This paper reports on the evaluation of the relative merits of several short depth quantum algorithms used for graph partitioning, integration with the LS-DYNA MCAE application, and initial results generated on IBM quantum computers.

Keyphrases: Computer Aided Engineering, graph partitioning, quantum computing

@booklet{EasyChair:9887,
  author    = {Sophia Kolak and Hamed Mohamedbagherpoor and Konstantis Daloukas and Kostas Kafousas and Francois-Henry Rouet and Yorgos Koutsoyannopoulos and Nathan Earnest-Noble and Robert Lucas},
  title     = {Evaluating Quantum Algorithms for Linear Solver Workflows},
  howpublished = {EasyChair Preprint 9887},
  year      = {EasyChair, 2023}}