Computational Complexity of Quantum Systems

Sandy Irani, University of California at Irvine Quantum Information and Computing
March 18, 2019 3:30 pm ESB 4133

One of the goals of quantum information theory is to understand quantum systems from the standpoint of computational complexity. How difficult is it to compute fundamental properties of a quantum system or simulate a particular system over time? Physicists have been using computers for decades to understand various aspects of quantum systems, but these methods are typically heuristic and achieve success on only limited classes of systems. This talk will give an overview of recent developments in the effort to understand these problems from a formal complexity-theoretic point of view. In particular, one of the most basic properties of a system is its lowest energy state or ground state. I will survey results on the complexity of ground states and the computational resources required to compute them. I will also discuss heuristics to find ground states on more near-term quantum computers.

Bio. Sandy Irani completed her PhD in Computer Science at University of California, Berkeley in 1991 and the following year was a recipient of the University of California President’s Postdoctoral Fellowship. In the Fall of 1992, she joined the faculty of University of California at Irvine where she is currently a full professor. She served as chair of the Computer Science Department from 2005 to 2008 and from 2010 to 2012. In the first part of her career, her research focused on the application of algorithm design and analysis to computing systems. In particular, she has specialized in the area of on-line algorithms and their applications to scheduling and resource allocation. More recently, she has been working in Quantum Computation and Quantum Information Science. She is also the author of a web-based, interactive textbook replacement on Discrete Mathematics in collaboration with zyBooks, Inc. which has been used by more than 40,000 students.


Join us for refreshments before the talk, 3:30-4p. The talk is 4-5p. Both are in the PIMS Lounge, ESB 4133.

The IAM Lecture Series on Quantum Computing is generously sponsored by 1QBit, DWave, and PIMS.

Download lecture slides from Professor Irani’s talk.