Recently, the dynamics of quantum systems that involve both unitary evolution and quantum measurements have attracted attention due to the exotic phenomenon of measurement-induced phase transitions. The latter refers to a sudden change in a property of a state of n qubits, such as its entanglement entropy, depending on the rate at which individual qubits are measured. At the same time, quantum complexity emerged as a key quantity for the identification of complex behaviour in quantum many-body dynamics. In this work, we investigate the dynamics of the quantum state complexity in monitored random circuits, where n qubits evolve according to a random unitary circuit and are individually measured with a fixed probability at each time step. We find that the evolution of the exact quantum state complexity undergoes a phase transition when changing the measurement rate. Below a critical measurement rate, the complexity grows at least linearly in time until {saturating to a value e Ω ( n ) .} Above, the complexity does not exceed poly ( n ) . In our proof, we make use of percolation theory to find paths along which an exponentially long quantum computation can be run below the critical rate, and to identify events where the state complexity is reset to zero above the critical rate. We lower bound the exact state complexity in the former regime using recently developed techniques from algebraic geometry. Our results combine quantum complexity growth, phase transitions, and computation with measurements to help understand the behavior of monitored random circuits and to make progress towards determining the computational power of measurements in many-body systems.
Recently, the dynamics of quantum systems that involve both unitary evolution and quantum measurements have attracted attention due to the exotic phenomenon of measurement-induced phase transitions. The latter refers to a sudden change in a property of a state of n qubits, such as its entanglement entropy, depending on the rate at which individual qubits are measured. At the same time, quantum complexity emerged as a key quantity for the identification of complex behaviour in quantum many-body dynamics. In this work, we investigate the dynamics of the quantum state complexity in monitored random circuits, where n qubits evolve according to a random unitary circuit and are individually measured with a fixed probability at each time step. We find that the evolution of the exact quantum state complexity undergoes a phase transition when changing the measurement rate. Below a critical measurement rate, the complexity grows at least linearly in time until {saturating to a value e Ω ( n ) .} Above, the complexity does not exceed poly ( n ) . In our proof, we make use of percolation theory to find paths along which an exponentially long quantum computation can be run below the critical rate, and to identify events where the state complexity is reset to zero above the critical rate. We lower bound the exact state complexity in the former regime using recently developed techniques from algebraic geometry. Our results combine quantum complexity growth, phase transitions, and computation with measurements to help understand the behavior of monitored random circuits and to make progress towards determining the computational power of measurements in many-body systems.
Random quantum circuits provide a framework for probing universal dynamical phenomena in chaotic quantum many-body systems, by circumventing the microscopic details of Hamiltonian evolution. Bipartite entanglement measures can be used to characterize the dynamical phases that emerge in these systems. Typically, under random unitary evolution, bipartite entanglement entropies exhibit a linear growth, and attain steady-state values that scale extensively with the system volume. However, when local projective measurements are introduced, a suppression of steady-state bipartite entropies occurs, leading to a sub-extensive scaling with the system volume. This class of entanglement scaling transitions, from an extensive to a sub-extensive scaling regime, has sparked interest in a broader class of measurement-induced phase transitions, with a potential to further our understanding of fault-tolerance in quantum computing, and in realizing synthetic quantum phases on digital quantum simulators. In this work, we characterize entanglement scaling transitions in one-dimensional random quantum circuits composed of q-level systems, with the local Hilbert space dimension q ≥ 2. This predominantly numerical study employs generalizations of the stabilizer formalism and the Clifford group to higher-dimensional Hilbert spaces to simulate the measurement-induced transitions. We find that the nature of the entanglement scaling transition remains invariant under changes in the local Hilbert space dimension. However, the critical measurement rate inducing the transition increases with q, asymptotically approaching 1/2 in the limit q → ∞. To further explore this classical limit, we develop a minimal dynamical model that captures entanglement structures under unitary evolution. We analyze the entanglement structures in thermal stabilizer states using this model, and propose an approach for incorporating measurements within this framework.
The intersection of physics and information theory has advanced rapidly in the past few decades. Information-theoretic concepts have been employed to formulate physical laws, while quantum information processing, such as quantum computation and communication, has been developed both theoretically and experimentally. Simultaneously, understanding the universal or specific behaviors of quantum many-body systems has remained a central challenge since shortly after the inception of quantum mechanics. This is studied in part by statistical mechanics, which models complex many-body systems using simple ensembles. In this thesis, we investigate information-theoretic problems in quantum many-body dynamics that lie at the intersection of these avenues. To begin with, we investigate the extent of randomness, captured by unitary designs, in random quantum circuits. Quantum circuits serve as discrete models for random many-body quantum dynamics. Specifically, we study how the internal structure of random gates influences the generation of randomness in quantum circuits. We demonstrate that the spectral gap of structured random circuits can be larger than that of unstructured ones, implying that the former can converge to designs faster than the latter. In this analysis, free-fermionic techniques play a crucial role in obtaining exact results on the spectrum of second-moment operators. We then investigate the effect of quantum measurements on the quantum complexity in random circuits. Here, the quantum complexity of a state is defined as the minimum number of local gates required for its exact preparation in quantum circuits. We prove that in monitored random quantum circuits, the complexity undergoes a measurement-induced phase transition by leveraging techniques from percolation theory. Above the critical measurement rate, the complexity saturates quickly. Below the threshold, it grows at least linearly for an exponentially long time. Finally, we discuss quantum communication scenarios in noisy quantum dynamics, where we simulate the identity channel by combining a given noisy quantum dynamics and our quantum operational strategies. Specifically, we consider multi-time noisy processes and optimize our strategies to simulate near-noiseless channels, both of which are mathematically formulated using quantum combs. We introduce formal concepts of simulation and capacity for quantum combs, and we derive lower-bounds on the minimum simulation error in terms of semidefinite programming (SDP). We impose certain conditions on our strategies, such as the positive partial transpose (PPT) preserving constraint. We then analyze these SDPs for simple models, such as the depolarizing process, to determine their fundamental communication limits.
Out-of-equilibrium quantum many-body systems stand at the forefront of modern theoretical physics, addressing fundamental questions on thermalization, transport, and universal phenomena. These fields, already well established in condensed matter, statistical physics, quantum optics, and quantum information theory, are progressively gaining even greater relevance with the rapid development of quantum technologies and simulation, which inherently operate in dynamical regimes. In recent years, the traditional paradigm of unitary quantum evolution has been expanded to include measurements, opening new directions in out-of-equilibrium physics. At the core of these advances lie measurement-induced phase transitions (MIPTs), which have emerged as a new class of dynamical critical phenomena characterizing the general behavior of monitored quantum dynamics. When external monitoring intertwines with unitary evolution, many-body quantum correlations change their structure, giving rise to distinct entanglement phases of matter. This discovery has sparked enormous interest in MIPTs, leading to significant advances in open quantum systems, entanglement theory, and more broadly quantum complexity. Despite much progress, a full understanding of monitored many-body dynamics is far from complete, leaving several open questions on the nature of MIPTs, their experimental observability, and the possibilities offered by measurements to enhance control over synthetic quantum matter. These issues persist due to the intrinsic complexity of the problem and the lack of efficient tools to study it, mainly caused by the stochastic character of monitored evolution. This thesis addresses these challenges by expanding the investigation of measurement-induced phenomena in new settings and introducing innovative probes of entanglement and many-body quantum complexity for MIPTs. A core question we investigate is the role of symmetries, non-ergodicity, and especially integrability in measurement-induced criticality, which dramatically affect the non-equilibrium phases. We further explore how these phenomena extend beyond bipartite quantum correlations to multipartite entanglement and quantum non-stabilizerness, highlighting the non-trivial interplay between measurements and complexity notions rooted in quantum information theory. Finally, we focus on the compelling problem of decoherence, modeling how noise spoils entanglement structures. These findings, supported by advanced numerical simulations and theoretical analysis, deepen the current understanding of entanglement, complexity, and integrability in monitored quantum many-body systems, offering new perspectives on their rich behavior. In parallel, we address the experimental problem of dissipation in MIPTs, which is of key relevance for practical implementations. We anticipate the present investigation to foster future research on the nature of monitored dynamical critical phenomena and, more broadly, the applications of measurements in quantum state evolution.
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.
The circuit complexity of time-evolved pure quantum states grows linearly in time for an exponentially long time. This behavior has been proven in certain models, is conjectured to hold for generic quantum many-body systems, and is believed to be dual to the long-time growth of black hole interiors in AdS/CFT. Achieving a similar understanding for mixed states remains an important problem. In this work, we study the circuit complexity of time-evolved subsystems of pure quantum states. We find that for greater-than-half subsystem sizes, the complexity grows linearly in time for an exponentially long time, similarly to that of the full state. However, for less-than-half subsystem sizes, the complexity rises and then falls, returning to low complexity as the subsystem equilibrates. Notably, the transition between these two regimes occurs sharply at half system size. We use holographic duality to map out this picture of subsystem complexity dynamics and rigorously prove the existence of the sharp transition in random quantum circuits. Furthermore, we use holography to predict features of complexity growth at finite temperature that lie beyond the reach of techniques based on random quantum circuits. In particular, at finite temperature, we argue for an additional sharp transition at a critical less-than-half subsystem size. Below this critical value, the subsystem complexity saturates nearly instantaneously rather than exhibiting a rise and fall. This novel phenomenon, as well as an analogous transition above half system size, provides a target for future studies based on rigorous methods.
Quantum complexity is a measure of the minimal number of elementary operations required to approximately prepare a given state or unitary channel. Recently, this concept has found applications beyond quantum computing—in studying the dynamics of quantum many-body systems and the long-time properties of anti–de Sitter black holes. In this context, Brown and Susskind [] conjectured that the complexity of a chaotic quantum system grows linearly in time up to times exponential in the system size, saturating at a maximal value, and remaining maximally complex until undergoing recurrences at doubly exponential times. In this work, we prove the saturation and recurrence of complexity in two models of chaotic time evolutions based on (i) random local quantum circuits and (ii) stochastic local Hamiltonian evolution. Our results advance an understanding of the long-time behavior of chaotic quantum systems and could shed light on the physics of black-hole interiors. From a technical perspective, our results are based on establishing new quantitative connections between the Haar measure and high-degree approximate designs, as well as the fact that random quantum circuits of sufficiently high depth converge to approximate designs. Published by the American Physical Society 2024