



01537nas a2200157   4500008004100000245004800041210004800089260001400137520103000151100002101181700002001202700002801222700001701250700002801267856008401295       2022                        eng d00aLinear growth of quantum circuit complexity0 aLinear growth of quantum circuit complexity  c3/28/20223 a<p>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&mdash;this is the operation&rsquo;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.</p>1 aHaferkamp, Jonas1 aFaist, Philippe1 aKothakonda, Naga, B. T.1 aEisert, Jens1 aHalpern, Nicole, Yunger  uhttps://www.quics.umd.edu/publications/linear-growth-quantum-circuit-complexity