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

The 1994 discovery of Shor's quantum algorithm for integer factorization―an important practical problem in the area of cryptography―demonstrated quantum computing's potential for real-world impact. Since then, researchers have worked intensively to expand the list of practical problems that quantum algorithms can solve effectively. This book surveys the fruits of this effort, covering proposed quantum algorithms for concrete problems in many application areas, including quantum chemistry, optimization, finance, and machine learning. For each quantum algorithm considered, the book clearly states the problem being solved and the full computational complexity of the procedure, making sure to account for the contribution from all the underlying primitive ingredients. Separately, the book provides a detailed, independent summary of the most common algorithmic primitives. It has a modular, encyclopedic format to facilitate navigation of the material and to provide a quick reference for designers of quantum algorithms and quantum computing researchers.

Alexander M. Dalzell is a Research Scientist at the Amazon Web Services Center for Quantum Computing where he works on quantum algorithms. Following undergraduate studies at MIT, he received a Ph.D. in physics from Caltech, where he was awarded an NSF Graduate Research Fellowship. He currently serves as an editor for the journal 'Quantum.'

Sam McArdle is a Research Scientist at the Amazon Web Services Center for Quantum Computing where he works on quantum computing with a focus on quantum algorithms and applications. Prior to joining AWS, he completed his Ph.D. in Quantum Computing at the University of Oxford, UK. Sam also holds an MPhys in Theoretical Physics from Durham University, UK.

Mario Berta is a professor of physics at the Institute for Quantum Information at RWTH Aachen University and a Visiting Reader in the Department of Computing at Imperial College London. He received his Ph.D. in theoretical physics from ETH Zürich in 2013.

Przemysław Bienias is a Research Scientist at the Amazon Web Services Center for Quantum Computing. As a Marie Skłodowska-Curie fellow, he obtained a Ph.D. from the University of Stuttgart. He was a UMD faculty member and a researcher at JQI, QuICS, and Harvard. He researches quantum error correction, quantum algorithms, and hardware optimization for neutral-atom and superconducting-qubit platforms. He applies machine learning to quantum computing and quantum many-body systems.

Chi-Fang Chen is a postdoctoral scholar in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. He works on quantum Gibbs sampling algorithms and random matrix theory. He received a bachelor's degree in physics from Stanford and a Ph.D. in physics from Caltech.