Linear growth of quantum circuit complexity

By Jonas Haferkamp, Philippe Faist, N. B. T. Kothakonda, Jens Eisert, Nicole Yunger Halpern. Nature Physics, 2021

183 citations recorded by the source corpus.

The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haar-random two-qubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates—this is the operation’s exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits. The dynamics of quantum states underlies the emergence of thermodynamics and even recent theories of quantum gravity. Now it has been proven that the quantum complexity of states evolving under random operations grows linearly in time.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/18c68f84bb9e2bc7f9d9d5da5a3dfee6f369e404

Citations in the corpus