Leveraging Preconditioning to Speed Up Quantum Simulation-Based Optimization

Leveraging Preconditioning to Speed Up Quantum Simulation-Based Optimization

Abstract:

Simulation-based optimization is computationally intensive requiring many evaluations of complex simulations to optimize an objective function. Quantum algorithms can provide a better runtime over classical methods by simultaneously evaluating multiple possible solutions. If the objective function and/or constraints depend on the summary statistic information derived from the result of a simulation, the problem is classified as a Quantum Simulation-Based Optimization (QuSO) problem. A subclass of QuSO is LinQuSO, where the simulation component can be formulated as a system of linear equations. The calculation of the objective function depends on the complexity of solving the corresponding linear system of equations, which is linear influenced by the condition number of the system. A recent paper introduced a quantum algorithm for solving prototypical second-order linear elliptic partial differential equations, which are discretized by 𝑑-linear finite elements on Cartesian grids within a bounded 𝑑-dimensional domain. By using a BPX preconditioner the system of linear equations is transformed into a well-conditioned one. Functionals of the solution can be computed for a given tolerance 𝜀 with a complexity of 𝒪(︀polylog (︀𝜀−1)︀)︀ and a quantum advantage over classical solvers is accomplished for 𝑑 > 1. This work shows how to improve the efficiency of computing optimal input parameters for a LinQuSO problem by inserting the preconditioning algorithm into the Quantum Approximate Optimization Algorithm (QAOA), which results in a runtime of 𝒪(︀𝜀−1 polylog (︀𝜀−1)︀)︀ for the simulation component. The new approach is demonstrated with an example of a topology optimization problem for heat conduction.

Author:

Carlotta von L’Estocq

Advisors:

Jonas Stein, David Bucher, Claudia Linnhoff-Popien

Student Thesis | Published January 2025 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors