TY - JOUR T1 - Complexity-constrained quantum thermodynamics Y1 - 2024 A1 - Anthony Munson A1 - Naga Bhavya Teja Kothakonda A1 - Jonas Haferkamp A1 - Nicole Yunger Halpern A1 - Jens Eisert A1 - Philippe Faist AB -

Quantum complexity measures the difficulty of realizing a quantum process, such as preparing a state or implementing a unitary. We present an approach to quantifying the thermodynamic resources required to implement a process if the process's complexity is restricted. We focus on the prototypical task of information erasure, or Landauer erasure, wherein an n-qubit memory is reset to the all-zero state. We show that the minimum thermodynamic work required to reset an arbitrary state, via a complexity-constrained process, is quantified by the state's complexity entropy. The complexity entropy therefore quantifies a trade-off between the work cost and complexity cost of resetting a state. If the qubits have a nontrivial (but product) Hamiltonian, the optimal work cost is determined by the complexity relative entropy. The complexity entropy quantifies the amount of randomness a system appears to have to a computationally limited observer. Similarly, the complexity relative entropy quantifies such an observer's ability to distinguish two states. We prove elementary properties of the complexity (relative) entropy and determine the complexity entropy's behavior under random circuits. Also, we identify information-theoretic applications of the complexity entropy. The complexity entropy quantifies the resources required for data compression if the compression algorithm must use a restricted number of gates. We further introduce a complexity conditional entropy, which arises naturally in a complexity-constrained variant of information-theoretic decoupling. Assuming that this entropy obeys a conjectured chain rule, we show that the entropy bounds the number of qubits that one can decouple from a reference system, as judged by a computationally bounded referee. Overall, our framework extends the resource-theoretic approach to thermodynamics to integrate a notion of time, as quantified by complexity.

UR - https://arxiv.org/abs/2403.04828 ER - TY - JOUR T1 - Linear growth of quantum circuit complexity JF - Nat. Phys. Y1 - 2022 A1 - Jonas Haferkamp A1 - Philippe Faist A1 - Naga B. T. Kothakonda A1 - Jens Eisert A1 - Nicole Yunger Halpern AB -

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.

U5 - https://doi.org/10.1038/s41567-022-01539-6 ER - TY - JOUR T1 - Resource theory of quantum uncomplexity JF - Physical Review A Y1 - 2022 A1 - Nicole Yunger Halpern A1 - Naga B. T. Kothakonda A1 - Jonas Haferkamp A1 - Anthony Munson A1 - Jens Eisert A1 - Philippe Faist AB -

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.

VL - 106 UR - https://arxiv.org/abs/2110.11371 U5 - 10.1103/physreva.106.062417 ER - TY - JOUR T1 - A single T-gate makes distribution learning hard Y1 - 2022 A1 - Marcel Hinsche A1 - Marios Ioannou A1 - Alexander Nietner A1 - Jonas Haferkamp A1 - Yihui Quek A1 - Dominik Hangleiter A1 - Jean-Pierre Seifert A1 - Jens Eisert A1 - Ryan Sweke AB -

The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits form a particularly interesting class of distributions, of key importance both to quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we provide an extensive characterization of the learnability of the output distributions of local quantum circuits. Our first result yields insight into the relationship between the efficient learnability and the efficient simulatability of these distributions. Specifically, we prove that the density modelling problem associated with Clifford circuits can be efficiently solved, while for depth d=nΩ(1) circuits the injection of a single T-gate into the circuit renders this problem hard. This result shows that efficient simulatability does not imply efficient learnability. Our second set of results provides insight into the potential and limitations of quantum generative modelling algorithms. We first show that the generative modelling problem associated with depth d=nΩ(1) local quantum circuits is hard for any learning algorithm, classical or quantum. As a consequence, one cannot use a quantum algorithm to gain a practical advantage for this task. We then show that, for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth d=ω(log(n)) Clifford circuits is hard. This result places limitations on the applicability of near-term hybrid quantum-classical generative modelling algorithms.

UR - https://arxiv.org/abs/2207.03140 ER - TY - JOUR T1 - Learnability of the output distributions of local quantum circuits Y1 - 2021 A1 - Marcel Hinsche A1 - Marios Ioannou A1 - Alexander Nietner A1 - Jonas Haferkamp A1 - Yihui Quek A1 - Dominik Hangleiter A1 - Jean-Pierre Seifert A1 - Jens Eisert A1 - Ryan Sweke AB -

There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable in the statistical query model, i.e., when given query access to empirical expectation values of bounded functions over the sample space. This immediately implies the hardness, for both quantum and classical algorithms, of learning from statistical queries the output distributions of local quantum circuits using any gate set which includes the Clifford group. As many practical generative modelling algorithms use statistical queries -- including those for training quantum circuit Born machines -- our result is broadly applicable and strongly limits the possibility of a meaningful quantum advantage for learning the output distributions of local quantum circuits. As a positive result, we show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable by a classical learner. Our results are equally applicable to the problems of learning an algorithm for generating samples from the target distribution (generative modelling) and learning an algorithm for evaluating its probabilities (density modelling). They provide the first rigorous insights into the learnability of output distributions of local quantum circuits from the probabilistic modelling perspective. 

UR - https://arxiv.org/abs/2110.05517 ER - TY - JOUR T1 - Resource theory of quantum uncomplexity Y1 - 2021 A1 - Nicole Yunger Halpern A1 - Naga B. T. Kothakonda A1 - Jonas Haferkamp A1 - Anthony Munson A1 - Jens Eisert A1 - Philippe Faist AB -

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.

UR - https://arxiv.org/abs/2110.11371 ER -