Scaling and performance analysis of variational quantum algorithms for quantum simulation

In the past decades, several algorithms for fault-tolerant quantum computers such as Berry’s algorithm for systems of ordinary differential equations [1], HHL for solving linear systems of equations [2] and Shor’s algorithm for factorization [3] have been proven to provide an advantage over classical methods. Their mathematical structure makes it possible to bound precision and asymptotic runtime scaling in terms of several key quantities such as problem size, allowed error and simulated time. On the other hand, variational quantum algorithms (VQA) [4] are one of the most promising classes of algorithms with the capability of bridging the gap between current NISQ- and future fault-tolerant (FT) quantum computers. However, because of their heuristic nature, VQA are considerably less amenable to performance evaluations and investigations of their asymptotic runtime scaling. In this talk we introduce an approximate numerical scaling analysis strategy for VQA for quantum simulation and show the results of applying it to a selection of cases.

 

[1] D. Berry, et al., Commun. Math. Phys.356, 1057–1081 (2017).

[2] A. Harrow, et al., Phys. Rev. Lett. 103, 150502 (2009). 

[3] P. Shor, Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124-134.

 [4] M. Cerezo, et al. Nat Rev Phys 3, 625–644 (2021).