Quantum Algorithms: A Survey of Applications and End-to-End Complexities

The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities.  

In this talk, we present examples and comment on takeaways identified in our larger survey of quantum algorithms and applications (arXiv:2310.03011). We discuss several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties to understand the “end-to-end” resource requirements of the application, and how it compares against state-of-the-art classical methods.

This is based on joint work with Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, Fernando G. S. L. Brandão – carried out at the AWS Center for Quantum Computing.