Holographic Interpretation of Relative State Complexity
Alexander Yosifov Aditya Iyer Lachezar Filipov
hep-th
 
Ultrafast strain-induced charge transport in semiconductor superlattices
    F. Wang^1,2, C.L. Poyser^2, M.T. Greenaway^1, A.V. Akimov^2, R.P. Campion^2, A.J. Kent^2, T.M. Fromhold^2, and A.G. Balanov^1
    December 30, 2023
=================================================================================================================================





§ INTRODUCTION


The AdS/CFT correspondence relates a d-dimensional boundary conformal field theory (CFT) to a bulk gravity theory in (d+1)-dimensional asymptotically Anti-de Sitter (AdS) spacetime. The existing bulk/boundary dictionary points to a deep relation between the concepts of quantum complexity, quantum information, chaos, and gravity – all of which interplay in black holes.

Quantum complexity (herein referred to as complexity) is usually defined in the literature as the minimum number of gates required to prepare a quantum state, assuming a universal gate set { g_i}. Holographic complexity has been shown to admit two dualities, known as "complexity=volume" (CV-duality) and (ii) "complexity=action" (CA-duality). The CV-duality <cit.> dictates the evolution of complexity of a boundary CFT is gravitationally dual to the linear growth of the black hole interior,[We should note that, classically, the interior black hole volume continues to grow indefinitely, see Christodoulou-Rovelli <cit.>.] while the CA-duality <cit.> associates a family of weakly-coupled bulk degrees of freedom in the Wheeler-DeWitt (WDW) patch to the quantum state of the boundary CFT.[Using the classical action associated with the WDW patch in AdS spacetimes eliminates the ambiguities related to the size of the horizon relative to the AdS radius.]

Similarly important concept which we will focus on in this paper is relative state complexity, roughly defined as the minimum number of gates required to prepare a target state |ψ⟩ from a simpler reference state |ψ_0⟩, assuming a universal gate set { g_i}. Usually, for a two-sided AdS black hole the reference state is the thermofield-double (TFD) state, while for a one-sided AdS black hole it is the ground state. In fact, as we will assume throughout the paper for the case of a one-sided AdS black hole, the target state will simply be the time-evolved reference state |ψ⟩=U|ψ_0⟩, where U denotes a unitary transformation.[Note that the entropic behavior of complexity <cit.> suggests the relative state complexity for any |ψ⟩ and |ψ'⟩ increases linearly in time and with the number of degrees of freedom.] Understandably, a lot of effort has been devoted <cit.> in the direction of investigating the evolution of complexity and relative state complexity from the perspective of geometry for which we have a richer toolbox.

Quantum chaos in strongly-coupled quantum systems of many degrees of freedom plays an important role in terms of information processing and strong thermalization which, on the other hand, can help us better understand quantum gravity. The semiclassical black hole structure, however, makes examining the interior highly non-trivial. Although different measures such as out-of-time-order correlators (OTOC) <cit.> and random matrix theory (RMT) <cit.> exist, more recently, the incorporation of quantum information-theoretic tools in holography together with the established protocol for assigning computational costs to trajectories on the unitary manifold <cit.> have opened the possibility of probing the highly chaotic black hole interior from a new angle. Despite those advancements, however, we have a long way to go as we still do not fully understand what the CFT can teach us about the interior region. It would thus be useful to learn, for instance, how the fast scrambling of infalling matter is encoded in the CFT, and for that a more intuitive way of studying quantum chaos is needed. Given the widely adopted qubit description, the study of complexity and chaos in black holes has benefited tremendously lately from the (examined in Section <ref>) geometric approach of Nielsen et al. <cit.>.

Following the recent progress, in an attempt to extend the bulk/boundary dictionary and shed light onto the elusive nature of quantum chaos in strongly-coupled quantum systems, our goal in this paper is to propose, within AdS/CFT, a holographic interpretation of relative state complexity as a decoding task in the bulk, and demonstrate how it can be used as a novel measure of quantum chaos.[Similar proposals, relating quantum chaos and circuit complexity, have been recently explored <cit.>. Although there are technical differences in the approaches, all models agree that circuit complexity can be utilized as a new diagnostic of quantum chaos.] More precisely, employing Nielsen's complexity geometry framework, we investigate the evolution of relative state complexity of a small auxiliary system of M weakly interacting degrees of freedom coupled to a large-N CFT in a high-energy pure state, gravitationally dual to one-sided AdS black hole. We suggest the relative state complexity of the auxiliary system (i) holographically corresponds to the minimal depth of the quantum circuit necessary to decode its gravitational dual, and (ii) can furthermore be studied to derive the chaotic properties of the dual one-sided AdS black hole. In light of this, for the case of an evaporating black hole <cit.>, and in agreement with the conclusions reached by Kim-Tang-Preskill <cit.>, the quantum state of the emitted Hawking radiation is suggested to be pseudorandom, meaning an outside observer with limited computational resources (i.e. using a polynomial-size quantum circuit) will not be able to decode it and thus distinguish it from a maximally mixed state. The supposed pseudorandomness of the Hawking radiation highlights the computational limitations of exterior observers in regard to decoding information processed by quantum chaotic systems and is reminiscent of the Harlow-Hayden computational cost argument <cit.> in the context of decoding subfactors of the Hilbert space of the Hawking cloud in the firewall proposal.

Throughout the paper we will assume the idealized scenario in which the CFT evolution is described by a random quantum circuit[Random quantum circuits have been shown to be fast scramblers and thermalize quantum information in time logarithmic in the entropy <cit.>.] acting on a large but finite N.[Throughout the paper we will work under the assumption that a black hole (holographically dual to a strongly-coupled large-N CFT) is represented as a collection of N qubits, where S_BH=A/4G_Nħ=N.] Moreover, we will assume the random quantum circuit has a discrete time-step evolution Δτ, dictated by a universal gate set of two-local gates.[For similar setup, see <cit.>. Note that for a time interval Δ t ∈ [0,t], where Δ t ≫Δτ we can divide Δ t into j steps, where each is of order Δτ.] 



§ COMPLEXITY AND CHAOS


In this Section we examine how complexity and chaos develop in large-N random quantum circuits within AdS/CFT. We then put forward, employing Nielsen's approach, a geometrical interpretation of complexity and chaos, where the computational cost is given in terms of "distance" on a unitary manifold <cit.>.
Later, we demonstrate the same geometrical interpretation naturally
arises in the large-N limit of the Sachdev-Ye-Kitaev (SYK) model.



 §.§ Complexity


Complexity has quasi-periodic behavior. For a generic large-N quantum system whose dynamics is dictated by a random quantum circuit, complexity is low for small t. Then, for t∼ t_*, due to the early chaotic dynamics, and bounded from above by the Lloyd's bound (<ref>), complexity grows exponentially, where for a system of N degrees of freedom at temperature T


    𝒞_*=Nlog N

Although the scrambling complexity is nowhere near the upper bound 𝒞_*≪𝒞_max, it is still substantial for N≫ 1. Having e^λ_L(t-t_*)∼𝒪(1), where λ_L is the Lyapunov exponent (<ref>), at the scrambling time indicates the presence of chaos in the holographic CFT.

Later, for t>t_*, the exponential growth of complexity is saturated. After the scrambling time, it continues to increase but now linearly in the number of degrees of freedom (<ref>)


    d𝒞/dt∼ NT

where both early- and late-time growth (<ref>) and (<ref>), respectively, are restricted by the Lloyd's bound <cit.> [Being the fastest scramblers and the most chaotic objects in nature, black holes saturate the Lloyd's bound.]


    d𝒞/dt≤2M/πħ

