Discussion Session: Complexity

Computational complexity is a notion from information theory, initially defined for finite-dimensional systems, measuring the number of gates that have to be applied to a given reference state to reach a target state. Susskind’s proposals for defining computational complexity also for characterising quantum properties black holes have triggered significant interest in defining computational complexity also for quantum field theories, i.e. for infinite-dimensional Hilbert spaces. The idea is to establish a precise holographic dictionary for complexity. There are successful proposals for complexity definitions in free quantum field theory. Recently, there have been several proposals also for interacting theories, mostly in the context of conformal field theories, building gate sets from symmetry generators. Questions to be discussed include, in addition to further questions about the talks on the subject presented at the workshop: - What is the status of defining complexity for interacting field theories? - How do different proposals for gate sets, reference states and cost functions compare to each other? - What is the status of establishing a holographic dictionary? - What are promising avenues to be pursued for further progress?