Randomness vs Quantumness

ACO Student Seminar
Friday, November 9, 2018 - 1:05pm
30 minutes
Skiles 005
School of Computer Science, Georgia Tech
 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.