The liner growth continues for t_cr∼ e^N (classical recurrence time) at which point the upper bound is reached


    𝒞_max=poly(N)e^N

Complexity then remains at its maximum value for a quantum recurrence time t_qr∼ e^e^N (doubly exponential in the entropy) and then begins to decrease.

The sharp transition in the dynamics at the scrambling time is well-motivated on both sides of the duality. In particular, if this exponential growth is saturated before the scrambling time, then this would indicate some yet unknown interior dynamics for AdS black holes which allows for faster information processing. On the other hand, exponential growth of complexity beyond the scrambling time would violate (<ref>), see Refs. <cit.>.

Apparently, the scrambling time is of particular interest when studying large-N chaotic systems. It is generally given as


    t_*=β/2πlog N

where β≡ T^-1 is the inverse temperature. Having a two-local universal gate set, we can define the scrambling time as the time for a reduced density matrix to become approximately
thermal <cit.>. Another definition, suitable for
strongly-coupled large-N theories (dual to AdS black holes), is
the time for all degrees of freedom to indirectly interact. From the bulk/boundary equality of the Hilbert spaces, we see the
scrambling time is of particular importance for both AdS black holes, and high-temperature boundary CFTs since it indicates the presence of chaos.



  §.§.§ Complexity=Action


In <cit.> Susskind et al. suggested the complexity
of a CFT, living on the boundary of an asymptotically AdS spacetime, is dual to the action of a WDW patch in the bulk. The WDW patch is
defined as the union of the past and future light cones of a spacelike hypersurface, anchored at some boundary time. One can also think of it as the region spanned by the union of all spacelike hypersurfaces (i.e. slices) anchored at some boundary time. In its most general form the CA-duality reads 


    𝒞=I_WDW/πħ

where the boundary complexity is dual to the action of the
entire WDW region which extends deep within the AdS black hole
interior. Usually, the bulk I_WDW contains an Einstein-Hilbert
action, and a York-Gibbons-Hawking boundary term.

The CA-duality is equally well-defined for both, one- and two-sided
AdS black holes. Suppose we have a CFT dual to a one-sided black hole
in the bulk, and pick an arbitrary boundary time t. The state of
the corresponding patch would be


    |ψ(t)⟩ =e^-iHt|CFT⟩

where H is a local Hamiltonian.

Eq. (<ref>) can be straightforwardly extended for the case of two entangled copies of a boundary CFT, dual to an eternal two-sided AdS black hole. In particular, picking t_L and t_R for the left and right AdS boundary, respectively, yields


    |ψ(t_L,t_R)⟩ =e^-i(H_Lt_L+H_Rt_R)|TFD(,)⟩

where the TFD state is given as


    |TFD(,)⟩≡1/√(Z)∑_ne^-β E_n/2|n_L⟩⊗|n_R⟩

here, |n_L,R⟩ denotes the energy eigenstates,
and β is the inverse temperature. 

Thus the conjectured CA-duality (<ref>) suggests 

    𝒞(|ψ(t_L,t_R)⟩)=I_WDW/πħ




  §.§.§ Complexity=Volume


Initially proposed in <cit.> the CV-duality[Interestingly, the CA-duality can successfully reproduce the CV-duality without the need of adding any parameters by hand.] relates the complexity of a boundary CFT to the volume of a maximally-extended spacelike hypersurface behind the horizon 


    𝒞=V/G_Nl_AdS

where l_AdS is the AdS radius.

Behind the horizon the volume of the hypersurface has been shown to
grow linearly like


    V∼ ST

where S and T are the entropy and the temperature of the black
hole, respectively.

As it was pointed out in <cit.>, however, the
CV-duality lacks the universality of the CA-duality since it requires
hand-put length scale. In particular, the relation (<ref>) is only valid
assuming the black hole is large compared to l_AdS. Otherwise,
for black holes smaller than l_AdS, (<ref>) reads


    𝒞=V/G_Nr_+

where r_+ is the horizon radius.

Note that r_+ depends on the mass of the black hole, and thus
has to be put ad hoc. Therefore, the CA-duality is considered more
universal, and can easily reproduce the CV relation.



 §.§ Chaos


Chaos quantifies the sensitivity of a system to changes in the initial
conditions. The chaotic behavior of a strongly-coupled large-N
CFT manifests in the AdS bulk as fast scrambling (<ref>). A commonly used
way to probe chaos involves the use of out-of-time-order correlators, where for a strongly-coupled large-N quantum
system at some fixed temperature β 


    ⟨ W(t)V(0)W(t)V(0)⟩ _β e^λ_Lt

Here, λ_L is the Lyapunov exponent which is bounded from
above as 


    λ_L≤2π/β

