Quantum Information and Computing Meeting: Quantum complexity in random circuits

Philippe Faist
Quantifying quantum states' complexity is a key problem in various subfields of science, from quantum computing to black-hole physics.

Phillipe Faist
Group meeting (hybrid format: online/seminar room B2.46)
Tue, 30. November 2021, 11:00 am (MEZ)

Abstract:

Quantifying quantum states' complexity is a key problem in various subfields of science, from quantum computing to black-hole physics. Motivated by the expected behavior of wormholes in quantum gravity, Brown and Susskind came up with a conjecture: The quantum complexity of the state output by a random circuit grows linearly as more and more random gates are applied, until saturating after an exponential number of gates. We prove this conjecture by studying the dimension of the set of all unitaries that can be accessed with a given arrangement of gates, if the gates are chosen randomly from the Haar measure on the 2-qubit unitaries. Our core technical contribution is a lower bound on this dimension, using techniques from algebraic geometry and with considerations based on Clifford circuits. In a second part of my talk, I'll discuss some thermodynamic and effective information-theoretic aspects of the complexity of quantum states and its growth in quantum many-body systems, and draw a connection between the concepts of complexity and entropy.

Joint work with: Jonas Haferkamp, Naga B. T. Kothakonda, Jens Eisert, Nicole Yunger Halpern; arXiv:2106.05305, arXiv:2110.11371