01533nas a2200157 4500008004100000245004800041210004800089260001400137520103000151100002101181700002001202700002801222700001701250700002801267856008001295 2022 eng d00aLinear growth of quantum circuit complexity0 aLinear growth of quantum circuit complexity c3/28/20223 a

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.

1 aHaferkamp, Jonas1 aFaist, Philippe1 aKothakonda, Naga, B. T.1 aEisert, Jens1 aHalpern, Nicole, Yunger uhttps://quics.umd.edu/publications/linear-growth-quantum-circuit-complexity01714nas a2200181 4500008004100000245004400041210004400085260001500129490000800144520120900152100002801361700002801389700002101417700002001438700001701458700002001475856003701495 2022 eng d00aResource theory of quantum uncomplexity0 aResource theory of quantum uncomplexity c12/19/20220 v1063 a

Quantum complexity is emerging as a key property of many-body systems, including black holes, topological materials, and early quantum computers. A state's complexity quantifies the number of computational gates required to prepare the state from a simple tensor product. The greater a state's distance from maximal complexity, or "uncomplexity," the more useful the state is as input to a quantum computation. Separately, resource theories -- simple models for agents subject to constraints -- are burgeoning in quantum information theory. We unite the two domains, confirming Brown and Susskind's conjecture that a resource theory of uncomplexity can be defined. The allowed operations, fuzzy operations, are slightly random implementations of two-qubit gates chosen by an agent. We formalize two operational tasks, uncomplexity extraction and expenditure. Their optimal efficiencies depend on an entropy that we engineer to reflect complexity. We also present two monotones, uncomplexity measures that decline monotonically under fuzzy operations, in certain regimes. This work unleashes on many-body complexity the resource-theory toolkit from quantum information theory.

1 aHalpern, Nicole, Yunger1 aKothakonda, Naga, B. T.1 aHaferkamp, Jonas1 aMunson, Anthony1 aEisert, Jens1 aFaist, Philippe uhttps://arxiv.org/abs/2110.1137101694nas a2200169 4500008004100000245004400041210004400085260001500129520120900144100002801353700002801381700002101409700002001430700001701450700002001467856003701487 2021 eng d00aResource theory of quantum uncomplexity0 aResource theory of quantum uncomplexity c10/21/20213 a

Quantum complexity is emerging as a key property of many-body systems, including black holes, topological materials, and early quantum computers. A state's complexity quantifies the number of computational gates required to prepare the state from a simple tensor product. The greater a state's distance from maximal complexity, or ``uncomplexity,'' the more useful the state is as input to a quantum computation. Separately, resource theories -- simple models for agents subject to constraints -- are burgeoning in quantum information theory. We unite the two domains, confirming Brown and Susskind's conjecture that a resource theory of uncomplexity can be defined. The allowed operations, fuzzy operations, are slightly random implementations of two-qubit gates chosen by an agent. We formalize two operational tasks, uncomplexity extraction and expenditure. Their optimal efficiencies depend on an entropy that we engineer to reflect complexity. We also present two monotones, uncomplexity measures that decline monotonically under fuzzy operations, in certain regimes. This work unleashes on many-body complexity the resource-theory toolkit from quantum information theory.

1 aHalpern, Nicole, Yunger1 aKothakonda, Naga, B. T.1 aHaferkamp, Jonas1 aMunson, Anthony1 aEisert, Jens1 aFaist, Philippe uhttps://arxiv.org/abs/2110.11371