W and V are simple Hermitian operators, where


    W(t)≡ e^iHtWe^-iHt

and H is a local Hamiltonian.

At the scrambling time, due to chaos, the out-of-time-order correlator
(<ref>), up to a constant, decays exponentially <cit.>


    ⟨ W(t)V(0)W(t)V(0)⟩ _β=e^λ_L(t-t_*)+𝒪(N^-2)

Thus, for t>t_*, regardless of V and W, the correlator takes the following form


    ⟨ VV⟩⟨ WW⟩

This exponential decay is related to the rapid initial growth of the
commutator, which becomes highly non-trivial at the scrambling time.
For t≪ t_* the commutator is suppressed by the large-N term,
and it is both small, and approximately constant.

Notice that for chaotic quantum systems the behavior of the commutator
at early times is similar to that of complexity; namely, both quantities are initially low (and approximately constant for t≪ t_*), and later on undergo exponential growth, saturated at the scrambling time <cit.>.[The authors of <cit.> propose a new diagnostic for quantum chaos, where by tuning the interaction Hamiltonian, a timescale, associated with the transition between classical and chaotic dynamics, is derived.]

The growth of the commutator is illustrative of the growth of complexity of W(t). As we later argue in the paper, one way to probe quantum chaos of a large-N CFT would be to introduce a small auxiliary system, correlate it with the initial CFT, and examine the evolution of its relative state complexity.  



§ GEOMETRIC INTERPRETATION





 §.§ Complexity & Chaos


Following Nielsen et al. <cit.>, we now put forward a geometrical interpretation of complexity and chaos to illustrate their relation to gravity. Here, complexity is interpreted as "distance" on a unitary manifold. In this language, "distance" essentially means computational cost. Note that due to the assumed bulk/boundary Hilbert space equality, distances have to be preserved across the duality. With that in mind, the geometric approach will later be used to study the gravitational dual of relative state complexity of a small weakly-interacting auxiliary quantum system entangled to a large-N CFT.

Usually, the Fubini-Study metric <cit.> with its distance bound of


    d∈[0,π/2]

suffices when talking about quantum states orthogonality. One issue,
however, concerns the ease of saturating the bound. For the purpose
of studying complexity, the Fubini-Study metric cannot adequately describe its exponential upper bound, and thus has to be substituted.
 
That is why for studying complexity we employ a non-standard 2^N-dimensional unitary manifold U(2^N). Here, a time-evolving quantum state defines a trajectory s on the manifold, whose length naturally increases with time, corresponding to the state's increasing complexity. Similarly, for a pair of quantum states |ψ⟩ and |ψ'⟩, where |ψ⟩ ,|ψ'⟩∈ U(2^N),
each state defines its own trajectory on the manifold, where the distance between them linearly increases, and it is the geometrical analog of their increasing relative state complexity <cit.>. Moreover, the unitary manifold has intrinsic penalty factors which restrict quantum states from exploring more complex paths. Note that they are independent of the metric as a whole but rather depend on particular directions. Simple paths have 𝒪(1) penalties, while the more complex paths are exponentially suppressed by e^N penalties. Obviously, the penalty factors are important because (i) they are related to the minimum possible complexity increase, associated with acting with a simple two-local gate (which geometrically can be interpreted as minimizing the geodesic length in the bulk), (ii) they define the local coordinates on the gravity side, and (iii) they define a natural notion of locality.

Similar to the SYK model examined below, a generic object of interest in this framework is the evolution operator


    U(t)≡ e^-iHt

whose symmetry transforms as U(s)=e^-i∑_jθ_j(s)T_j, where T_j is as defined in Section <ref>.

In a geometrical context, (<ref>) formally reads


    U(s)=𝒫exp(i∫^sds H(s))

where 𝒫 is a path-ordering operator and H(s) is a local Hamiltonian which parameterizes a path s on the unitary manifold


    H(s)=Y^j(s)𝒢_i

where Y^j(s) denotes the set of penalty factors which, when applied at every step (i.e. point) along the geodesic, control its path, and 𝒢_i≡{ g_i} is a universal gate set. Proper choice of {Y^j} ensures the computational task at hand is optimized. Geometrically, this translates to minimizing[It was demonstrated in <cit.> that the geodesic remains locally minimal for at least exponential time.] the local geodesic on U(2^N).

Working in a unitary manifold, the complexity of U(t) is e^N, which is to say that U(t) (here described as a point on U(2^N)) can explore an e^N-dimensional state space. More precisely, we focus on the increase of complexity associated with applying U(t) to an arbitrary pure quantum state |ψ⟩∈ U(2^N). Note that when we time-evolve a quantum state


    e^-iHt|ψ⟩

the corresponding complexity growth is independent of |ψ⟩. Rather, the complexification is solely determined by the local Hamiltonian. Essentially, a time-evolving quantum state behaves like a non-relativistic particle moving across the unitary manifold. Where for a strongly-coupled large-N system, due to the early chaotic dynamics for t∼ t_* when the Lyapunov exponent is 𝒪(1), the distance traveled (i.e. increase of complexity) is exponential


    d(t)=e^2λ_Lt_*

where at late times t>t_* it saturates to an evolution linear in N


    d(t)=Nt

Evidently, the growth of the distance, traveled by a time-evolving
quantum state on the unitary manifold, is (i) exponential for t∼ t_*, (ii) linear in N for t>t_* until t∼ t_cr, and (iii) a function of the local Hamiltonian


    𝒞(e^-iHt|ψ⟩)≡∫ F(H(t))dt

Given the discrete time-step evolution of the random quantum circuit, when describing the trajectory s, spanned by the quantum state on U(2^N), we need to specify how the local Hamiltonian acts at each time step Δτ. For that purpose we define an instantaneous Hamiltonian H, i.e. a Hermitian operator which depicts the point-by-point evolution of the trajectory s


    H̃(s) = i dU(s)/ds U^†(s)

Here, an infinitesimal change along s corresponds to a simple unitary operation, i.e. acting with a two-local gate, and reads


    U(s+ds)=e^-iH̃(s)dsU(s)

where geometrically, (<ref>) can be expressed in the Schrodinger picture as, see Fig. <ref>


    i|ϕ(t_1)⟩/ds=H̃(s)|ϕ(t_0)⟩

