Quantum computers are fascinating devices that use quantum-mechanical phenomena to perform computation. A traditional computer is governed by classical physics and operates on bits, which encode either a zero or a one. A quantum computer, on the other hand, can operate on superpositions of ones and zeros. This sounds very exciting. But exactly how powerful can quantum computers be over their classical counterparts? And can we classify all the problems for which quantum computers have definite advantages? In this talk I will discuss these questions. In particular we will look at symmetries and graph properties. We will see that for graph properties whether or not we get large quantum speedups depends on what model the graph is represented in. I will also discuss the power of quantum proofs. No prior knowledge of quantum mechanics is required.
Supartha Podder is currently doing his 2nd postdoc at the University of Ottawa, Canada. Previously, he was a postdoc at the University of Texas at Austin, TX. Supartha received his PhD from the Centre for Quantum Technologies, National University of Singapore in Singapore. Before coming to CQT he obtained his MPRI (Parisian Master of Research in Computer Science) from École Normale Supérieure de Cachan (ENS de Cachan) in Paris, France.
Faculty Host: Dakshita Khurana