Computational Complexity of Quantum Systems - From Theory to Ground State Analysis

Explore quantum systems' computational complexity in this 55-minute lecture delivered by UC Irvine Professor Sandy Irani at Illinois Quantum. Gain insights into the challenges of computing fundamental properties and simulating quantum systems, moving beyond traditional heuristic methods used by physicists. Delve into recent developments in formal complexity theory, with particular focus on understanding ground states in both finite and infinite systems. Learn about the computational resources required for ground state calculations and discover heuristic approaches for finding ground states on near-term quantum computers. The lecture covers key topics including local Hamiltonian complexity, translational invariance, decision versus function problems, complexity classes, and binary search, concluding with discussions on infinite grids and open problems in the field. Drawing from her extensive background in computer science and quantum computation, Professor Irani, an ACM Fellow and distinguished faculty member, presents a comprehensive overview of this crucial intersection between quantum information theory and computational complexity.