Despite being different than the classical Hamiltonian H, for the simplest case of an evolution operator U(t) that we consider (<ref>), H=H.[For a detailed description of the instantaneous Hamiltonian, see <cit.>.]

Therefore, a time-evolving quantum state, expressed in terms of the instantaneous Hamiltonian, reads


    H̃( ρ(t) , dρ/dt) = ∑_j[ρ(t),dρ/dt]^j/(j+1)!dρ(t)/dt

where ρ(t) is the density matrix corresponding to the time-evolving state and j denotes the number of time steps each of interval ∼Δτ. Essentially, (<ref>) provides a microscopic step-by-step (i.e. from j to j+1) description of a time-evolving quantum state (<ref>), Fig. <ref>. While geometrically, considering the intrinsic penalty factors of the unitary manifold (<ref>), it corresponds to the "weighted choices" the geodesic makes each time step. That is, at each time step the geodesic evolution, dictated by the instantaneous Hamiltonian (<ref>), (<ref>), (<ref>), and bounded by the penalty factors chooses a computationally economical (i.e. mildly penalized) direction. Moreover, assuming the initial state |ϕ(t_0)⟩ factorizes as


    |ϕ(t_0)⟩=|0⟩⊗…⊗|0⟩_j

and given our choice of penalty factors (<ref>), the instantaneous Hamiltonian can be expressed as <cit.>


    H̃=H̃_1⊗1⊗…⊗1+1⊗H̃_2⊗1⊗…⊗1+…+1⊗…⊗1⊗H̃_j

Therefore, following (<ref>) and (<ref>)-(<ref>), the instantaneous Hamiltonian factorization yields


    ⟨ϕ(s)|H̃(s)|ϕ(s)|=⟩∑_j⟨ϕ_j(s)|H̃_j(s)|ϕ_j(s)|⟩



In light of the proposed in Section <ref> measure of quantum chaos in terms of circuit complexity, and to further illustrate the relation between complexity and geometry, suppose we
have a pair of arbitrarily close (i.e. low relative state complexity) quantum states |ψ⟩ and |ψ'⟩, where |ψ⟩ ,|ψ'⟩∈ U(2^N), see Fig. <ref>. Geometrically, the initial exponential growth of complexity (<ref>) (indicative of chaos) can be interpreted as the rapid divergence of the trajectories of |ψ⟩ and |ψ'⟩. That is, for t∼ t_*, the number of simple steps j between the states grows exponentially. As a result, assuming both states correspond to quantum systems of many degrees of freedom (as will be the case in Section <ref>), the minimum size quantum circuit necessary to time-reverse the evolution of the system back to its initial low-complexity configuration grows immensely. Thus, the distance between the quantum states on U(2^N) increases exponentially (<ref>), and as a result, the relative state complexity between the initially close states is highly non-trivial after only a scrambling time.

Even from this relatively straightforward setup, where an outside observer has access to all the relevant degrees of freedom, one can see that the computational cost of dealing with chaotic large-N quantum systems, whose evolution is dictated by a random quantum circuit, grows quickly. Thus, extracting information from such complex systems for t>t_* is very resource-demanding task. As we demonstrate in Section <ref> for the more physically-relevant case of an AdS black hole entangled with its Hawking radiation in the context of quantifying quantum chaos in terms of circuit complexity, decoding the Hawking particles requires a superpolynomial-size quantum circuit. Meaning, the Hawking radiation is in a pseudorandom quantum state since it cannot be distinguished from a maximally-mixed state by any reasonable computation.

Before proceeding further, let us now briefly sketch an analog of the above argument in terms of particles in phase space ℱ, where similar conclusions regarding the evolution of relative state complexity at late times were derived <cit.>. Here, nearby points x(p,q) and Δ x(p,q) are depicted as quantum states


    |ψ⟩=|p_x(t),q_x(t)⟩
       |ψ'⟩=|p_Δ x(t),q_Δ x(t)⟩

where in |ψ'⟩ both the position q and momentum p are slightly perturbed.

In this context, a generic perturbation which can yield the evolution |ψ⟩→|ψ'⟩, intuitively, reads


    e^iΔ=e^i(pΔ q-qΔ p)

where (<ref>) is a unitary operator which acts as a quantum circuit. Finding the complexity of e^iΔ can thus be used to calculate the relative state complexity between |ψ⟩ and |ψ'⟩. Geometrically, using a Hamiltonian functional similar to (<ref>), the complexity of e^iΔ can naturally be interpreted as the length of the minimum geodesic connecting the two points in ℱ. Notice, however, that for this to be true, the instantaneous Hamiltonian (<ref>), giving the evolution of the Hamiltonian functional at each point along the geodesic, has to be considered for sufficiently small intervals.

Analogously to (<ref>) and (<ref>), time-evolving a quantum state is given as


    |ψ'⟩=e^-iHte^iΔ|ψ⟩

where |ψ'⟩ is perturbed, and its evolution can be expressed as


    |ψ'⟩=|p(t)+Δ p(t),q(t)+Δ q(t)⟩

To summarize, evidently, similar to the above discussion, calculating relative state complexity between particles in ℱ comes down to finding the minimum geodesic distance between their states in ℱ (<ref>) which is achievable given (i) the Hamiltonian evolution is constant and (ii) the instantaneous Hamiltonian (<ref>) is considered for sufficiently small time-intervals as to globally minimize the geodesic, i.e. optimize the computational cost of acting with e^iΔ.

Below we briefly show that the large-N SYK model which is chaotic, holographically dual to d=2 quantum gravity, and describes the evolution of a chaotic Hamiltonian, admits identical late-time growth and geometrical interpretation.



 §.§ Sachdev-Ye-Kitaev



Our goal is to further motivate the complexity and chaos evolution estimates and their geometrical interpretation. For this reason we proceed by very briefly looking at the geometrical approach to complexity in the standard large-N SYK model describing a chaotic Hamiltonian in the Lie algebra formalism.[For a detailed take on this approach, see <cit.> and the references therein.] Consequently, we demonstrate the results in Section (<ref>) can easily be reproduced since the main objects have natural analogs within SYK.

