Power of Quantum Computation, Symmetries and Graph Properties

Abstract

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 power of quantum proofs. No prior knowledge of quantum mechanics is required.

Bio:

I am currently doing my 2nd postdoc with Anne Broadbent at the University of Ottawa in Ottawa, Canada. Previously, I was a postdoc with Scott Aaronson at UT Austin in Austin, TX. I received my PhD from the Centre for Quantum Technologies, National University of Singapore in Singapore, under the supervision of Hartmut Klauck. Before coming to CQT I obtained my MPRI (Parisian Master of Research in Computer Science) from École Normale Supérieure de Cachan (ENS de Cachan) in Paris, France.

I work in theoretical computer science. My main interest lies in quantum and classical complexity theory (specifically, query complexity, communication complexity) and space bounded computational models. I am very interested in understanding the limits of quantum resources. I am also interested in quantum cryptography, in particular in the interplay between complexity theory and cryptography.

Please join meeting in Sococo VH 102, or Zoom.

Join Zoom Meeting: https://tufts.zoom.us/j/98610939077

PASSWORD: See colloquia email

Dial by your location: +1 646 558 8656 US (New York)

Meeting ID: 986 1093 9077

Passcode: See colloquia email