{'fraction_non_alphanumeric': 0.038972800841391805, 'fraction_numerical': 0.013862514242309153, 'mean_word_length': 4.703490793968174, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantum simulation using noisy unitary circuits and measurements

Many-body quantum systems are notoriously hard to study theoretically due to the exponential growth of their Hilbert space. It is also challenging to probe the quantum correlations in many-body states in experiments due to their sensitivity to external noise. Using synthetic quantum matter to simulate quantum systems has opened new ways of probing quantum many-body systems with unprecedented control, and of engineering phases of matter which are otherwise hard to find in nature. Noisy quantum circuits have become an important cornerstone of our understanding of quantum many-body dynamics. In particular, random circuits act as minimally structured toy models for chaotic nonintegrable quantum systems, faithfully reproducing some of their universal properties. Crucially, in contrast to the full microscopic model, random circuits can be analytically tractable under a reasonable set of assumptions, thereby providing invaluable insights into questions which might be out of reach even for state-of-the-art numerical techniques. Here, we give an overview of two classes of dynamics studied using random-circuit models, with a particular focus on the dynamics of quantum entanglement. We will especially pay attention to potential near-term applications of random-circuit models on noisy-intermediate scale quantum (NISQ) devices. In this context, we cover hybrid circuits consisting of unitary gates interspersed with nonunitary projective measurements, hosting an entanglement phase transition from a volume-law to an area-law phase of the steady-state entanglement. Moreover, we consider random-circuit sampling experiments and discuss the usefulness of random quantum states for simulating quantum many-body dynamics on NISQ devices by leveraging the concept of quantum typicality. We highlight how emergent hydrodynamics can be studied by utilizing random quantum states generated by chaotic circuits.


I. INTRODUCTION
Recent developments in quantum many-body physics have highlighted the importance of entanglement in understanding phases of matter in and out of equilibrium [1][2][3]. Even limited control of entanglement in quantum circuits has provided an opportunity for the fusion of ideas from quantum information science and condensed matter physics, and an exciting platform for testing our knowledge of quantum many-body physics [4,5]. This has been particularly constructive for understanding phenomena far away from the ground state of quantum many-body systems such as quantum chaos [6][7][8][9][10] and many-body localization [11][12][13][14][15][16]. The quantum simulation of complex quantum phenomena exploring the exponentially large Hilbert space have been enriched by using entanglement as a probe. Entanglement provides a non-trivial parametrization of the many-body states which has ramifications for their simulability [17][18][19]. For non-equilibrium phenomena the dynamics of entanglement can exhibit universal features characterizing the phase of matter and its coarse grained properties, which can be a useful tool for visualizing macroscopic quantum coherence.
Realizations of unitary quantum gates and fast measurements achieved in several physical systems, such as superconducting circuit QED systems [20][21][22] and trapped ions [23][24][25], have opened new avenues for quantum simulation. The low error rates in these unitary gates allow coherent evolution of many-body states over relatively long time scales enabling the study of quantum correlations in the form of entanglement. This experimental effort is in its early stages with 10s of qubits, but nonetheless is already in the realm of providing an advantage for simulating quantum systems compared to classical supercomputers. The quantum control of the microscopic degrees of freedom has also opened the avenue to realize exotic entangled states stabilized by non-equilibrium effects [26][27][28][29]. Digital quantum simulation using a gate-based architecture complements the earlier achievements in analogue quantum simulation using ultra-cold atoms [30][31][32][33][34][35][36] due to its connections to quantum error correction and complexity and provides a new lens for classifying quantum phases of matter [37][38][39][40].
The study of quantum circuits has enriched our understanding of quantum chaos, providing a toy model for describing entanglement dynamics in these systems [7,41]. In contrast to the eigenstate thermalization hypothesis which is applicable to Hamiltonian and Floquet systems [1,42,43], where one is often limited to exact diagonalization to evaluate eigenstates, unitary circuits comprising of randomly chosen gates offer a simplified effective description for chaos. For a certain class of circuits, known as dual-unitary circuits [28,[44][45][46], constrained to be unitary along dual directions of space and time, the dynamics in the circuit are further simplified for certain observables while retaining their quantum chaotic properties. On introducing global conservation laws, the random unitary prescription naturally lends itself to describing the emergent hydrodynamics of the conserved quantities opening a new platform for studying quantum hydrodynamics.
These circuits are also fertile playground for studying dynamics induced by measurements on the qubits [47][48][49]. It opens a new regime for probing dynamics of entanglement of open quantum systems far from equilibrium. Despite measurements, the quantum trajectories of a many-body system for weak measurements can become highly entangled and far from a classical product state. In the strong measurement regime the trajectories become unentangled and lose their quantum correlations. Many questions related to the nature of the phase transitions between these two phases continue to be actively investigated [50][51][52][53][54][55][56][57][58][59]. The entanglement preserving phase can have error correcting properties and is being considered for stabilizing novel many-body states with multipartite entanglement by monitoring local degrees of freedom [60][61][62].
In this chapter, we give an overview of random-circuit models, with a particular focus on the dynamics of quantum entanglement. We will especially pay attention to potential near-term applications of random-circuit models on noisy-intermediate scale quantum (NISQ) devices. To this end, consider a quantum many-body systems with physical degrees of freedom defined on discrete lattice sites. The degrees of freedom can for instance be quantum spins, in which case the local Hilbert-space dimension is d = 2s+1 with s being the spin quantum number, but also fermionic or bosonic particles. In case of an isolated quantum system, its time evolution is unitary and governed by the time-dependent Schrödinger equation. Specifically, given some out-of-equilibrium initial state |ψ(0) , the time-evolved state at a later time t follows as, cf. Fig. 1 (a), where H denotes the Hamiltonian of the system. In practice, however, the evaluation of Eq. (1) is challenging due to the exponentially growing Hilbert space with increasing system size L (D = d L = 2 L for quantum spins with s = 1/2, i.e., qubits). Even though significant progress has been achieved in solving Eq. (1) also for large quantum systems due to the development of sophisticated numerical methods, especially matrix-product state techniques (see e.g. [63]), such approaches are typically limited by the growth of quantum entanglement during the time evolution, where ρ A denotes the reduced density matrix for a bipartition of the system into subsystems A and B. In particular, S(t) is typically expected to increase linearly in time, S(t) ∝ t [64], which causes the computational requirements to faithfully describe the state |ψ(t) to grow exponentially. Note, however, that there are also cases where S(t) builds up slower such as disordered models exhibiting many-body localization [3].
While the out-of-equilibrium dynamics of quantum many-body systems are hard to analyze, random circuits provide minimally structured models to describe their properties. The circuits consist of unitary gates acting locally on the degrees of freedom, for instance in a brickwall pattern akin to well-known Trotter decompositions, see Fig. 1 (b). The gates are not chosen to reproduce the properties of a particular Hamiltonian, but rather to capture the universal aspects of quantum chaotic dynamics. In particular, the gates are drawn at random, for instance the two-site gates in Fig. 1 (b) are d 2 × d 2 matrices, which could be drawn from the unitarily-invariant Haar measure or from the Clifford group [6]. Moreover, it is possible to consider the impact of symmetries, such as conservation of total magnetization or dipole moment, as well as kinetic constraints, by suitably choosing the gates (e.g., Haar-random matrices that are block-diagonal) [7,8,65]. In contrast to the intrinsically continuous time evolution of quantum systems [cf. Eq. (1)], the time evolution in circuit models is discrete, where U is the full unitary operator of one layer of the circuit. Nevertheless, analogous to the Hamiltonian time evolution, the entanglement entropy S(t) is found to grow very rapidly in random-circuit models [6,7]. Crucially, random circuits not only capture the essential features of chaotic quantum many-body dynamics, but in some cases also allow for analytical solutions of the dynamics. The latter makes these models very valuable to gain important insights that are out of reach for currently available numerical approaches.
In this chapter, we especially focus on two particular kinds of circuit models: In Sec. II, we consider monitored circuits, where unitary gates are interspersed with local projective measurements. These circuits can be understood as toy models to describe the interaction of quantum systems with their environment, which constantly "measures" the system leading to decoherence. In particular, it has been found that the competition between unitary gates and projective 1. (a) Given a (chaotic) quantum many-body system described by a Hamiltonian H, the continuous time evolution of a quantum state |ψ is generated by the unitary operator exp(−iHt). (b) Random circuits act as minimal models to describe the properties of chaotic quantum many-body systems, with local gates acting on the degrees of freedom, with the time evolution now being discrete.
measurements leads to a dynamical phase transition between a volume-law phase of S(t) and an area-law phase of S(t). Furthermore, in Sec. III, we consider pseudo-random circuits consisting of one-and two-qubit gates drawn from a set of elementary gates available on today's NISQ devices. These circuits have recently gained importance to demonstrate a quantum computational advantage, i.e., to perform a computational task with a quantum computer that is out of reach for classical machines. We will discuss the main ideas of the random-circuit sampling task that was implemented, and also describe how such circuits can be useful in the context of simulations of quantum many-body dynamics on NISQ devices.

II. MEASUREMENT-INDUCED ENTANGLEMENT TRANSITIONS IN HYBRID QUANTUM CIRCUITS
In a many-body quantum system, the entanglement entropy typically follows a scaling law, where the entropy S(A) of a contiguous subsystem A scales with some geometric property of A. There are several examples of scaling laws. A volume law means the entropy S(A) ∝ |A| + · · · scales to leading order with the size of A, whereas an area law means the entropy S(A) ∝ |∂A| + · · · scales with the size of the boundary of A. The highly entangled volume law states can be found, for example, as the steady states of chaotic quantum dynamics [1], while an area law is often found in states with fast decay of correlations [66], such as the ground states of gapped Hamiltonians [67]. There are also scaling laws intermediate between volume and area laws; for example, the entropy of the ground state of a 1+1D conformal field theory scales logarithmically as S(A) ∝ log |A| + · · · [68].
An entanglement transition is then a phase transition in which the scaling behavior of the entanglement entropy changes in some state of interest, such as an energy eigenstate or the steady state of some quantum dynamics. In this section we will mainly be interested in a particular class of entanglement transitions, known as measurement-induced transitions [17, 26, 27, 37-40, 47-56, 58, 60, 69-106]. These occur in the steady state of nonunitary dynamics, where the nonunitarity is a result of quantum measurements being applied to the system at a constant rate. This setup can emerge quite naturally as a model for the interaction between a system and its environment. When the overall dynamics includes a mixture of measurements and also unitary dynamics, such as Hamiltonian time evolution representing a system's internal dynamics, we will refer to this as 'hybrid quantum dynamics'. Unitary dynamics often provides a natural route to generating entanglement, which is typically (though not always!) destroyed by measurements. However, it is known that entanglement transitions can also occur in measurement-only models [26,54,82,85,94], where the entanglement is generated as a result of frustration between the measurements.

A. Quantum trajectories
When modeling the effect of an external environment on a quantum system, there are several complementary approaches. In the 'mixed state approach', we take into account the fact that some information about the system will leak into the environment by modelling the state of the system with a density matrix. The mixed state ρ(t) will then evolve in time according to some master equation. An alternative viewpoint is the 'quantum trajectories approach', where we model the system with a pure state, and treat the effect of the environment through repeated measurements of the state. These approaches are equivalent in the sense that one can map between the two pictures: averaging over the possible quantum trajectories recovers the master equation for the density matrix ρ, and one can 'unravel' the master equation to focus on individual quantum trajectories. Note that this unraveling is in general not unique; for example, consider the following trajectory equations, both describing Hamiltonian evolution of a fermionic chain undergoing continuous weak measurements [56]. The first class of trajectories, known as quantum state diffusion, is described by where ξ l,t is a real-valued Gaussian variable with zero mean and covariance ξ l,t ξ m,t = γdtδ l,m δ(t − t ), andM l,t = n l − n l t with n l the local fermion occupation number. We could also consider the class of 'quantum jump' trajectories, given by for a state with conserved particle number, where now the noise is defined by ξ 2 l,t = ξ l,t and ξ l,t = γdt n l t . Upon averaging the state |ψ ψ| over the noise {ξ l,t } to get the density matrix ρ = |ψ ψ|, both of these models give rise to the same master equation However, that is not to say that these two forms of trajectory are completely equivalent. In particular, some quantities do not commute with the average over states, in particular if they are a nonlinear function of the state -in other words, we can have functions f of the state with For our purposes the main example of such a quantity will be the entanglement entropy S(A) = −tr [ρ A ln ρ A ], but the same is also true for connected correlation functions of observables, One surprising aspect of measurement-induced transitions is that there can be phase transitions in quantities calculated along individual quantum trajectories that are completely invisible if one only looks at linear functions of the state. In particular, this means that for these phase transitions there can be no order parameter O = tr [Oρ] given by an expectation value taken with the average state. In the rest of this section, we will always average over trajectories only after first calculating the entanglement entropy or any other relevant quantities that can witness the phase transition.

B. Monitored quantum circuits
As a minimal model, consider the quantum circuit shown in Fig. 2 (a). This is a 'hybrid' quantum circuit, consisting of rounds of nearest-neighbor unitary gates, followed by a round of measurements, where at each time step each spin has probability p of being measured. For each spin that is measured, the probability of each outcome is determined by the Born rule, and the state is subsequently updated via a projection on to the corresponding state.
The case with the least structure, retaining only locality and unitarity, is when the unitary gates are drawn uniformly (according to the Haar measure) from the unitary group U(q 2 ), where q is the local Hilbert space dimension. Haarrandom unitaries are highly chaotic, generating entanglement ballistically [6,7] and forming unitary designs in polynomial time [107]. For circuits with Haar-random gates on qubits, q = 2, there is a phase transition in the steady state entanglement from volume-law to area-law at measurement probability p c ≈ 0.17 [47,53], where we can interpret p as the density of measurements in spacetime, cf. Fig. 2 (c). That this probability is nonzero may be surprising, given that naively local unitaries can only generate O(1) entanglement per time step, whereas local measurements can potentially destroy an extensive amount of entanglement. The resolution is that the local unitaries may 'scramble' quantum information, such that the information about the state of a given subsystem is spread out over global degrees of freedom, with the effect that local measurements cannot learn much about the overall state of the system. This is very much in the spirit of quantum error correction, and indeed it has been argued that measurement-induced transitions can be viewed as phase transitions in the quantum channel capacity density Q/N , where the volume-law phase corresponds to Q/N > 0 [60].

C. Purification transition
While the discussion in the previous section couched the measurement-induced transition in the language of an entanglement transition, it turns out that there is an alternative viewpoint in terms of a purification transition [60]. Imagine keeping the same hybrid quantum circuit, but rather than using a product state as the initial state, using the maximally mixed state ρ max = 1/tr [1] instead, as shown in Fig. 2 (b). The action of the hybrid circuit will then be to purify the initial state, eventually reaching a pure state in the steady state. However, it turns out that there can be a phase transition in the time t p taken for this purification -from exponential to polynomial in system size, as shown in Fig. 2 (d) -and further that this transition seems to generically coincide with the entanglement transition for that class of hybrid quantum dynamics [55,60]. Since in an experiment the effect of the environment is such that the state is generically mixed, unlike the pure state setting of the entanglement transition, the purification transition may provide a more robust lens through which to observe measurement-induced transitions in experiments [60].
The purification picture also permits the introduction of an 'order parameter' via coupling the system to an auxiliary system R [76]. In the simplest case, we can take R to be a single qubit. We maximally entangle R with a subset of the system at time t 0 , and then let the system evolve in time -the hybrid circuit acts only on the main system, so any dynamics in R are induced solely through its entanglement with the system. The purification dynamics of R then serve as a local probe of the measurement-induced phase structure [76]. By varying with which subsystem R is entangled, and the time t 0 at which it is entangled, we can probe different critical exponents, as will be discussed further in Section II F.

D. Transitions in the Rényi entropies
There are many quantities that can characterize the entanglement of a quantum state. Focusing on pure states, the most common choice is the von Neumann entropy, where ρ A is the reduced density matrix for subsystem A. But the von Neumann entropy turns out to be very difficult to measure in a large-scale experiment since it requires something like full state tomography [108], whose resource cost scales exponentially with system size.
Happily, there is a related family of entropies, the Rényi entropies, which are more amenable to experimental access. Given a non-negative number n, the n-Rényi entropy S n (A) is defined as with the von Neumann entropy recovered in the limit n → 1. For integer values of n -the easiest being n = 2 -the n-Rényi entropy can be measured in an 'interferometry'-like experiment, where one prepares n identical copies of the quantum state in question, and then measures the Rényi entropy through the expectation value of a certain observable. While this remains a considerable challenge, it has already been demonstrated experimentally [109], and so provides a possible route to accessing entanglement transitions in an experimental setting.
Given the experimental relevance of the Rényi entropies, it is natural to ask whether each Rényi entropy undergoes an entanglement transition at the same critical point. It turns out that while in general not all the Rényi entropies will transition at the same critical point, it follows from some basic properties of the Rényi entropies that many of them will in fact undergo the same entanglement transition. By differentiating with respect to n the definition in Eq. (8) for the n-Rényi entropy, one can show that where D(σ λ) = i σ i log(σ i /λ i ) is the relative entropy, taken between the probability distributions λ = {λ i }, given by the eigenvalues of ρ A , and σ ≡ {λ n i / j λ n j }. As a consequence of the non-negativity of the relative entropy, this implies that In other words, the n-Rényi entropies are non-increasing as a function of n. In terms of the measurement-induced transition, this has the consequence that an area-law in the n-Rényi entropy implies an area-law in the (m > n)-Rényi entropies, and a volume-law in the n-Rényi entropy implies a volume-law in the (m < n)-Rényi entropies. Note however that we don't necessarily have the converse, which would imply that p c is equal for all Rényi entropies.
However, we do have the converse for m, n > 1. This is a consequence of the following inequality, valid only for n > 1, which implies that all the (n > 1)-Rényi entropies must have the same scaling behaviors. This inequality can be proven by using monotonicity of the Rényi entropies and the fact that S ∞ (A) is the largest eigenvalue of ρ A .

E. Analytically tractable limits
To determine the universality class of a phase transition, it is useful to have an analytic treatment. For measurementinduced transitions, such a treatment is currently available in a few select limits. A particularly simple treatment is available for the 0-Rényi entropy S 0 , also known as the Hartley entropy. S 0 (A) simply gives the logarithm of the number of nonzero eigenvalues of the reduced density matrix ρ A . It can be accessed through an adaptation of the 'minimal cut' prescription for calculating the entanglement entropy [48], which first appeared in the context of random unitary circuits [6], and provides a 'coarse-grained' picture for entanglement growth. The upshot is that the measurement-induced transition in the Hartley entropy in d-dimensional hybrid quantum circuits with Haar-random gates is in the universality class of (d + 1)-dimensional percolation, where the extra dimension comes from the time direction of the quantum circuit. Furthermore, the critical measurement probability is precisely the bond percolation threshold for percolation on a lattice determined by the geometry of the quantum gates.
Percolation also appears in a different limit, corresponding to the transition in the (n ≥ 1)-Rényi entropies strictly in the limit of infinite local Hilbert space dimension q = ∞. Here the connection to percolation is more subtle: it appears only in a replica limit Q → 1 of a Q!-state Potts model obtained by averaging over unitary gates and measurements in a system where the gates are drawn from the Haar distribution over the unitary group [70]. This treatment indicates that all the (n ≥ 1)-Rényi entropies undergo a phase transition at the same critical point, consistent with the discussion in Section II D. Interestingly, it turns out that the q = ∞ fixed point is unstable in the sense that finite q explicitly breaks an emergent symmetry, allowing for the presence of an RG-relevant perturbation that drives the system away from the percolation fixed point. At the time of writing, the ultimate fate of that new fixed point is unknown, but remains a focus of current research.

F. Critical properties of measurement-induced transitions
In Section II E we saw that in certain limits the measurement-induced transition was in the percolation universality class. However, both of these limits are somewhat unphysical: realistic quantum spin systems typically have finite local Hilbert space dimension, and the 0-Rényi entropy can change discontinuously under arbitrarily small perturbations to the density matrix. Away from these limits, we turn to numerical probes to determine the relevant universality classes.
The critical exponents determining a universality class are typically obtained in numerics through finite-size scaling.
In the rest of this section, we will mainly focus on numerics performed on Clifford circuits, where the unitary gates are drawn uniformly from the Clifford group. Clifford circuits are convenient to look at in the context of measurementinduced entanglement transitions because they can be efficiently simulated classically [110], while still being able to rapidly generate entanglement. Their classical simulability is important in enabling sufficiently large system sizes that finite-size scaling provides good estimates of critical exponents. Furthermore, Clifford operations often turn out to be relatively easy to implement on current quantum computing devices, so hybrid Clifford circuits may be some of the first to be simulated in experiments. Box 1 outlines a method to classically simulate Clifford circuits using a graph-state based algorithm which is particularly suitable in the context of entanglement phase transitions.
To extract the critical point numerically, a natural quantity to look at in 1+1D is the half-chain entanglement entropy S(L/2) (all Rényi entropies are equal in Clifford circuits). However, this has the disadvantage that it appears to scale logarithmically with system size L, as in a 1+1D conformal field theory [68]. This means that at the critical point the entanglement entropy for different system sizes does not coincide, so one cannot simply 'read off' the critical point by looking at the data. Furthermore, if one attempts to extract the critical point p c and other critical exponents using standard finite-size scaling, these can have correlated errors depending on the extracted value of p c . For a better estimator of the critical point, we turn to the tripartite information I 3 , defined as where is the mutual information. One can show that for pure states, given a partition into four subsystems, the tripartite information of three of the subsystems does not depend on the choice of subsystems, so we will simply write I 3 ≡ I 3 (A : B : C) from now on, with the partition in Fig. 3 (b) in mind. One can then argue using the 'minimal cut' prescription of Ref. [48] that for this choice of partition, I 3 cancels out the 'boundary' contributions that give rise to the logarithmic scaling of the entanglement entropy at criticality [53], resulting in the scaling Notably, this means that at the critical point I 3 (p c , L) should coincide for different system sizes L, providing a much more accurate estimator of the critical point. Figure 3 (a) shows a data collapse of I 3 calculated in the steady state of 1+1D random Clifford circuits, which yields the estimate p c ≈ 0.158 for the critical point and ν ≈ 1.33 for the correlation length exponent. Notably, the latter is still very near the value of ν = 4/3 for 2D percolation, despite the discussion in Section II E that for finite local Hilbert space dimension (here q = 2) we should expect the universality class to be distinct from percolation.
To measure other critical exponents, we turn to the 'auxiliary system' method discussed in Section II C. For example, to extract the bulk exponent β, we initialize the system for a time t 0 = 2L, and then entangle a reference qubit R with the system qubit at position x = L/2, i.e. in the bulk. We then evolve the system for a further time t = 2L, and measure the entanglement entropy of R. Close to the phase transition, the circuit-averaged entropy should scale as S(R) ∼ (p c − p) β , reaching zero in the area-law phase. This yields the values β = 0.14(1) in 1D [53] and β = 0.40 (1) in 2D [55]. Again both of these values are reasonably close to the corresponding values for 2D and 3D percolation, β 2D = 5/36 ≈ 0.139  and β 3D ≈ 0.43. However, there is increasing evidence that, despite these similarities, the measurement-induced transition in Clifford circuits is indeed in a different universality class to percolation [53,55,71,97].
We can also extend this method to measure correlation function exponents. We introduce two auxiliary systems, R 1 and R 2 , which are entangled with separate subsystems at a time t 0 , and then subject to dynamics again only through their entanglement with the main system. We can extract correlation function exponents by studying their mutual information I 2 (R 1 : R 2 ), which serves as an upper bound on all connected correlation functions of local observables [111]. For example, the exponent η governs the power-law decay of bulk correlation functions for local observables A r and B 0 supported at sites r and 0 respectively. We can extract this exponent by initializing the system for time t 0 = 2L, entangling auxiliary qubits R 1 and R 2 with the bulk qubits at positions x = L/4 and x = 3L/4, and then letting the system evolve for a further time t = 2L. The mutual information should then decay as I 2 (R 1 : R 2 ) ∼ 1/L η in 1+1D, so we can extract η by optimizing for a data collapse of L η I 2 (R 1 : R 2 ) for different system sizes L. We could also extract the corresponding surface correlation length exponents η ⊥ and η by choosing to entangle one or both of R 1 and R 2 to a surface qubit instead of a bulk qubit. In Fig. 3 (c) we reproduce from Refs. [53,55] the current numerical estimates of the critical exponents of the measurement-induced transition in 1+1D and 2+1D Clifford circuits, which were determined using the methods described here.

Box 1 | SIMULATING CLIFFORD CIRCUITS WITH GRAPH STATES
The Clifford group C n on n qubits is defined as the group that preserves the corresponding Pauli group P n under conjugation, modulo global phases. To be concrete, we focus on models with nearest-neighbor unitary gates drawn uniformly from the two-qubit Clifford group C 2 , akin to the sketch in Fig. 2 (a), and with projective measurements in the σ z basis. The two-qubit Clifford group can be generated by the gates {H, S, CZ}, where CZ is a two-qubit controlled-Z gate, and H and S are the single-qubit Hadamard and phase gates given in the computational basis by Ignoring overall phases, the resulting group has 11520 elements, which is sufficiently small that it can be hardcoded as a lookup table decomposing each group element into a product of the generators. This allows for simulations of random Clifford circuits using a graph-state based algorithm [112], which makes use of the fact that all stabilizer states resulting from a Clifford circuit can be written as a graph state, up to the action of some one-qubit Clifford gates [113]. Alternative simulation methods exist, most notably one based on storing a 'stabilizer tableau' of the stabilizers fixing the quantum state, and then updating the tableau based on the action of Clifford gates [114]. However, the graph-state method is particularly well suited to the study of measurement-induced transitions, because its time complexity scales with the typical vertex degree of the graph storing the quantum state. This degree is generically reduced by the presence of measurements, such that it is possible to simulate very large system sizes in the area-law phase and near the critical point.

Graph states and stabilizer states
The graph-state algorithm relies on a fortunate connection between graph states and stabilizer states, the latter being the states generated by Clifford circuits acting on the |0 ⊗N initial state. Namely, all stabilizer states can be written as a graph state, up to the action of some one-qubit Clifford gates [113]. Given a graph G = (V, E), the graph state |G is defined by where |+ = (|0 + |1 )/ √ 2, and N is the total number of qubits. That is, starting from the initial state |+ ⊗N , we perform a controlled-Z gate between all pairs of qubits (i, j) connected by an edge in the graph. Thus, to represent the graph state |G we just need to store the graph G, which only takes O(N 2 ) memory. We can then write any stabilizer state as where the C i are drawn from the one-qubit Clifford group C 1 . This group has only 24 elements up to phase, so this additional information is only an O(N ) overhead.
The entanglement in a graph state is completely fixed by the graph G. Suppose we wanted to calculate the entanglement entropy of a subsystem A. Partitioning the adjacency matrix Γ of G into the block form where B is the complement of A, the entanglement entropy S A is given by the rank over the binary field F 2 of the subadjacency matrix Γ AB characterizing connections between A and B [115].

Implementing Clifford operations
Clifford operation Time complexity Note that there is some 'gauge freedom' in writing stabilizer states this way, so different combinations (G; {C i }) can correspond to the same quantum state. This freedom turns out to be useful in implementing two-qubit Clifford operations on the quantum state.
Here we will summarize how one performs Clifford gates and Pauli measurements on stabilizer states represented in this way -for the full details we refer the reader to Ref. [112]. The relevant time complexities of the different operations are shown in Table I.
One-qubit Clifford gates are trivial to perform since they leave the graph invariant -we merely have to update the one-qubit Clifford C i corresponding to the site i of the gate, which takes Θ(1) time. This can be done with a lookup table of size |C 1 | 2 = 24 2 . Two-qubit Clifford gates are more technical, since they involve both the graph and the one-qubit Cliffords. We only need to focus on implementing CZ gates, since this is the only two-qubit gate in the generating set of the two-qubit Clifford group. There are two cases in implementing CZ on a given pair of qubits (i, j). The easy case is if the corresponding one-qubit Cliffords C i and C j commute with CZ i,j . In this case, the CZ leaves the one-qubit Cliffords unchanged, and toggles the edge (i, j) in the graph. The harder case is if CZ i,j does not commute with the one-qubit Cliffords, and it is here that the 'gauge freedom' becomes useful. The goal is to move to a gauge where the problem is reduced to the easy case previously described. We do this using an operation called 'local complementation', which toggles all the edges in the subgraph induced by the neighborhood of a given vertex, say i, and then modifies the one-qubit Cliffords of site i and its neighbors. In this way, one can obtain C i and C j which commute with CZ i,j . The local complementation is the dominant cost, taking time O(d 2 ), where d is the maximum vertex degree of qubits i and j. This scaling with d rather than system size N means the runtime of this algorithm depends strongly on the connectedness of the graph, and hence, roughly speaking, that less entangled states are quicker to simulate. This is especially pertinent in the context of entanglement phase transitions. In principle, d can be as large as O(N ), and this scaling is relevant in the volume-law phase. However, in the area-law phase and near the critical point, the typical vertex degree can be O(1), so that even two-qubit gates are easy to implement.
Finally we describe how to perform single-site Pauli measurements. The basic idea is to reduce the measurement on the stabilizer state |G; {C i } to a measurement on the underlying graph state |G without the one-qubit Cliffords. Suppose we measure Pauli P a on site a, with outcome λ ∈ {±1}. The stabilizer state will be updated to where we inserted a factor of 1 = C a C † a in the last step. Since C a is a Clifford operator and preserves spectra, P a ≡ C † a P a C a ∈ {±X a , ±Y a , ±Z a }. Hence the effect of measuring Pauli P a on the stabilizer state |G; {C i } can be modelled by measuring Pauli P a on the graph state |G . Relegating full details of graph state measurements to Refs. [112,113], we note that Pauli Z measurements are particularly simple: they simply remove all edges from the graph connected to the measured site, which takes O(d) time.

Scalability issues
As discussed in Section II D, it is very difficult to experimentally measure the von Neumann entropy, but this can possibly be ameliorated by instead measuring a Rényi entropy, such as the 2-Rényi entropy S 2 (related to the purity via tr ρ 2 = exp[−S 2 ]). However, before one can get to that point one has to reliably and repeatedly prepare a given steady state for which the entropy is to be calculated, and it is here that the probabilistic nature of the measurements can present an issue of scalability. Even if we fix the measurement locations for simplicity, their random outcomes mean that for T rounds of measurements with probability p, in a system of N spins with local Hilbert space dimension q, the number of repetitions required to get O(1) samples of a given trajectory is of the order q pN T , which is exponential in the system size. To make things worse, the equilibration time T is typically at least linear in the system size N , so the sampling overhead can be doubly exponential in N . In principle, this presents a severe barrier to scaling up these experiments to the large system sizes where phase transitions are most apparent.
There are several options to try to avoid this particular issue of postselection. One option is to relate entanglement entropy to a quantity which can be more easily measured. In particular, this is possible by relating a given hybrid quantum circuit to its spacetime dual. Given a unitary matrix U acting on a pair of spins, we denote its matrix elements by [U ] ioutjout iinjin . This matrix is unitary in the 'time' direction, expressed by the condition kl [U ] kl iinjin [U * ] kl ioutjout = δ iinjin,ioutjout . However, we could decide to swap the space and time directions: viewing the unitary U as a tensor with four legs, two for input and two for output, we form an associated tensor U , where one of the original output legs of U becomes an input leg of U , and one of the original input legs of U becomes an output leg of U . The resulting U is generically nonunitary, and can be interpreted as a unitary gate followed by a weak measurement [17]. Thus by taking the spacetime dual we have a relation between a hybrid quantum circuit and an associated unitary circuit. It turns out that one can relate the 2-Rényi entropy in the hybrid circuit to a correlation function in the unitary circuit [93], which is typically much easier to measure in an experiment.
Another option is to consider a modification of the measurement protocol, where instead of having random measurements with outcomes distributed according to the Born rule, we consider a non-unitary but deterministic time-evolution, such as that resulting from a non-Hermitian Hamiltonian [96]. In effect one can think of this as being similar to 'forcing' certain measurement outcomes. [77]. Non-Hermitian Hamiltonians can emerge quite naturally in certain open quantum systems undergoing continuous measurement. However, it is worth noting that the measurement-induced transition in these systems may be somewhat different in character to that in random quantum circuits with Born rule projective measurements-in replica treatments of the phase transition (see Section II E), the Born rule factor necessitates an additional replica compared to the case of forced measurements [70], so the latter in fact appears to be more like closely related transitions in random tensor networks [116]. Additionally, the lack of quenched randomness with forced measurements may give rise to qualitatively different behavior of the entanglement domain walls that arise in statistical mechanical models describing these transitions.

Measurement-induced transition in a trapped-ion experiment
Ref. [25] presented the first experimental observation of a measurement-induced transition. They studied a chain of 13 trapped 171 Yb + ions, with relatively high gate fidelities of 99.96% for single-qubit gates and 98.5-99.3% for two-qubit gates. Instead of directly measuring the entanglement entropy, they focused on the measurement-induced transition in the purification picture, as discussed in Section II C, since this is typically more robust to experimental imperfections, and also made use of the following simplification. In this system certain operations are easier to perform than others: the 'native' two-qubit gate they employ is an 'Ising' XX gate of the form U (θ) = exp(−iθσ x i σ x j ), where the value of θ is controlled by the duration of a control pulse. The use of this gate implies that if measurements are performed in the σ x basis then we will quickly approach a σ x -basis product state, since the XX Ising gates cannot generate entanglement from σ x basis states. Exploiting this fact, the authors consider a modification of the usual purification protocol, fixing the overall measurement probability p, but performing the measurements in two different bases, the σ x and σ z bases. There is an additional parameter p x that controls the probability that a given measurement is performed in the σ x basis. With p fixed to a small value to limit the overall number of measurements, there is a phase transition as a function of p x between the slow-and fast-purifying phases.

III. RANDOM CIRCUITS ON NOISY-INTERMEDIATE SCALE QUANTUM DEVICES
As outlined so far, random circuits with different designs have proven extremely useful to understand the properties of quantum many-body systems and the dynamics of entanglement. Recently, random circuits have found a new application in quantum information science. In particular, they have been used to demonstrate "quantum supremacy" or, in other words, a quantum computational advantage, which refers to the fact that a quantum device can perform a task that is unfeasible for its classical counterpart [4]. Such a demonstration of a quantum advantage is especially nontrivial given the eponymous noise of today's NISQ devices. This is not least the reason why, as a computational problem to achieve "quantum supremacy", it was chosen to sample from the output probability distribution of a random circuit, which is believed to be a hard task for classical supercomputers. In Sec. III A, we will provide an introduction to the main ideas of random-circuit sampling. Moreover, in Sec. III B, we will discuss that random circuits on NISQ devices are not just abstract tools to outperform classical computers, but are useful in a wider range of applications. To this end, we will leverage the concept of quantum typicality (see Box 2) and focus on the results reported in Ref. [117].
A. Random-circuit sampling for achieving a quantum computational advantage Random circuits are natural candidates when striving to outperform classical computers. On one hand, random circuits seem more appealing than some arithmetic calculation in view of the noise of today's NISQ devices. On the other hand, these circuits are challenging for classical machinery due to the lack of structure and the quick generation of entanglement. The main idea of random-circuit sampling is as follows [118,119]. Given a random circuit R, apply R to the L qubits of the system and measure all qubits afterwards, which yields a bitstring |k = |010110 · · · according to Born's rule with probability z = | k|R|0 | 2 . Repeating this experiment many times then yields a set of bitstrings |k 1 , |k 2 , |k 3 , . . . , which allows to draw conclusions on the underlying probability distribution. In particular, for random circuits that are sufficiently deep, it is expected that the resulting state is Haar-random [118,[120][121][122][123][124], i.e., it is a realization drawn from the uniform distribution on the 2D-dimensional unit sphere, where D = 2 L is the dimension of the Hilbert space. In practice, this implies that the complex coefficients c k of the wave function R |0 = k c k |k are drawn from a Gaussian distribution and that the probability distribution of z = |c k | 2 follows as [118,125], where the approximation on the right hand side of Eq. (22) applies to large Hilbert-space dimensions D, and is sometimes referred to as Porter-Thomas law [126].
In order to demonstrate a quantum computational advantage using random-circuit sampling, several key points have to be addressed [125]. First of all, it is important to execute the random circuit on a large system that surpasses the capacities of classical computers (currently the best supercomputers can evaluate circuits with L ≈ 45 [127]). However, for such large systems, the corresponding Hilbert space is huge and reconstructing the probability distribution p(z) would require an impracticably high number of bitstrings (experimental repetitions). Moreover, how can one verify that the quantum device indeed samples from the correct probability distribution if classical verification is impossible? An important step to overcome these difficulties has been achieved by the introduction of cross-entropy benchmarking (XEB) [118]. To understand XEB, consider an ideal (quantum) computer that can execute R and thus provides the probabilities p(|k ) of all 2 L bitstrings. Now, let a NISQ device execute R and we collect N samples S = {|k 1 , . . . , |k N }. If N is large enough, we could reconstruct the corresponding probability distribution p NISQ (|k ) and compare it with the ideal distribution p(|k ) using standard statistical tools. However, even for a smaller number of samples, it was shown that conclusions on the quality of the NISQ device can drawn based on an approximation of the cross entropy [118,125], where the second part results from replacing the sum over all D bitstrings by the sample average justified by the central limit theorem. In practice, the probabilities p(|k ) to perform XEB are obtained numerically by simulating the quantum circuit on a supercomputer. Obviously, this is not possible in the regime of system sizes and circuit depths where a quantum computational advantage occurs. Nevertheless, various sophisticated techniques have been developed (e.g., considering elided circuits with fewer entangling gates [119]) to estimate the cross entropy in Eq. (23) also in such cases. For more details on XEB, we refer to [118,119,125].
A quantum computational advantage based on random-circuit sampling has been announced for the first time using Google's NISQ device Sycamore [119]. In the experiment, the Josephson junction-based processor executed a random circuit consisting of layers of one-qubit and two-qubit gates. We will discuss such types of circuits in more detail in Sec. III B. Due to imperfections in the execution, it was found in [119] that the cross entropy decays exponentially with the number of qubits and the depth of the circuit. Nevertheless, a nonzero S XEB was established even for the largest circuits with 53 qubits and 20 cycles of one-qubit and two-qubit gate layers, implying that the processor samples from a nontrivial probability distribution. In particular, according to Google's estimate at that time, a classical supercomputer would require 10,000 years for the same task (albeit significantly lower estimates have been suggested subsequently [128,129]). In more recent experiments, a team from China used their superconducting quantum processor Zuchongzhi 4. (a) Algorithm to simulate dynamical spin-spin correlation function. A random circuit R acts on L − 1 qubits (except site ), followed by a time evolution U (t) on all L sites. Measurement on site then yields C , (t). (b) We here consider a two-dimensional geometry. Similar to [118,119], R consists of layers of one-qubit and two-qubit gates, cf. Fig. 5 (c). The patterns A-D indicate the position of the two-qubit gates in different cycles. (c) For reference site = 1, the expectation value ψ R, (t)| S z |ψ R, (t) yields 2C , (t). Data is shown for the Heisenberg chain with L = 25, where the dynamics of the one-dimensional system can be simulated by considering a snake-like path through the two-dimensional grid. Figure adapted from Ref. [117].
to perform random-circuit sampling for even larger qubit numbers and circuit depths, which impressively substantiate the fact that a quantum computational advantage has indeed been achieved [130,131]. Eventually, it is important to note that a quantum computational advantage is of course a moving target since both quantum and classical hardware as well as algorithms are expected to further improve in the future [132].

B. Applications of random circuits in quantum many-body physics
While sampling the outcome of random circuits is arguably a rather abstract task, it is an intriguing question to what extent the current capabilities of NISQ devices can be leveraged to study a wider class of problems. In this context, we specifically refer to questions in quantum many-body dynamics, which are generally challenging for classical computers due to the exponentially large Hilbert space. Simulations on NISQ devices might provide an opportunity to tackle these challenges and, moreover, to open up novel directions of research. In particular, it is important to note that today's NISQ devices, with of the order of 50 qubits, already operate in Hilbert spaces that are competitive to or even go beyond what is possible with the best supercomputers, as also demonstrated recently [133][134][135] In this section, we discuss a recent proposal to simulate hydrodynamics in quantum many-body systems on NISQ devices using random circuits [117], which emphasizes that random circuits are not just useful to demonstrate "quantum supremacy", but they in fact form tailor-made building blocks to study questions in quantum many-body physics. The two key points in this context are that (i) random circuits swiftly generate random highly entangled quantum states, and (ii) the properties of such random states can be exploited for efficient simulations by relying on the concept of quantum typicality [136][137][138][139] (see Box 2). More specifically, Ref. [117] presented a scheme to compute the infinite-temperature spatiotemporal correlation function C , (t), where S z is a spin-1/2 operator at lattice site , S z (t) = e iHt S z e −iHt is the time-evolved operator with respect to a Hamiltonian H (although, in principle, evolutions with respect to other unitaries U (t) are conceivable as well), and L denotes the numbers of spins (qubits). The algorithm to simulate C , (t) is sketched in Fig. 4 (a). First, all qubits are initialized in the |0 state. (We identify |0 ≡ |↑ and |1 ≡ |↓ in the following.) A random circuit R then acts on L − 1 qubits (except for site ). The resulting state |ψ R, = |0 ⊗ R |0 ⊗L−1 is evolved in time, |ψ R, (t) = e −iHt |ψ R, , and the measurement at site yields the spatiotemporal correlation function according to (see [117] for a derivation), where the statistical error of the quantum-typicality approximation vanishes exponentially with increasing system size [125]. In this context, quantum typicality can be interpreted as a form of "quantum parallelism" [140,141], as the time 10´ evolution of a single random state |ψ R, already captures the full ensemble average. This typicality-based approach to simulate dynamical two-point correlation functions such as C , (t) on a quantum computer is complementary to other established schemes [142][143][144], and operates without an overhead of bath or ancilla qubits. Crucially, it is a direct extension of the random-circuit experiments already realized on today's NISQ devices [119,130,131].
We now discuss the individual components of the algorithm in more detail. As in [118,119], we consider a twodimensional grid of qubits. The random circuit R then consists of individual cycles, each composed of a layer of one-qubit gates and a layer of two-qubit gates, where we denote the total number of cycles with d. The two-qubit gates generate entanglement between different parts of the system, and different choices are possible such as CZ or CNOT gates [117,145], or other hardware-specific gates [119,133]. As shown in Fig. 4 (b), they are aligned in one of the patterns A-D, and the sequence ABCD· · · is repeated in subsequent cycles throughout R. Afer d cycles, |ψ R, = 2 L k=1 c k |k is a superposition of computational basis states. In particular, even for moderately shallow R, |ψ R, will approximate the properties of a full Haar-random state (we will discuss this fact further below in the context of Fig. 5), i.e., the coefficients c k are approximately distributed according to a Gaussian distribution with zero mean. As a consequence, these states can be used within the typicality approach to calculate C , (t).
As a numerical example, we here consider the dynamics with respect to the paradigmatic spin-1/2 Heisenberg chain, where the one-dimensional model can be readily studied using a snake-like path through the two-dimensional grid, see Fig. 4 (c). The time evolution with respect to H is then evaluated by decomposing U (t) = exp(−iHt) into discrete Trotter steps [146,147], where H e (H o ) denotes the even (odd) bonds of H and δt = t/N is a (short) time step.
After having outlined the general principle of the algorithm, it is insightful to go back one step and study the buildup of randomness of |ψ R, due to the action of R. Such an analysis is presented in Figs. 5 (a) and (b) in terms of the participation entropy S p k (|ψ R, ) and the von Neumann entanglement entropy S vN (|ψ R, ), with p k = |c k | 2 , and ρ A = Tr B |ψ R, ψ R, | being the reduced density matrix for a half-system bipartition. As already mentioned above, R consists of one-qubit and two-qubit gates, cf. Fig. 5 (c). For the simulations shown here, the one-qubit gates are drawn at random from the set {X 1/2 , Y 1/2 , T }, where X 1/2 (Y 1/2 ) are π/2 rotations around the x-axis (y-axis) of the Bloch sphere and T is the non-Clifford gate T = diag(1, e iπ/4 ). Similar to [118,119], gates on a given site have to be different in subsequent cycles. As two qubit gates, we here consider CNOT gates. As shown in Fig. 5 (a) and (b), both S p k (|ψ R, ) and S vN (|ψ R, ) saturate towards their analytically known random-state values already for moderate depth d of R. Specifically, S p k (|ψ R, ) approaches ln(2 L−1 ) − 1 + γ with Euler constant γ ≈ 0.577 [118] already at d 10, with no major dependence on L. Likewise, S vN (|ψ R, ) approaches the "Page value" ln(2 L/2 ) − 1 [150] appropriate for a random state on L − 1 sites, albeit the depth d to reach this value appears to grow slightly with L. It is important to stress that the design of R chosen here is by no means optimized but already sufficient to create highly random and entangled states. In Fig. 5 (d), we analyze the dependence of the expectation value ψ R,1 (t)| S z 1 |ψ R,1 (t) on the depth d of R. While this expectation value converges to the exact autocorrelation function 2C , (t) for sufficiently large d, we find in Fig. 5 (d) that even for rather shallow circuits with d = 10, the resulting dynamics is almost indistinguishable from the dynamics for d = 20. Thus, even for states with entanglement below the Page value, cf. Fig. 5 (b), the resulting dynamics is still a good approximation to C 1,1 (t) and captures the correct hydrodynamic behavior.
Finally, let us comment on the accuracy of the typicality approach. In Fig. 6 (a), we compare the dynamics of two states that result from different realizations of the random circuit, R 1 and R 2 . Moreover, we also show data obtained from exact diagonalization. Even for the rather small system size L = 16 chosen here, we find that the dynamics obtaind from |ψ R1, and |ψ R2, closely follow the exact result with only minor fluctuations. In particular, these residual fluctuations can be further suppressed by averaging over multiple random realizations of R. As shown in Fig.  5 (a), the dynamics obtained by averaging over 10 2 realizations is indistinguishable from ED. Note that for larger system sizes (i.e., significantly larger Hilbert-space dimensions) quantum typicality becomes more and more accurate such that such an averaging is not necessary anymore and a single realization of R is sufficient [125].
While we have so far focused on the full expectation value ψ R, (t)| S z |ψ R, (t) , this expectation value cannot be obtained on a quantum computer in a single run. In particular, |ψ R, (t) will generally be a superposition of computational basis states, |ψ R, (t) = 2 L k=1 a k |k , and the coefficients a k can be reconstructed by repeating the experiment multiple times and averaging the final measurements of the qubits. More specifically, C , (t) can be reconstructed as, where | a k | 2 is the experimentally obtained probability of the state |k , and the two sums in (28) run over all states for which the spin is up or down respectively. The accuracy can be systematically improved by increasing the number of samples N s such that | a k | 2 → |a k | 2 . Crucially, as we show in Fig. 6 (b), the sampling of the distribution of the |a k | 2 can be combined with the averaging over random realizations of R. Specifically, Fig. 6 (b) compares the dynamics obtained from one realization of R with N s = 10 5 repetitions to the dynamics obtained from 10 2 realizations of R with N s = 10 3 repetitions each, i.e., the total number of runs is the same in both cases. While the noise level is found to be similar in both cases, we observe that the data averaged over multiple R agrees better with ED. In this context, we note that varying R on a NISQ device is straightforward experimentally.

Box 2 | QUANTUM TYPICALITY
The notion of quantum typicality refers to the fact that the overwhelming majority (Haar measure) of quantum states within some energy shell yields expectation values of observables very close to the full microcanonical ensemble [136][137][138][139]. Speaking differently, given a single pure quantum state, drawn at random from a high-dimensional Hilbert space, the expectation values of observables with respect to this state will be effectively indistinguishable from their thermodynamic equilibrium values. As such, quantum typicality has been put forward as an important concept to explain the emergence of thermodynamic behavior in closed quantum systems [151,152]. Here, we focus on the implications of typicality for efficient simulations (see [125,153] for reviews).

Quantum typicality as a numerical tool
The key idea in this context is that random quantum states are highly accurate trace estimators [154,155]. To demonstrate this fact, let |ψ be a random state, drawn from the unitarily invariant Haar measure, where the coefficients a k and b k are Gaussian-distributed with zero mean and unit variance, and |k denote a set of orthogonal basis states of the Hilbert space with dimension D. Given an observable O, its trace can then be written as [125], where the overline means averaging over random realizations of |ψ . Importantly, the second equation in (30) emphasizes that for sufficiently large Hilbert-space dimensions, even a single realization of |ψ provides an accurate approximation of tr [O]. In particular, given some mild assumptions on the spectral properties of O, the statistical error of the approximation vanishes for D → ∞ (see, e.g., [125] for details on error bounds). It is straightforward to extend the scheme in Eq. (30) to equilibrium expectation values of O at temperature T = 1/β [156], where |ψ β is sometimes referred to as thermal pure quantum state [156] and the standard deviation of the statistical error scales as σ( ) ∝ 1/ √ d eff , with d eff = tr[exp(−β(H − E 0 ))] being an effective dimension, and E 0 is the ground-state energy of H [125,156]. Furthermore, quantum typicality also carries over to time-dependent situations (see e.g., [152,[157][158][159][160]), which has been particularly exploited in the context of dynamical two-point correlation functions, which can be approximated as [161][162][163][164], where |ϕ β (t) = e −iHt O 2 e −βH/2 |ψ , |ψ β (t) = e −iHt e −βH/2 |ψ . The crucial ingredient why the pure-state approximations in Eqs. (31) and (32) are useful is given by the fact that the temperature-and time-dependence can be efficiently evaluated by using well-established sparse-matrix techniques [165] (e.g., Krylov-subspace methods [166], or Chebyshev-polynomial expansions [167][168][169]). These methods essentially rely on matrix-vector multiplications which can be carried out both time and memory efficient. In particular, no exact diagonalization of H is required such that significantly larger Hilbert spaces can be handled.

Quantum typicality versus eigenstate thermalization hypothesis (ETH)
The ETH asserts that the diagonal matrix elements of observables written in the eigenbasis of chaotic nonintegrable Hamiltonians are a smooth function of energy and agree with the corresponding microcanonical expectation value [1], While the ETH has been numerically confirmed for a variety of models and observables, it is known to break down for instance in strongly disordered models exhibiting many-body localization [3]. In this case, the diagonal matrix elements show pronounced eigenstate-to-eigenstate fluctuations, O nn = O (n+1)(n+1) = O mc (E). In contrast, the concept of typicality remains valid irrespective of the ETH being fulfilled. Specifically, consider a state |ψ E that is constructed as a random superposition of eigenstates |n in an energy shell with mean energy E. Then, the expectation value of O with respect to |ψ E will again be very close to the microcanonical expectation value as long as the energy window contains sufficiently many eigenstates to reduce statistical errors, where c n are Gaussian random numbers.
As a consequence, quantum typicality can be exploited as a numerical tool to study the properties of integrable or many-body localized systems where the ETH breaks down [170][171][172][173], as well as to verify the validity of the ETH for system sizes beyond the range of exact diagonalization [174,175].

IV. CONCLUSION
The goal of this chapter was to give a brief overview of certain aspects of random quantum circuits. Such random circuits have recently gained increased attention as minimally structured models for quantum many-body systems, providing new insights into challenging questions, e.g., regarding the dynamics of entanglement or the emergence of hydrodynamics. In view of the vast literature, we here deliberately refrained from giving an in-depth review of all actively pursued directions, but rather refer the interested reader to the pertinent references included in Secs. I -III. Instead, we here focused in more detail on two particular topics, i.e., (i) entanglement transitions in monitored circuits, where random unitary gates are interspersed with measurements, and (ii) random quantum circuits recently implemented on noisy intermediate-scale quantum devices to achieve a quantum computational advantage.
In the context of monitored circuits, we have given an introduction to the notion of quantum trajectories and reviewed the equivalent pictures of a measurement-induced pure-state transition from volume-law to area-law scaling of the entanglement entropy and a purification transition from mixed to pure states with increasing measurement rate. We have particularly discussed the critical properties of the transition in one and two dimensions and explained how Clifford circuits, especially in combination with graph states, provide a powerful approach to explore this type of physics numerically. Moreover, we have touched on the challenges to realize and observe entanglement transitions in monitored circuits in actual experiments. While our understanding of measurement-induced criticality has increased substantially over the last couple of years, a variety of open questions still remain. For example, the exact nature of the critical point in realistic limits remains open, despite recent progress [77]. It has also been shown that it is possible to stabilize phases of matter using specific measurement protocols [26,27,94], which would otherwise be unstable in thermal equilibrium. However, it is not yet clear what restrictions, if any, apply to the phases realizable in this way. Similar protection against equilibration can be afforded by many-body localization [176], but this is not possible in the presence of non-Abelian symmetries [177], for example, so it would be interesting if monitored quantum circuits could provide a route to avoiding these restrictions. Finally, it would be interesting to see if the quantum error-correcting properties of the volume-law phase, which have provided a useful lens on the phenomenology [37-39, 60, 178], could be put to practical use in quantum computers. While the hybrid dynamics encode quantum information, and a decoder is known to exist in the volume-law phase [60], it is not clear whether in general a 'good' decoder exists which could efficiently detect and correct errors [61].
Regarding random circuits on NISQ devices, we have provided a brief introduction to the ideas of random-circuit sampling and cross-entropy benchmarking to achieve a quantum computational advantage. Furthermore, we have focused on a recently proposed random-circuit based algorithm to simulate hydrodynamics on NISQ devices [117], which emphasizes that random circuits are not just abstract tools to outperform classical computers for a specific computational problem, but are relevant also for a wider range of applications. In this context, we have demonstrated that random circuits can efficiently generate random and highly entangled quantum states. Importantly, we have explained that such random states are immediately useful for simulations, both on quantum and classical computers, by leveraging the concept of of quantum typicality. Exploring in more detail the potential applications of random quantum states and quantum typicality on NISQ devices will be an interesting direction of future research. Such applications are particularly appealing from a complexity point of view as random states can be prepared on NISQ devices by random circuits of moderate depth. However, due to their high entanglement, they are usually not amenable to concepts such as matrix-product states, which makes classical representations very costly. Applications of random states thus fall naturally into a category that is classically hard, but might be accessible by NISQ devices. Let us note that quantum typicality has in fact been recently exploited in experiments on actual quantum hardware. In [133], a scheme very similar to that outlined in Sec. III B was used to calculate dynamical spin-spin correlation functions in a driven Floquet spin chain in order to verify the occurrence of discrete time-crystalline eigenstate order. Moreover, in [179], quantum typicality was used to evaluate thermodynamic expectation values at finite temperature (cf. Box 2), which involved the approximation of the imaginary time-evolution of random states on a NISQ device [180].