Similar to the holographic case, to have a well-defined geometrical
approach to complexity in the SYK model, we need a basis which yields a notion of locality. We classify the Lie algebra of unitaries into two subgroups, i.e. "easy" and "hard" directions on the unitary manifold. A natural notion of locality is introduced by the simple (i.e. low complexity/computationally economical) generators { T_i} in the Lie algebra, where { T_i}=γ_1γ_2...γ_n, which are analogous to quantum gates in the quantum information-theoretic approach. The Lie algebra generators are k-local, where for simplicity we set k=2, and strictly penalize the (k>2)-local ones. The k=2 restriction simply means no generator can act on more than two gamma matrices at a time. Here, the gamma matrices {γ_i}∼ N which satisfy the Clifford algebra, where {γ_α,γ_β} =2δ_αβ, play the role of qubits. Similar to the discussion above (see Section (<ref>)), locality implies the geodesic can only explore simple paths (i.e. sourced by k=2 generators) on the unitary manifold, thus retaining its local minimum. Likewise, the restrictions on "easy" and "hard" directions are imposed by penalty factors which favor the use of k=2 generators. That way, within SYK, we have a straightforward notion of locality on the unitary manifold which assures the geodesic is locally minimized.

Therefore, considering (<ref>), and assuming a universal two-local set of generators {T_i}, the path of a geodesic on U(2^N) is <cit.>


    U(s)=𝒫exp(-i∫_t_1^t_2ds'V^i(s')T_i)

where V^i denotes the velocity terms. The unitary operator along
the trajectory can thus be given as


    dU/ds=-iV^i(s)T_iU(s)

Here, assuming a given direction is not strictly penalized, the velocity terms dictate the path of the geodesic. This implies that we need to consider the velocities for every value of t, i.e. at each time step. Apparently, the velocities are equivalent to the instantaneous Hamiltonian in the holographic picture. In fact, we can make the relation even more precise and express the instantaneous Hamiltonian (<ref>) in terms
of the velocities in the tangent space as


    H(t)=∑_iv^iT_i

where only 𝒪(1) penalties are considered. This relation
ensures the unitary manifold is well-defined at each point along the
geodesic.

Evidently, the unitary evolution of the geodesic on the unitary manifold is sourced by (i) the velocities which control the path, and (ii) the two-local Lie algebra generators which ensure locality. The relation between geometry and complexity in the SYK model can thus be schematically expressed as <cit.>


    𝒞(e^-iHt)=∫ ds(G_ijV^i(s)V^j(s))^1/2

where G_ij denotes the positive-definite bilinear metric form, and H is the Hamiltonian.

Therefore, considering only the simple generators, the late-time growth of complexity reads <cit.>


    𝒞(t)=(∑_n(E_nt+2π k_n)^2)^1/2

Obviously, the behavior of complexity for a chaotic Hamiltonian in
the large-N SYK model agrees with the holographic framework. Namely, at late times complexity increases linearly for time exponential in the number of degrees of freedom. Geometrically, a quantum state on the 2^N-dimensional state space moves with velocity given by the sum over E_n, and its complexity is related to the distance traveled. 



§ RELATIVE STATE COMPLEXITY & PSEUDORANDOMNESS



In the current Section, using the geometric approach discussed in Section <ref>, we examine a system of large-N CFT in a high-energy pure state (dual to a one-sided AdS black hole) entangled to an auxiliary system of M weekly-interacting degrees of freedom (dual to the Hawking radiation), where both systems are described as products of qubits with Hilbert spaces, respectively, ℋ_N=2^N and ℋ_M=2^M, and we assume N>M.[It should be noted that the dual AdS black hole is "young," meaning it has evaporated much less than half of its initial degrees of freedom.] We study the evolution of complexity of the auxiliary system and argue its relative state complexity with respect to the identity is holographically dual to the minimum depth of the quantum circuit which can efficiently decode the Hawking radiation. We then suggest the growth of the relative state complexity can be utilized as a probe of the chaotic properties of the AdS black hole. Lastly, we argue the inability of any outside observer with reasonable computational resources to decode the Hawking cloud is indicative of its pseudorandom state.

It has been argued that ER=EPR <cit.>, meaning a pair
of CFTs in a nearly maximally-entangled state, living on the conformal AdS boundary, are dual to an eternal two-sided AdS black hole with smooth geometry behind the horizon. As is well known, AdS black holes with radius ∼ l_AdS do not evaporate due to the reflective conditions of the conformal boundary. However, as demonstrated by Raamsdonk <cit.>, weakly coupling a high-energy CFT to an auxiliary system perturbs the boundary conditions, and the dual AdS black hole evaporates, where following <cit.> the time scale associated with the beginning of the evaporation is set by the scrambling time.[The scrambling time is well-motivated even from a purely classical general relativity perspective as it is related to the relaxation time.] This way, black hole degrees of freedom leak to the adiabatically growing auxiliary system M which now contains the radiation.[Note that if the auxiliary CFT is an exact copy of the original CFT, the two boundary theories are initially weakly correlated, and adiabatically evolve toward a TFD state (<ref>).]

We here extend Raamsdonk's argument for the case of a large-N high-energy CFT, entangled to a weakly-interacting
auxiliary system of M degrees of freedom, and address a two-part question: What is the gravitational dual to the relative state complexity of the auxiliary system, and do the results have any implication to information loss/firewalls?

