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 conjectured that the quantum complexity of the state output by a random circuit on n qubits grows linearly as more and more random gates are applied, until saturating after a number of gates exponential in n. We prove this conjecture by studying the dimension of the set of all unitaries that can be accessed with a given arrangement of two-qubit gates. Our core technical contribution is a lower bound on this dimension, using techniques from algebraic geometry and considerations based on Clifford circuits. In the 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, establishing a resource theory to capture a notion of quantum complexity and drawing a connection between the concepts of complexity and entropy.
Joint work with: Jonas Haferkamp, Teja Naga Bhavia Kothakonda, Anthony Munson, Jens Eisert, Nicole Yunger Halpern
Zoom Link: https://pitp.zoom.us/j/94288479163?pwd=Nm8wOUdReGhreDErdUpJTzFETlBUUT09
- Quantum Information
- Scientific Series