Haferkamp, Jonas 
ORCID: 0000-0002-3592-7274, Faist, Philippe ORCID: 0000-0003-1696-6400, Kothakonda, Naga B. T., Eisert, Jens ORCID: 0000-0003-3033-1292 and Halpern, Nicole Yunger
(2022).
Linear growth of quantum circuit complexity.
Nat. Phys., 18 (5).
S. 528 - 535.
BERLIN:
NATURE PORTFOLIO.
ISSN 1745-2481
Abstract
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. 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.
| Item Type: | Journal Article | ||||||||||||||||||||||||
| Creators: |
|
||||||||||||||||||||||||
| URN: | urn:nbn:de:hbz:38-689855 | ||||||||||||||||||||||||
| DOI: | 10.1038/s41567-022-01539-6 | ||||||||||||||||||||||||
| Journal or Publication Title: | Nat. Phys. | ||||||||||||||||||||||||
| Volume: | 18 | ||||||||||||||||||||||||
| Number: | 5 | ||||||||||||||||||||||||
| Page Range: | S. 528 - 535 | ||||||||||||||||||||||||
| Date: | 2022 | ||||||||||||||||||||||||
| Publisher: | NATURE PORTFOLIO | ||||||||||||||||||||||||
| Place of Publication: | BERLIN | ||||||||||||||||||||||||
| ISSN: | 1745-2481 | ||||||||||||||||||||||||
| Language: | English | ||||||||||||||||||||||||
| Faculty: | Unspecified | ||||||||||||||||||||||||
| Divisions: | Unspecified | ||||||||||||||||||||||||
| Subjects: | no entry | ||||||||||||||||||||||||
| Uncontrolled Keywords: |
|
||||||||||||||||||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/68985 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
 |
View Item |