As we show below, on the AdS boundary, the combined system of a large-N CFT and a small-M auxiliary CFT begins in a product state (<ref>). By weakly correlating the two theories (<ref>), the initial product state adiabatically evolves to a TFD state (<ref>). In the bulk, this is dual to a one-sided AdS black hole which at early times is in thermal equilibrium with its environment but then begins to evaporate, and at the Page time becomes maximally entangled with its Hawking radiation. We will now examine the relative state complexity of the auxiliary system with respect to the identity |ϕ(t_0)⟩=𝕀=1, i.e. relative to its value at t=0, where we will focus on the intermediate phase of the evolution while the black hole is still evaporating and the TFD state is not yet reached. Our claim is that this relative state complexity can be interpreted as being dual to an effective low-energy notion of computational cost in the bulk, namely to the minimal depth 𝒟_min of the quantum circuit, required to decode the Hawking quanta; the most efficient way to execute the computation (<ref>) in the form (<ref>). The depth of a quantum circuit gives the complexity-per-qubit measure of the computational task at hand, where in the random quantum circuit model we employ, the depth yields the number of time steps j (or equivalently, the time t) needed to carry out (<ref>). Thus, it effectively quantifies the relative state complexity of a computation. This measure is particularly useful when dealing with quantum systems composed of interacting qubits, especially in the complexity geometry approach.[Using the minimal depth of a quantum circuit as a measure of the computational cost associated with executing a task, e.g. (<ref>), resembles the Hartman-Maldacena tensor networks <cit.>. Tensor networks, like quantum circuits, have width and depth, and their evolution is very similar to that of circuits.]

More precisely, consider the following setup. On the
conformal AdS boundary we begin with a large-N CFT in some high-energy pure state |ψ_0⟩, and introduce a small-M auxiliary system in its vacuum state |0⟩, where N>M and N,M≫ 1. The combined system is initially in a product state


    |⟩ =|ψ_0⟩^⊗ N⊗|0⟩^⊗ M

where |⟩ admits a Hilbert space factorization of the form


    ℋ_total=ℋ_N⊗ℋ_M

where ℋ_N=⊗_i=1^N|ψ_i⟩ and ℋ_M=⊗_i=1^M|ϕ_i⟩. Suppose we now introduce an interaction Hamiltonian which entangles the two CFTs


    H_I=∑_γC^γ_NM𝒪^γ_N𝒪^γ_M

where 𝒪^γ_N and 𝒪^γ_M are locally defined operators which only act on their respective Hilbert spaces, and C^γ_NM denotes a family of coefficients.

The black hole interior N is now purified by the exterior system M (early and late Hawking radiation) and we assume, following AdS/CFT and being agnostic as to the exact mechanism as lies within the realm of quantum gravity, that N is nonlocally encoded in M.[Effectively, the interaction Hamiltonian H_I plays the role of an encoding map H_I:Ñ→ M, where Ñ denotes an interior subregion which, assuming the validity of the equivalence principle, is purified by the late-time Hawking radiation.] That is, degrees of freedom are somehow transferred to the radiation reservoir M <cit.>. Intuitively, this would translate in the bulk to the one-sided AdS black hole starting to evaporate. Due to the transfer of modes, the auxiliary system is perturbed, and is no longer in the vacuum but instead in some typical state |ϕ⟩, whose complexity we denote as 𝒞_ϕ. Moreover, the dimensionality of its Hilbert space ℋ_M monotonically increases, corresponding to the steady growth of the number of degrees of freedom in M.

For small t, the complexity of the auxiliary CFT is low 𝒞_ϕ≪𝒞_max, and due to the weak interactions of its degrees of freedom, grows linearly in M


    d𝒞_ϕ/dt∼ MT

where geometrically, (<ref>) implies the quantum state |ϕ⟩ of the auxiliary system M moves in a particle-like manner across the unitary manifold with the length of the geodesic linearly increasing (<ref>), see Fig. <ref>.

