Conveners
ADVANCE TUTORIAL: Quantum algorithms – what’s quantum complexity theory got to do with it?
- Alessandra Di Pierro (University of Verona)
- Sevag Gharibian
Description
This tutorial gives a gentle introduction to the crucial interplay between quantum algorithms and quantum complexity theory, with an eye on developments in the Quantum Machine Learning sphere. We begin with basic complexity classes such as BQP, followed by the HHL algorithm for its complete problem, Matrix Inversion. We then discuss how the Quantum Singular Value Transform (QSVT) significantly generalizes HHL to general quantum algorithms for Linear Algebra. Finally, as time permits, we discuss the other side of the coin – what does it mean to “dequantize” algorithms like the QSVT, and when is it possible?
