Comparing classical and quantum complexity

Talk
Richard Jozsa
University of Cambridge
Time: 
09.23.2016 11:00 to 12:00
Location: 
CSI 2117

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.