The evolution of the state |ϕ⟩ of the auxiliary system due to the highly non-trivial encoding map which non-locally relates the interior N and exterior M black hole regions, can schematically be given as |ϕ(t_1)⟩=U|ϕ(t_0)⟩, where U is a unitary transformation by a polynomial-size random quantum circuit. That is, 𝒞_ϕ quantifies how much more computationally demanding |ϕ(t_1)⟩ is to decode; how many more steps j it would take. For reasons we make precise below, we suggest this increase of 𝒞_ϕ is reminiscent of the Harlow-Hayden firewall proposal <cit.> and is equally unlikely to be computed.[Harlow-Hayden <cit.> argued that AMPS' conjectured violation of the equivalence principle after Page time is computationally unrealizable for astrophysical black holes since it requires complicated measurements with superpolynomial-size quantum circuits on the emitted Hawking quanta the execution of which would take time exponential in the entropy. That is, no reasonable outside observer can verify that Ñ is purified by a subsystem M.] 


Unlike in <cit.>, however, where Alice's goal was decoding only subfactors of the Hawking radiation in order to verify that early radiation is purified by modes in the black hole atmosphere, here the decoding task concerns applying unitary transformations to the auxiliary system to try to derive its initial state. Naively, calculating the relative state complexity may appear to be an easy task. Alice can simply apply U^† to the perturbed state |ϕ(t_1)⟩ and time-reverse the operation 


    |ϕ(t_0)⟩ =U_1U_2U_3⋯ U_j|ϕ(t_1)⟩

Notice, however, that such an operation – unitary transformation by a polynomial-size random quantum circuit followed by a time-reversal operation, is conceptually similar to the quantum-mechanical measure of chaos, where a pair of identical states are evolved via slightly different Hamiltonians, resulting in exponential decay of their inner products <cit.>. In our case, rather than changing the evolution operator, the slight difference comes from the encoding map. Namely, given the AdS black hole evaporates, in time Δ t, where t_*< Δ t ≪ S^3/2, only a very small number n of thermalized qubits will be transferred to M, where n≪ M. However, since black holes are notoriously good scramblers (fastest and most efficient in nature), and assuming Alice can only manipulate M, we argue those n extra qubits will suffice to render the computation (<ref>) unrealizable in time less than exponential in the black hole entropy. That is, no exterior observer with sub-superpolynomial size quantum circuit at their disposal can efficiently execute (<ref>) and thus derive the initial state. Let's put the complex unitary encoding of Ñ into M aside for a moment. Even under the assumption that M is, to begin with, in a typical pure state ρ_M=|ψ⟩⟨ψ| (chosen uniformly at random), it is still exponentially complicated for ρ_M (considered with respect to a Haar distribution) to be distinguished from a maximally mixed state <cit.>. So to all computationally bounded observers the quantum state of M will continue to appear maximally mixed. We can therefore conjecture that the computational cost of implementing (<ref>); the relative state complexity of |ϕ(t_1)⟩, can be interpreted as being gravitationally dual to <cit.>


    𝒞(ϕ(t_1),ϕ(t_0)) = 𝒟_min∫_t_0^t_1 F(H̃(s)) ds

where H̃(s) is as in (<ref>) given some appropriate (<ref>), and 𝒟_min denotes the minimum depth of the quantum circuit.

Since the auxiliary system M plays the role of a Hawking cloud, we can apply similar analysis as in <cit.> to try to estimate (<ref>) or at least put some constraints. Generally, the computational task Alice faces scales like 2^M for m>0, where m denotes the leaking degrees of freedom to the auxiliary system. She could, of course, take different approaches to try to decode the auxiliary CFT, and hence execute (<ref>) efficiently. For instance, we imagine Alice could manipulate the degrees of freedom of the adiabatically growing auxiliary system, and engineer them into individual sets. She could then apply, in succession or in parallel, unitary transformation to the different sets in any arbitrary order she wishes. As it was demonstrated in <cit.>, however, this procedure of limiting the unitary transformation to any particular group of degrees of freedom is especially complicated. Even more so, given m>0, meaning there is a non-local map encoding Ñ into M, multiple such limiting transformations have to be considered, further complicating the computation. Another decoding approach Alice could take is to make specific gates act on particular groups of degrees of freedom. Or similarly, connect different groups to specific gate subsets, and choose which groups to be acted on and when. Establishing any such connections would obviously require introducing extra degrees of freedom which scale as e^M.

Evidently, even assuming Ñ is encoded in M, meaning there is a unitary non-local transfer of information to the exterior region, because black holes are such efficient scramblers, an outside observer with polynomial-size quantum circuit and access only to M will not be able to read it. That is to say that Ñ is hidden to computationally bounded exterior observers.[We should note, however, that if Alice had access to all the relevant degrees of freedom, e.g. she waits for the black hole to evaporate completely, she would be able to efficiently decode M.] As far as Alice is concerned, performing a quantum computation on M, she will not be able to distinguish Ñ from the maximally mixed state of the thermal bath of radiation M. This implies that for ordinary observers the execution of (<ref>), i.e. calculating the relative state complexity, is computationally unrealizable. Even if we suppose that an n-qubit pure state, where n≪ N is encoded in M, for any reasonable quantum system N which is also a fast scrambler, the probability of Alice distinguishing the n qubits from the maximally mixed radiation with precision (error tolerance) logarithmic in the number of gates of her quantum circuit is ∼ e^-2^n. Thus, for generic M≫ 1, decoding it and reading the extra n qubits is exponentially unlikely. Therefore, this rapid growth of the computational complexity of executing (<ref>) is indicative of the chaotic  black hole dynamics. Said otherwise, quantum computation seems to very well protect the interior spacetime. This robustness of the semiclassical spacetime is usually discussed in the following context. Suppose we have a pair of entangled black holes in the TFD state (<ref>). Alice is outside of her black hole while Bob has already crossed the horizon on his side. For Alice to perturb her CFT and send a high-energy Planckian messages to Bob (create a firewall behind his horizon) would require her to either act with an exponentially complex quantum circuit or apply a highly fine-tuned future precursor operator, thus making the computation unrealizable for astrophysical black holes <cit.>.

The current work may be considered as an extension of <cit.> where we initially studied this new measure of chaos in strongly-coupled quantum systems of many degrees of freedom in terms of circuit complexity. We demonstrated that, due to the chaotic dynamics of the black hole and its causal semiclassical structure, Alice cannot decode the Hawking subsystem faster than time exponential in the entropy. Furthermore, we showed that Alice has two options, she can either act with a maximally complex unitary operator or act with future precursor operators to the perturbed state, and rely on extreme fine-tuning, where both options were argued to be computationally unreasonable for astrophysical black holes formed by sudden collapse. The exponential growth at the scrambling time of the minimum number of time steps j (as defined in (<ref>)) required to implement (<ref>), and thus calculate the relative state complexity, indicates the presence of chaos in N. We showed that by studying the circuit complexity, we can learn about the efficiency of the information processing, and the chaotic dynamics of the black hole interior. Furthermore, by using the circuit complexity as a measure of quantum chaos, we demonstrated that the Hawking radiation is pseudorandom. Namely, assuming there are information-carrying particles among the radiated thermal Hawking quanta, they are scrambled beyond recognition given Alice does not have superpolynomial computational resources, and can only act on M. We have thus made the case that the 2^k+m+r bound proposed by Harlow-Hayden <cit.> holds strong even for young black holes.[The results we derived in <cit.> have since been supported in <cit.>, and more recently in <cit.>. Moreover, in terms of the AMPS' paradox, our work reaffirms the expectations that creating a firewall by an outside observer is notoriously difficult and computationally-demanding task.]




§ CONCLUSIONS


In summary, we examined the case of a small auxiliary system of M degrees of freedom weakly coupled to a large-N high-temperature CFT, whose bulk dual is an evaporating one-sided AdS black hole entangled to the Hawking cloud. We demonstrated that the natural linear increase of the relative state complexity of the auxiliary CFT, (<ref>), with respect to the identity, i.e. between |ϕ(t_0)⟩ and |ϕ(t_1)⟩ could be interpreted as being dual to a low-energy notion of computational cost (decoding task) in the bulk. That is, to the minimal depth of the quantum circuit required to decode the auxiliary CFT, namely to execute (<ref>) in the form (<ref>). In particular, the auxiliary system, playing the role of a Hawking cloud in the bulk, gets harder to decode with time, corresponding to the increasing relative state complexity of its boundary dual. We showed that the inability of any computationally bounded exterior observer to decode the Hawking radiation demonstrates its pseudorandom state, and can further be used as a measure of quantum chaos in terms of circuit complexity.  



§ ACKNOWLEDGEMENT

AY is thankful to the University of Oxford for the hospitality. We would like to acknowledge, in particular, the numerous insightful discussions with Vlatko Vedral. The authors are also grateful to Jinzhao Sun for his help with the figures.  

999
plain

rovelli
Marios Christodoulou and Carlo Rovelli,
"How Big is a Black Hole?"
PRD 91, 064046 (2015).


magan
Pablo Bueno, Javier Magan, and C. Shahbazi,
"Complexity Measures in QFT and Constrained Geometric Actions,"
arXiv:1908.03577 [hep-th] (2019).


evap
Mark Van Raamsdonk,
"Evaporating Firewalls,"
JHEP 11, 038 (2014).


EREPR
Juan Maldacena and Leonard Susskind,
"Cool Horizons for Entangled Black Holes,"
Fortschritte der Physik, 61 (9), 781-811, (2013).


CV2
Josiah Couch, Stefan Eccles, Ted Jacobson, and Phuc Nguyen,
"Holographic Complexity and Volume,"
JHEP 11, 044 (2018).


LS
Leonard Susskind,
"Entanglement is Not Enough,"
arXiv:1411.0690 [hep-th] (2014).


SYK
Juan Maldacena and Douglas Stanford,
"Comments on the Sachdev-Ye-Kitaev Model,"
PRD 94, 106002 (2016).


Pol
Joseph Polchinski and Vladimir Rosenhaus,
"The Spectrum in the Sachdev-Ye-Kitaev Model,"
JHEP 04, 001 (2016).


VB
Vijay Balasubramanian, Matthew DeCross, Arjun Kar, and Onkar Parrikar,
"Quantum Complexity of Time Evolution with Chaotic Hamiltonians,"
JHEP 01, 134 (2020).


TA
Tibra Ali, Arpan Bhattacharyya, S. Shajidul Haque, Eugene Kim, Nathan Moynihan, and Jeff Murugan,
"Chaos and Complexity in Quantum Mechanics,"
PRD 101, 026021 (2020).


CG
Adam Brown and Leonard Susskind,
"The Complexity Geometry of a Single Qubit,"
PRD 100, 046020 (2019).


MN1
Michael Nielsen, Mark Dowling, Mile Gu, and Andrew Doherty,
"Optimal Control, Geometry, and Quantum Computing,"
PRA 73, 062323.


MN2
Mark Dowling and Michael Nielsen,
"The Geometry of Quantum Computation,"
arXiv:quant-ph/0701004 (2007).



MN
Michael Nielsen,
"A Geometric Approach to Quantum Circuit Lower Bounds,"
arXiv:quant-ph/0502070 (2005).


CA2
Adam Brown, Daniel Roberts, Leonard Susskind, Brian Swingle, and Ying Zhao,
"Complexity, Action, and Black Holes,"
PRD 93, 086006 (2016).

CE
Horacio Casini, Marina Huerta, and Robert Myers,
"Towards a Derivation of Holographic Entanglement Entropy,"
JHEP 05, 036 (2011).

bound
Seth Lloyd,
"Ultimate Physical Limits to Computation,"
Nature 406, 1047-1057 (2000).

RN
Richard Nally,
"Stringy Effects and the Role of the Singularity in Holographic Complexity,"
JHEP 09, 094 (2019).

HH1
Daniel Harlow and Patrick Hayden,
"Quantum Computation vs. Firewalls,"
JHEP 06, 085 (2013).

SC
Adam Brown and Leonard Susskind,
"The Second Law of Quantum Complexity,"
PRD 97, 086015 (2018).

CA
Adam Brown, Daniel Roberts, Leonard Susskind, Brian Swingle, and Ying Zhao,
"Complexity Equals Action,"
PRL 116, 191301 (2016).

JM
Javier Magan,
"Black holes, Complexity and Quantum Chaos,"
JHEP 09, 043 (2018).

CV
Douglas Stanford and Leonard Susskind,
"Complexity and Shock Wave Geometries,"
PRD 90, 126007 (2014).

YF1
Alexander Yosifov and Lachezar Filipov,
"Quantum Complexity and Chaos in Young Black Holes,"
Universe, 5(4), 93 (2019).
  
Hartman
Thomas Hartman and Juan Maldacena,
"Time Evolution of Entanglement Entropy from Black Hole Interiors,"
JHEP 05, 014 (2013).

Preskill
Isaac Kim, Eugene Tang, and John Preskill,
"The Ghost in the Radiation: Robust Encodings of the Black Hole Interior,"
arXiv:2003.05451 [hep-th] (2020).

Kim
Run-Qiu Yang and Keun-Young Kim,
"Time Evolution of the Complexity in Chaotic Systems: Concrete Examples,"
JHEP 05 045, (2020).

Masam
Masamichi Miyaji,
"Butterflies from Information Metric,"
JHEP 09 002, (2016).

fubinistudy
Paolo Facchi, Ravi Kulkarni, Vladimir Manko, Giuseppe Marmo, Ennackal Sudarshan, and Franco Ventriglia,
"Classical and Quantum Fisher Information in the Geometrical Formulation of Quantum Mechanics,"
PLA 374, 4801 (2010). 

otoc1
Juan Maldacena, Stephen Shenker, and Douglas Stanford,
"A Bound on Chaos,"
JHEP 08, 106 (2016).

rmt
O. Bohigas, M. J. Giannoni, and C. Schmit,
"Characterization of Chaotic Quantum Spectra and Universality of Level Fluctuation Laws,"
PRL 52, 1 (1984).

random1
Joseph Emerson, Etera Livine, and Seth Lloyd,
"Convergence Conditions for Random Quantum Circuits,"
PRA 72, 060302 (2005).

random2
Aram Harrow and Richard Low,
"Random Quantum Circuits are Approximate 2-designs,"
Comm. Math. Phys. 291, (2009).

chaos
Rodolfo Jalabert and Horacio Pastawski,
"Environment-Independent Decoherence Rate in Classically Chaotic Systems,"
PRL 86, 2490 (2001).

harlow
Daniel Harlow,
"Aspects of the Papadodimas-Raju Proposal for the Black Hole Interior,"
JHEP 2014, 55 (2014).

message
Leonard Susskind,
"Butterflies on the Stretched Horizon,"
arXiv:1311.7379v2 [hep-th] (2013).

message2
Leonard Susskind,
"Computational Complexity and Black Hole Horizons,"
arXiv:1402.5674v2 [hep-th] (2014).

pseudo
Patrick Hayden, Debbie Leung, and Andreas Winter,
"Aspects of Generic Entanglement,"
Comm. Math. Phys. 265, 95 (2006).



