01 QRE talk – Quantum algorithms: A survey of applications and end-to-end complexities

Title: Quantum algorithms: A survey of applications and end-to-end complexities Abstract: 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. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. 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. Bios: Sam McArdle is a Research Scientist at the AWS Center for Quantum Computing. His primary research interest is in quantum algorithms, with a particular focus on algorithms for quantum chemistry and simulation. Prior to joining Amazon, Sam received his PhD in Quantum Computing from the University of Oxford, UK. Alex Dalzell is a Research Scientist at the AWS Center for Quantum Computing. Alex joined the team in 2021 after completing his PhD in Physics at Caltech, where he studied the complexity theory of quantum advantage experiments using noisy devices. His current research interests lie primarily in quantum algorithms and applications, especially in the area of mathematical optimization, but also quantum computation and quantum information more broadly.