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.
Computational Complexity of Quantum Systems - From Theory to Ground State Analysis
Overview
Syllabus
Introduction
Problem Statement
Local Hamiltonian
Local Hamiltonian Complexity
Hamiltonian
Translationally invariance
Finite system
Decision vs function
Complexity class
Binary search
Infinite grid
Open problem
Taught by
Illinois Quantum
Related Courses
-
The Complexity of the Local Hamiltonian Problem
-
Guidable Local Hamiltonian Problems with Implications to Heuristic Ansatz State Preparation and Quantum PCP
-
Entanglement Subvolume Law for 2D Frustration-Free Spin Systems
-
Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis
-
A Complexity Theory for the Quantum Age?
-
Local Minima in Quantum Systems
