Quantum complexity and localization in random quantum circuits
Himanshu Sahu Aranya Bhattacharya Pingal Pratyush Nath

	
	
	himanshu.sahu@uwaterloo.ca
  Department of Physics and Astronomy and Institute for Quantum Computing,University of Waterloo, Ontario N2L 3G1, Canada.
  Perimeter Institute for Theoretical Physics, Waterloo, ON, N2L 2Y5, Canada.
 Department of Physics and Department of Instrumentation & Applied Physics, Indian Institute of Sciences, C.V. Raman Avenue, Bangalore 560012, India.
 
	aranya.bhattacharya@uj.edu.pl
	Institute of Physics, Jagiellonian University, Lojasiewicza 11, 30-348 Kraków, Poland. 

pingalnath@iisc.ac.in
	Centre for High Energy Physics, Indian Institute of Science, C.V. Raman Avenue, Bangalore 560012, India. 
	
	
	
	§ ABSTRACT 
		Quantum complexity has emerged as a central concept in diverse areas of physics, ranging from quantum computing to the theory of black holes. We perform a systematic study of complexity in random quantum circuits with and without measurements. We observe that complexity grows linearly before saturating to a constant value. For N qubits without measurements, the saturation value scales as 2^N-1, and  the saturation time scales as 2^N. This behaviour remains identical in the presence of random measurements with different probabilities, indicating that this notion of complexity is insensitive to the rate of measurement. We also study the behaviour of complexity in two variants of the random unitary floquet circuit, where we observe that complexity acts as a novel probe of Anderson localization and many-body localization. 
	
	
	Quantum complexity and localization in random quantum circuits
    Pingal Pratyush Nath^0000-0001-5311-7729
    September 9, 2024
==============================================================




 
Introduction.— Understanding the complexity of quantum states and operators is relevant to a wide range of settings, from quantum many-body physics through quantum gravity to quantum computation <cit.>. In many-body physics, insights into the buildup of complexity in the time evolution of an initial local observable, known as operator growth, have inspired new ways of probing the dynamics of thermalization <cit.>. 
Out-of-time-order correlators (OTOCs) <cit.>, a quantitative tool for measuring operator growth, obeys a dynamical bound arising from unitarity and analyticity <cit.>. It is shown that in a version of quantum gravity known as anti-de-Sitter space/conformal field theory (AdS/CFT) duality, the  black holes saturate this bound <cit.>. Similar to black holes, OTOCs saturates the bound in models such as the so-called Sachdev-Ye-Kitaev (SYK) model which has given rise to holographic dual description with black holes <cit.>.  

In quantum computing, the complexity of pure states is defined as the size of the smallest circuit that produces the state from a product state, while the complexity of a unitary  is defined as the smallest circuit that approximates the unitary. This notion of quantum circuit complexity has recently gained interest due to connections between gate complexity and holography in AdS/CFT correspondance <cit.>. It is conjectured that in the bulk theory, the wormhole's volume is dual to the boundary state's quantum complexity, whose growth has been proved for the random unitary circuits <cit.>.

