Comparing classical and quantum complexity

Richard Jozsa
University of Cambridge
09.23.2016 11:00 to 12:00
CSI 2117
Video File: 
PDF icon MarylandSept16.pdf19.53 MB

Issues of complexity are at the root of almost all theoretical aspects of quantum information science and correspondingly, concepts from theoretical computer science have provided a strikingly novel perspective on the foundations of quantum physics itself. For the theory of algorithms and computing, the formalism of 'classical simulation of quantum circuits' provides a mathematically precise tool for studying the rich relations between classical and quantum complexity. We will give an overview of this subject, indicating some elegant mathematical ingredients and implications for physics. Along the way we will mention some striking results for quantum Clifford circuits and matchgate circuits.