Thu. March 7, 3:00 p.m. – 3:36 p.m. CST
Auditorium 1
I'll reflect on our knowledge of quantum computing speedups, nearly 30 years after the discovery of Shor's factoring algorithm. Some people expected Shor's algorithm to be followed by a profusion of other quantum algorithms achieving exponential speedups, for example for NP-complete problems, and were disappointed when that didn't happen. Was there a deep reason for this? Discounting hype, and insisting on a fair comparison against the best known classical algorithms, what can we say in 2023 about the structure of problems most amenable to large quantum speedup?
Presented By
- Scott Aaronson (University of Texas at Austin)
Quantum Algorithms 30 Years After Shor
Thu. March 7, 3:00 p.m. – 3:36 p.m. CST
Auditorium 1
I'll reflect on our knowledge of quantum computing speedups, nearly 30 years after the discovery of Shor's factoring algorithm. Some people expected Shor's algorithm to be followed by a profusion of other quantum algorithms achieving exponential speedups, for example for NP-complete problems, and were disappointed when that didn't happen. Was there a deep reason for this? Discounting hype, and insisting on a fair comparison against the best known classical algorithms, what can we say in 2023 about the structure of problems most amenable to large quantum speedup?
Presented By
- Scott Aaronson (University of Texas at Austin)