Recently, the notion of state and operator complexity based on Krylov basis (which is referred to as `quantum complexity' for convenience) defined using the generator of evolution operator has been extensively studied as a probe of information scrambling <cit.>. Operator complexity (known as Krylov complexity) is conjectured to grow at most exponentially in nonintegrable systems and can be used to extract the Lyapunov exponent, therefore, establishing a connection with OTOCs <cit.>. On the other hand state complexity (known as spread complexity), a generalization of Krylov complexity for quantums states, is used as a probe to study quantum choas and topological phase transitions <cit.>. Furthermore, since by construction this notion of complexity measures the delocalization of a wave function in the Krylov basis with time, it also captures the localization of the wavefunction by suppresion in the complexity saturation value <cit.>.

Despite a number of investigations in varying quantum systems, how the quantum complexity in systems with discrete-time evolution behaves remains an open question. In this Letter, we study quantum complexity in various classes of random quantum circuits. Quantum circuits built from local unitary gates (and local measurements) are a new playground for quantum many-body physics and a tractable setting to explore universal collective phenomena far from equilibrium. These models have shed light on longstanding questions about thermalization and chaos, and on the underlying universal dynamics of quantum information and entanglement <cit.>. 

In random unitary circuits (RUCs) that consists of local random Haar unitaries, any quantum state evolves towards increasingly entangled states characterized by an extensive scaling of entanglement entropy with system volume. In presence of measurements that occur repeatedly during the evolution at a fixed rate, the system undergoes a phase transition from volume- and area-law entanglement entropy scaling for infrequent and frequent measurement rates, respectively <cit.>. Another class of random quantum circuits capturing important physical insights are the time-periodic ones, namely Floquet quantum circuits, where each time-step is repeated with the same random instances. In previous studies, classes of Floquet unitary circuit have been shown to exhibit localized phase such as Anderson localization (AL) and many-body localization (MBL) <cit.>.

 
In this Letter, we study the quantum complexity in two classes of quantum circuits — completely random unitary circuits and floquet random unitary circuits (where the random realization of the first timestep is repeated in all further timesteps). In random unitary circuits, the complexity undergoes transition from linear growth at early time to sublinear and saturates at exponential late times in system-size. We find that the complexity profile remains invariant under local measurements. In floquet unitary circuits, we find the suppression of late-time saturation value in localized phases, therefore, can be used as probe for phase transition from thermal to MBL and Anderson localization phases. To this end, our work therefore provides the first ever explicit circuit realization of the Krylov spread complexity, which probes the onset of localizing phases through suppression of complexity saturation value.

Model.— We consider discrete time evolution of two classes of one-dimensional quantum circuit models with N qubits — Random unitary circuits (RUCs) and Floquet unitary circuits (FUCs). For each time step, there is a unitary evolution operator U_t =U(t;t-1), under which a pure state evolves as |ψ(t)⟩ = U_t |ψ(t-1)⟩. The unitary evolution U_t is taken to be local unitary gates which are arranged in a bricklayer pattern:

    U_t    = (∏_x∈odd𝒰_(x,x+1),2t+1)(∏_x∈even𝒰_(x,x+1),2t) 
       = 𝒰^(o)_t ·𝒰^(e)_t

where 𝒰_(x,x+1),τ is the gate on link (x,x+1) at time step τ. In random unitary circuits, the local unitary gates 𝒰_x,t are Haar-random unitary gates. We note that even the minimal brickwork circuit above possesses one basic structure, which is the spatial locality of the interaction, which is natural in quantum information and as toy models for black holes <cit.>. The quantum circuit complexity of such system is shown to grow linearly, before saturating when the number of applied gates reaches threshold that grows exponentially with the number of qubits <cit.>. Furthermore, the scrambling dynamics exhibits similarities to the large-N or semiclassical case, but wavefront broadens diffusively <cit.>. We further introduce nonunitary dynamics by puncturing the unitary circuit with local single-qubit measurements. Measurements are done on a fraction p of all sites. Under the measurement, the wave function transforms as

    |ψ⟩→M_α |ψ⟩/‖ M_α|ψ⟩‖

where {M_α}  are a set of linear generalized measurement operators satisfying ∑_α M^†_α M_α = 1. Under such a measurement, the process described by Eq. (<ref>) is probabilistic, with outcome α happening with probability p_α = ⟨ψ |M^†_α M_α |ψ⟩. In our study, we will choose these generalized measurement operators to be mutually orthogonal projectors, that is M_α→ P_α, with P_± = (1± Z)/2 measuring the Z component of the spin of individual qubits. Such projectors satisfy P_α P_β = δ_αβ P_α and ∑_α P_α = 1. This model undergoes a phase transition at a finite value of p=p_C from volume- and  area-law entanglement <cit.>.



In Floquet unitary circuits, the evolution is made time-periodic U_t = U_t+1, I.e., the two layers are repeated identically in the spirit of Floquet evolution. We consider several variations of Floquet evolution with a unitary circuit, which was previously shown to exhibit localized phases <cit.>. The scenarios we consider are the following: 

(A) Gaussian circuits: We consider N fermionic pairs (a_i,a_i^†) satisfying {a_i,a^†_j} = δ_ij. We begin by defining a set of Hermitian fermionic operators given by

    q_i = 1/√(2) (a^†_i + a_i )     and     p_i = i/√(2) (a^†_i - a_i )

referred to as Majorana modes. Turning to the covariance matrix Ω, if we choose the Majorana basis ξ^a ≡ (q_1,p_1,q_2,p_2… q_N,p_N), 

    Ω^ab = -i Tr(ρ [ξ^a,ξ^b]) .


The covariance matrix provides a straightforward framework for discussing the corresponding group of unitary transformations for fermionic Gaussian states. In this context, we focus on Gaussian circuits that map Gaussian states to Gaussian states. The most general unitary operation acting on the covariance matrix is represented by an orthogonal transformation O∈ O(2N). We specifically consider a subclass of these unitary transformations, generated by quadratic Hamiltonians, which correspond to special orthogonal transformations O ∈SO(2N)
 <cit.>.




With this, the time evolution operator is given by an orthogonal transformation O∈O(2N) built of random two-site operations P_i, Q_i ∈O(4),

    U_t = G(⊕_i=1^N/2 Q_i) G^T (⊕_i=1^N/2 P_i)

where 

    G  = [   0         1_2; 1_2   0        ;   0   ⋱   ⋱    ;         1_2   0 ]

takes care of circularly shifting ⊕ Q_i by one site, and ensures periodic boundary condition. Given the block diagonal form of the evolution operator, the two-site operations P_i are coupling between sites 2i-1 and 2i. The time average of covariance matrix can be used to assess long-time behavior of a typical state. It is shown that the inhomogeneous evolution exhibits Anderson localization; an initially localized impurity stays localized. On the otherhand, the homogeneous evolution results in thermalization <cit.>.

(B) Spins: The spin system that we consider is periodic version of random unitary circuit, where local unitary gates 𝒰 are drawn from different probability distributions with the  common property of single-site Haar invariance. In other words, any transformation of a 𝒰 of the form 

    𝒰↔ (w_1⊗ w_2) ·𝒰·  (w_3⊗ w_4)

does not affect averages ⟨⋯⟩, for arbitrary choice of single-qubit operator w_i.








Method.— Consider the evolution of initial state |ψ(0)⟩ 

under discrete-time dependent unitary evolution such that |ψ(t)⟩  = U_t |ψ(t-1)⟩, where t = 1,2,… We define the Krylov basis by choosing |K_0⟩ = |ψ(0)⟩ and then recursively orthogonalizing each |ψ(t)⟩ with all the |K_i⟩ for i < t <cit.>. At any t, we can expand the state |ψ(t)⟩ in Krylov basis as
 
    |ψ(t) ⟩ = ∑_n=0^Dϕ_n(t) |K_n⟩ ,

 where D is dimension of Hilbert space, and ϕ_n(t) = ⟨ K_n|ψ(t)⟩. We define the spread complexity of the state as the average position of the distribution on the ordered Krylov basis:

    𝒞(t) = ∑_n=0^D n|ϕ_n(t)|^2  .





Analogously, we can define the Krylov complexity (K-complexity) of the operator, which evolves under discrete-time evolution O_t = U^†_t O_t-1 U_t. As before, the Krylov basis is obtained by choosing |K_0)  = O_o and then recursively orthogonalizing each O_t with all the |K_i) for i<t. At any t, we can expand the operator O_t in Krylov basis as 

    O_t = ∑_n=0^D^2φ_n(t) |K_n)

where φ_n(t) = (K_n|O_t). We define the K-complexity as 

    𝒦(t) = ∑_n=0^D^2 n |φ_n(t)|^2 .




















Results.— We start by considering the complexity of the random unitary circuits. In this case, the complexity profile consists of early time growth followed by saturation at exponentially late times. At early times, complexity growth is linear, which later transitions to sub-linear growth and reaches saturation depending on the size of the chain. The initial linear growth is tied to fast relaxation associated with linear light-cone <cit.>. 

At late times, the complexity saturates to half the Krylov dimension i.e.. D/2, which is generic in many-body chaotic systems and quantum circuit complexity. Figure <ref> shows the spread complexity for the system-sizes N=8,9,10, where the local unitaries are sampled from random-haar ensemble. Unless otherwise mentioned, we will perform the average over the large number of sample RUCs so that quantities are well-converged. In numerical calculations, the initial state is a product state |ψ(0)⟩ = |↑↓↑↓…⟩. However, taking any other states produces the same feature in the complexity profile, suggesting that it is independent of the initial state.

In monitored RUCs, the Krylov basis constructed from orthogonalization of span of vectors 

    𝔎_1 = {|ψ(0)⟩, M𝒰^(o)_1 M 𝒰^(e)_1 |ψ(0)⟩,…}

where M represents measurement operation performed at probability rate p. In Fig.  <ref>, the averaged spread complexity (the averaging is done over both randomized measurements and the choice of unitaries) behaves exactly similarly to the case without measurements, independent of probability rate p. 

Interestingly, the spread of complexity does not appear to affect the system undergoing a measurement-induced phase transition. In other words, the system's complexity grows independently in two distinct phases, each characterized by volume-law and area-law entanglement entropy.This indicates that complexity defined in this way is completely independent of the notion of entanglement, since it is defined on all the degrees of freedom of the system whereas entanglement measures how the correlation between two complementary parts of the systems change.






We now move to two classes of Floquet unitary circuits, namely Gaussian circuits and spins. 






(A) Gaussian circuits.— In Fig. <ref>, we show the spread complexity associated with inhomogenous and homogenous settings. In homogenous case where the time evolution O is 2-site-translation invariant, randomness is the same for all sites P_i = P_j and Q_i = Q_j. We find that the spread of complexity exhibits a lower value of late-time saturation in the inhomogeneous case compared to the homogeneous case, which is reminiscent of Anderson localization. The suppression value 𝒞_∞ takes up a constant in thermodynamics limit N→∞.


(B) Spins.— To begin with we consider the local unitary gates 𝒰 to be drawn from random Haar. In Fig. <ref>, we present numerical results for the spread complexity. The complexity profile remains similar to a random unitary case, except it features a peak before  saturating.

The local unitary 𝒰 drawn from random Haar are highly entangling operators, therefore, move information that is initial localized in one site across the chain. On the other hand, MBL can typically requires strong random potential relative to the coupling <cit.>. To witness the MBL <cit.>, we cast every unitary in 𝒰(4) as


    (u_1⊗ u_2) e^iaσ_x⊗σ_x + ib σ_y⊗σ_y + ic σ_z ⊗σ_z (u_3⊗ u_4)

where u_i∈U(2) and coefficients a,b,c∈ℝ. The probability distribution for all two-qubit operators 𝒰∈U(4) composing the time evolution operator is defined by Eq. <ref>, drawing each u_i from the Haar measure for U(2) and a,b,c uniformly from the interval [-h,h]. 





In Fig. <ref> we show numerics for 𝒞(t) for distributions with various coupling strengths h. We find a crossover from thermalization for large coupling and localization for small coupling as evident from late-time saturation value 𝒞_∞. The MBL transition can be extracted from 𝒞_∞ as a function of h. In Fig. <ref>, the transition occurs at value h_0 ≈ 0.3 independent of system-size which matches with previous studies <cit.>. 












































Discussion.— In this Letter, we study the state complexity in various classes of random unitary circuits. We show that the complexity undergoes a transition from linear to sublinear growth in random Haar unitaries, before saturating which scale exponentially with the number of qubits. Interestingly, the exponential scaling of saturation time is also found in quantum circuit complexity, indicating the possible connection between the two complexities <cit.>. In the monitored case, the quantum complexity profile remains invariant under measurement rate p. In Floquet unitary classes, we probe thermal and local phases using late time saturation of complexity. More specifically, inhomogenous Gaussian circuits exhibit Anderson localization while strongly coupled spins show many-body localization. The operator complexity can equally be studied and be used to probe thermal and local phases. Similar to the state complexity, the operator complexity is expected to undergo linear to sublinear transition, before it saturates at exponentially large times t_sat∼ 4^N to a value which grows exponentially with system size ∼ 4^N/2. 


In summary, we discuss in this letter 

    
  * How Krylov spread complexity can be defined for discrete time-dependent random circuits.
    
  * How the complexity profile, saturation values, and the saturation times scale with system size, indicating a connection with the circuit complexity.
    
  * In floquet setups, how this notion of complexity in the Krylov basis, generated by the unitaries in the discrete-time picture acts as a novel probe of various kinds of localization (Anderson and MBL) through suppression of the saturation value. This notion of complexity therefore still measures the delocalization of the wave function in the state Hilbert space. 

There are a number of questions that remain to be answered in future works. A pressing one is if its possible to probe scrambling transition in the monitored RUCs using quantum complexity. The definition of complexity allows it to grow even in the absence of any growth in entanglement. For example, a discrete evolution in which a product state evolves to another product state results in the growth of  complexity but not entanglement. A possible way could be to consider radiative random unitary circuits <cit.>, which were previously shown to exhibit scrambling transition probed using OTOCs. Additionally, it should be noted that the measurement process as defined in Eq. (<ref>), renormalizes the state, thereby, killing the non-unitary effects. To reattain the non-unitarity, one can either remove the normalization or study evolution with respect to the effective Hamiltonian derived from the non-unitary evolution operator.


Acknowledgement.— We would like to thank Sumilan Banerjee, Mario Flory, Shane Kelly, Subroto Mukherjee, and Zahra Raissi for useful discussions. The work of A.B. is supported by the Polish National Science Centre (NCN) grant 2021/42/E/ST2/00234. A.B. would like to thank International Centre for Theoretical Sciences, Bengaluru, and, the organizers of the program “Quantum Information, Quantum Field Theory, and Gravity" for the hospitality when this work was in the final stage. 



	apsrev4-2
	 
	
