Linear growth of quantum circuit complexity

Haferkamp J, Faist P, Kothakonda NBT, Eisert J, Halpern NY (2022)

Publication Type: Journal article

Publication year: 2022

Journal

Nature Physics Nature Research

Book Volume: 18

Pages Range: 528-532

Journal Issue: 5

DOI: 10.1038/s41567-022-01539-6

Abstract

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.

Involved external institutions

Freie Universität Berlin DE Germany (DE) Harvard University US United States (USA) (US)

How to cite

APA:

Haferkamp, J., Faist, P., Kothakonda, N.B.T., Eisert, J., & Halpern, N.Y. (2022). Linear growth of quantum circuit complexity. Nature Physics, 18(5), 528-532. https://doi.org/10.1038/s41567-022-01539-6

MLA:

Haferkamp, Jonas, et al. "Linear growth of quantum circuit complexity." Nature Physics 18.5 (2022): 528-532.

BibTeX: Download