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.

Table of Contents:
Part I. Areas of Application: 1. Condensed matter physics; 2. Quantum chemistry; 3. Nuclear and particle physics; 4. Combinatorial optimization; 5. Continuous optimization; 6. Cryptanalysis; 7. Solving differential equations; 8. Finance; 9. Machine learning with classical data; Part II. Quantum Algorithmic Primitives: 10. Quantum linear algebra; 11. Hamiltonian simulation; 12. Quantum Fourier transform; 13. Quantum phase estimation; 14. Amplitude amplification and estimation; 15. Gibbs sampling; 16. Quantum adiabatic algorithm; 17. Loading classical data; 18. Quantum linear system solvers; 19. Quantum gradient estimation; 20. Variational quantum algorithms; 21. Quantum tomography; 22. Quantum interior point methods; 23. Multiplicative weights update method; 24. Approximate tensor network contraction; Part III. Fault-Tolerant Quantum Computing: 25. Basics of fault tolerance; 26. Quantum error correction with the surface code; 27. Logical gates with the surface code; Appendix; References; Index.

About the Author :
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. András Gilyén is a Research Fellow in the Department of Probability and Statistics at the HUN-REN Alfréd Rényi Institute of Mathematics, Budapest. He coined the term 'block-encoding' in quantum linear algebra and was one of the co-inventors of Quantum Singular Value Transformation, which unified most major quantum algorithms in a single paradigm and earned him the ERCIM Cor Baayen Early Career Researcher Award in 2019. Connor T. Hann is a Senior Research Scientist at the Amazon Web Services Center for Quantum Computing. His research interests span the quantum computing stack, ranging from device physics to algorithms and applications. He received a Ph.D. in physics from Yale University and a BS in physics from Duke University. Michael J. Kastoryano is an Associate Professor of Quantum Computing at the University of Copenhagen and an Amazon Visiting Academic at the Amazon Web Services Center for Quantum Computing. He received his Ph.D. in quantum information theory from the Niels Bohr Institute in Copenhagen in 2012. Emil T. Khabiboulline is a National Resource Council Postdoctoral Associate at the Joint Center for Quantum Information and Computer Sciences (QuICS) at the University of Maryland, College Park. He works on protocols for quantum communication/cryptography and quantum simulation, with realizations on quantum optics platforms. The research has led to a patent. He completed his Ph.D. at Harvard, where he taught physics and computer science. He received his bachelor's degree at Caltech. Aleksander Kubica is an Assistant Professor in the Department of Applied Physics at Yale University. He received his Ph.D. in theoretical physics from Caltech. Prior to joining Yale University, he was a postdoctoral fellow at the Perimeter Institute for Theoretical Physics and a research scientist at the AWS Center for Quantum Computing. He works in the intersection of quantum information science and quantum many-body physics. Grant Salton is a Senior Research Scientist at Amazon Web Services. He received his Ph.D. in theoretical physics from Stanford University. Prior to joining AWS, Grant was a postdoctoral fellow at the IQIM, Caltech. His research interests range from quantum error correction and algorithms to applications of quantum devices. He also holds master's degrees from both Stanford and McGill Universities. Samson Wang is a Postdoctoral Scholar at the Institute for Quantum Information and Matter at Caltech. He has studied at the University of Oxford and Imperial College London. He researches theoretical aspects of quantum information and computation.

Review :
'This timely and forward-looking survey captures the state-of-the-art in quantum computing. Focusing on cutting-edge applications and recent advances in quantum primitives, it serves as an essential resource for understanding the rapidly evolving role of quantum algorithms in scientific discovery.' Lin Lin, University of California, Berkeley