Randomness vs Quantumness

ACO Student Seminar
Friday, November 9, 2018 - 1:05pm for 30 minutes
Skiles 005
Lance Fortnow – School of Computer Science, Georgia Tech – fortnow@cc.gatech.eduhttps://lance.fortnow.com/
He Guo
Often the popular press talks about the power of quantum computing coming from its ability to perform several computations simultaneously. We’ve already had a similar capability from probabilistic machines. This talk will explore the relationship between quantum and randomized computation, how they are similar and how they differ, and why quantum can work exponentially faster on some but far from all computational problems. We’ll talk about some open problems in quantum complexity that can help shed light on the similarities and differences between randomness and “quantumness”. This talk will not assume any previous knowledge of quantum information or quantum computing.