{'fraction_non_alphanumeric': 0.0554625294740799, 'fraction_numerical': 0.01893175682602604, 'mean_word_length': 3.896101723272545, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
History states of one-dimensional quantum walks

We analyze the application of the history state formalism to quantum walks. The formalism allows one to describe the whole walk through a pure quantum history state, which can be derived from a timeless eigenvalue equation. It naturally leads to the notion of system-time entanglement of the walk, which can be considered as a measure of the number of orthogonal states visited in the walk. We then focus on one-dimensional discrete quantum walks, where it is shown that such entanglement is independent of the initial spin orientation for real Hadamard-type coin operators and real initial states (in the standard basis) with definite site parity. Moreover, in the case of an initially localized particle it can be identified with the entanglement of the unitary global operator that generates the whole history state, which is related to its entangling power and can be analytically evaluated. Besides, it is shown that the evolution of the spin subsystem can also be described through a spin history state with an extended clock. A connection between its average entanglement (over all initial states) and that of the operator generating this state is also derived. A quantum circuit for generating the quantum walk history state is provided as well.

We analyze the application of the history state formalism to quantum walks. The formalism allows one to describe the whole walk through a pure quantum history state, which can be derived from a timeless eigenvalue equation. It naturally leads to the notion of system-time entanglement of the walk, which can be considered as a measure of the number of orthogonal states visited in the walk. We then focus on one-dimensional discrete quantum walks, where it is shown that such entanglement is independent of the initial spin orientation for real Hadamard-type coin operators and real initial states (in the standard basis) with definite site-parity. Moreover, in the case of an initially localized particle it can be identified with the entanglement of the unitary global operator that generates the whole history state, which is related to its entangling power and can be analytically evaluated. Besides, it is shown that the evolution of the spin subsystem can also be described through a spin history state with an extended clock. A connection between its average entanglement (over all initial states) and that of the operator generating this state is also derived. A quantum circuit for generating the quantum walk history state is provided as well.
In this work we will focus on one-dimensional discrete QW [3,4,[60][61][62], in which a spin 1/2 quantum particle undergoes a unitary evolution in a discrete homogeneous lattice in discrete time steps, according to a translation rule controlled at each step by the value of its spin component and the action of a quantum gate on the spin.
We will analyze the walk from the new perspective provided by the history state formalism, here applied in its discrete version [47][48][49]. The ensuing history state is a pure state of the composite system comprising both the position and spin degrees of freedom on one side (system S), and a quantum clock system T on the other. It contains the information of the whole QW and satisfies a timeless eigenvalue equation, such that the state of S at step n can be obtained by conditioning the history state with the corresponding clock state. It can be generated from an initial product state through a quantum circuit.
The corresponding system-time entanglement is a measure of the degree of evolution of S, i.e., of the number of orthogonal states visited in the QW, and will be shown to be fully determined by the overlaps between the evolved states. Notice that this entanglement is not the spin-position entanglement usually considered [31][32][33]. We then show that for real Hadamard-type coin operators such entanglement becomes independent of the initial spin state for a wide class of initial position states, including the standard case of an initially localized particle. In the latter, it is also shown that this entanglement is the operator entanglement of the quantum gate generating the history state from the initial product state. Such entanglement defines in fact the entangling power of this operator, which determines the average over all initial spin states of the history state entanglement. In the case of the quadratic entropy it can be evaluated analytically, and an asymptotic expression for large N can be derived in terms of the coin operator parameter, showing explicitly the deviation from the maximum entropy (i.e., maximally entangled) limit. The associated entanglement spectrum is also analyzed.
Besides, it is also possible to define a spin history state by considering a different partition of the whole system, with the spin on one side and a composite clock (the original clock plus the position degree of freedom) on the other. In the case of an initially localized particle the ensuing spin-rest entanglement is shown to be related to that of the unitary operator generating the spin history state. An upper bound to the average spin-rest entanglement is thus obtained, arising from the reduced Schmidt rank of the previous operator.
We first briefly review in Section II the main features of discrete one dimensional QW and their exact evolution. The history state formalism for the QW is introduced in section III, where the main results, together with analytic expressions for overlaps and system-time entanglement entropy are provided. The connection with operator entanglement and the spin history state are discussed in section IV. Illustrative numerical results are shown in both III and IV. Finally conclusions are drawn in V.

A. Generalities
Standard one-dimensional quantum walks are processes in which a quantum "particle" (quantum system) with spin 1 2 and hence internal Hilbert space H s = C 2 , moves along a one-dimensional lattice spanned by position eigenstates |x , x ∈ Z, which generate the position Hilbert space H p . The full Hilbert space of the system is then H S = H p ⊗ H s . At each time step two operations are performed such that their composition gives the unitary evolution from one time to the next. The first one acts on the spin component (quantum coin) and leaves the position unchanged. This is usually taken as a kind of generalized Hadamard transform [62], represented in the standard basis (eigenstates {|↑ , |↓ } of σ z ) as where γ, φ are arbitrary angles and 0 ≤ ρ ≤ 1, such that C † C = 1. We will here focus on traceless real coin operators, such that it results in a Hadamard-type operator with Pauli matrices and cos 2 θ = ρ. The usual Hadamard gate is recovered for θ = π/4. Any traceless hermitian unitary coin operator C can be written in the form (2) by adequately chosing the x axis. The second operation is a conditional one-step displacement to the right (left) if spin is up (down) along z, generated by the translation operator T (T † ). The total operator generating the step is then given by and verifies the unitary condition U † U = 1 p ⊗ 1 s .

B. Exact evolution and overlaps
Assuming an initial state which is localized in space, i.e., with support in some finite interval, it is convenient, for obtaining a closed exact analytic expression of the evolved states, to consider a finite position basis {|x , x = 0, . . . , M − 1}, with x|x = δ xx , which contains the initial state as well as the evolved states up to, say, N steps (i.e. M > 2N for an initially localized particle, where N is the number of steps). Then we define the associated discrete Fourier transformed (DFT) basis satisfying k|k = δ kk and |− k = |M−k . These states are the eigenstates of the cyclic translation operator defined by T |x = |x + 1 , with T |M − 1 = |0 , such that The operator (4) can then be rewritten as where K is the discrete "momentum" operator satisfying For each value k of K, (7b) represents, in the standard spin basis, a unitary operator U k in spin space fulfilling Det[U k ] = −1, with eigenvalues where φ k = 2π k/M , and eigenvectors satisfying s ν k |s ν k = δ kk δ νν . Thus, Whereas in the position representation (4) it is the spin which appears as controlling the position displacement, in the momentum representation (10a) based on the eigenbasis of T , it is the momentum K which controls the spin evolution at each step. Using (10) we can now determine the evolution of a general initial product state where ψ 0 (x) is the initial position state, with the DFT of ψ 0 (x) (sums over k, x are from 0 to M − 1) and |χ 0 the initial spin state. The state after n steps is where the evolved spin state for momentum k is A quantity of most importance in this work is the overlap between the evolved states, (9)). Moreover, entailing U n −k = (−1) n σ y U n k σ y . It is also evident from (7b) that for M even, We finally notice that in the special case θ = π/2, λ ± k = ±1 (ω k = 0) and U 2 k = 1 s ∀ k, i.e. U 2 = 1: the system always returns to its initial configuration after two steps, as C = σ x (Eq. (2)) flips the coin at each step.

A. Definition and main properties
Let us now consider a quantum walk with N − 1 steps, starting from an initial state |Ψ 0 at time t 0 = 0 and ending in a state |Ψ N −1 at time t N −1 = (N −1)τ , where τ is a certain time scale. We then consider a quantum clock system T with an orthogonal set of states |n , n = 0, . . . , N − 1, representing the scaled time n = t n /τ at which the n th step takes place. They are eigenstates of a clock operator T c satisfying T c |n = n|n , and could represent, for instance, the scaled position of the clock's needle.
We now define the quantum walk history state as where |Ψ n is the system state (13) at step n. The state (18) contains the whole information of the walk. For example, the time average of an observable O S of the particle over the complete walk can be expressed as whereas matrix elements between system states at any two times can be written as Using Eqs. (13) and (18), the quantum walk history state can be generated from an initial product state |ψ 0 |χ 0 |n = 0 through the schematic circuit of  History states actually determine the system evolution when they satisfy a proper timeless eigenvalue equation [49]. Defining the system-clock unitary operator where (18) is first seen to be an exact eigenstate of U with eigenvalue 1: Conversely, if |Ψ is any state satisfying Eq. (22), i.e. a state which remains fully invariant under U, then implying that system states |Ψ n := √ N n|Ψ will fulfill the discrete unitary evolution |Ψ n = U n,n−1 |Ψ n−1 , i.e., Eq. (13) for constant U n,n−1 = U (1 ≤ n ≤ N − 1). Normalization 1 = Ψ|Ψ = n Ψ|n n|Ψ then entails Ψ n |Ψ n = 1. The whole system evolution up to step N − 1 is thus determined by Eq. (22) and the initial state |Ψ 0 . The same holds for general unitaries U n,n−1 (22) implies J |Ψ = 0 (or 2kπ, k integer), which is a discrete Wheeler-DeWitt-type equation [50]. In fact, if U n,n−1 = U ∀ n = 1, . . . , N (such that U N = 1) then J = H ⊗ 1 T + 1 S ⊗ P c , where e −iH = U determines the step evolution in S and e −iPc = N n=1 |n n−1| generates the unit translation in the time basis (|n − 1 → |n ) [49].
We also mention that the other eigenvalues of U are e −i2πk/N (k = 0, . . . , N − 1) [48,49]. Hence, |Ψ can also be seen as the ground state of the hermitian operator − 1 2 (U + U † ), which has eigenvalues − cos 2πk N . This enables the use of variational methods for its determination [47,55].

B. System-time entanglement
The entanglement E(S, T ) of the history state (18) can be regarded as a measure of the "degree of evolution" of system S, i.e., of the number of orthogonal states visited in the walk: If |Ψ 0 is an eigenstate of U , i.e. a stationary state satisfying U |Ψ 0 = e iγ |Ψ 0 , the history state becomes separable: , and E(S, T ) = 0 [48]. This case arises here in finite cyclic realizations when |ψ 0 in (14) remains invariant under translations, i.e., when it is a state |k , and |χ 0 coincides with one of the eigenstates |s ± k of U k , such that U n |Ψ 0 = e ∓inω k |Ψ 0 for |Ψ 0 = |k ⊗ |s ± k . The opposite situation is an evolution where at each step the system evolves into a new orthogonal state such that Ψ n |Ψ n = δ nn , in which case E(S, T ) is maximum. This evolution arises here in the trivial limit θ → 0 for an initially localized state ψ 0 (x) = δ xx0 with definite spin along the z axis (σ z |χ 0 = ±|χ 0 ), such that the particle advances always in the same direction.
In the general case E(S, T ) will be determined by the overlaps (15). We can expand (18) where |k, s ± k = |k ⊗ |s ± In (24) |m S = k,ν V kν,m |k, s ν k , |m T = n W * nm |n are orthogonal system and clock states respectively ( m S(T ) |m S(T ) = δ mm ) while n s is the Schmidt rank, i.e. the number of nonzero eigenvalues λ m , which is just the rank of the matrix M . |Ψ is then entangled iff n s ≥ 2 and separable (product state) if n s = 1.
Eq. (24) shows that the states |m S(T ) are the eigenvectors of the reduced system and clock states (25) which determine the average along the walk of any local observable ( Ψ|O S ⊗ 1|Ψ =Tr S ρ S O S ), and have the same nonzero eigenvalues λ m . Their entropies are then identical and define the entanglement entropy of the history state |Ψ (system-time entanglement [48]) where the last expression holds for a general trace-form entropy The reduced states (25) can be here also written as Eq. (27b) shows explicitly that ρ T , and hence its eigenvalues λ m and the entanglement (26) of the history state, are fully determined by the overlaps (15). The standard choice for S is the von Neumann entropy which will satisfy such that 2 E(S,T ) is essentially a measure of the number of distinct orthogonal states visited in the evolution. Another convenient choice is the quadratic entropy (also denoted as linear entropy or q = 2 Tsallis entropy [63]), which is simply determined by the purity Tr ρ 2 : and corresponds to f (ρ) = ρ(1 − ρ). It does not require the explicit determination of eigenvalues and can be measured without requiring a full state tomography [64]. It can be here directly evaluated in terms of the overlaps (15): Using (27) together with (26) and (30) we obtain where (31b) holds when | Ψ n |Ψ n | depends just on |n − n |, as in Eq. (15) (with factor ∝ 1 − n N accounting for the pertinent multiplicity). It obviously satisfies such that 1 1−E2(S,T ) is here the effective number of orthogonal states visited. A directly related quantity is the q = 2 Renyi entropy S R 2 (ρ) = − log 2 (1 − S 2 ) = − log 2 Tr ρ 2 [65], which satisfies the same bound (29).
The upper limit in (29)-(32) is reached for θ → 0 in (2) and an initially localized particle with definite σ z . On the other hand, for θ = π/2 the evolution becomes periodic with period 2 (as U 2 = 1) and hence the system-time entanglement entropy will stay trivially bounded ∀ N : with the upper limit reached for an orthogonal intermediate state. Thus, by varying θ in the interval [0, π/2] we can reach, for an initially localized particle, all possible rates of system-time entanglement increase with N , from the maximum rate for θ = 0 to the null increase for θ = π/2, entailing in general a decrease of E(S, T ) with increasing θ in this interval.
C. Independence of system-time entanglement from initial spin state

Real initial states with definite site parity
We now examine the entanglement (26) for some general types of initial states |Ψ 0 . We first notice that if |Ψ 0 has a definite position parity, such that its support are just even (or odd) sites x, where X is the discrete position operator X|x = x|x , the overlap Ψ n |Ψ n will vanish for n − n odd since at each step the particle will move to sites of opposite parity: Eq. (34) is trivially fulfilled for an initially localized particle ψ 0 (x) = δ x,x0 . In momentum space, Eq. (34) implies c k+M/2 = ±c k (M even) and (35) follows from (17) and (13).
Then, for real ψ 0 (x) and α, β in (11), such that c −k = c * k and s ± −k |χ 0 = s ± k |χ 0 * , we obtain, using ν=± | s ν k |χ 0 | 2 = 1 and Eq. (15c), Thus, the overlap becomes independent of the initial (real) spin state |χ 0 ∀ n. This implies a system-time entanglement entropy independent of |χ 0 . Previous result can be seen more clearly using Eq. (16) and (15b): since σ y |χ 0 is orthogonal to |χ 0 for |χ 0 real (α, β real in (11c), equivalent to σ in the x, z plane) and χ 0 |U n −k |χ 0 = (−1) n χ 0 |σ y U n k σ y |χ 0 , for |c −k | = |c k | and n even we obtain which shows that the even overlap depends just on the trace of U n k , i.e. on the partial trace of U n over spin, and is hence independent of the initial spin state |χ 0 . Eq. (37) leads again to (36) for n even and also n odd, as Tr U n k = e −inω k + (−1) n e inω k = (−1) n Tr U n −k and hence the sum in (37) vanishes for n odd when |c −k | = |c k |.
With previous expressions, the sum over N in the quadratic system-time entanglement (31b) can be evaluated analytically: , N odd (38b) Here sin 2 mu m 2 sin 2 u is understood as its limit 1 if sin u = 0 (m integer), being a polynomial of degree m − 1 in cos u ( sin(n+1)u sin u = n/2 k=0 (−1) k n−k k (2 cos u) n−2k is a Chebyshev polynomial of the second kind [66]).
As a check, it is verified that for θ = 0, we obtain from (43b) maximum entropy ∀ N (P n (1) = 0 for n ≥ 1): in agreement with previous considerations (any entropy is obviously also maximum in this case). And for θ = π/2, we recover from (43b) Eq. (39) for both N even or odd, as P n (0) = 1 ∀ n ≥ 1. Exact results as a function of N and θ are depicted in Figs. 2-3. For large N , we may use Eq. (42) for n = 0 and approximate the sum over n in (43b) by an integral over u = 2n/N , which leads to the asymptotic expression sin t t dt and c = 1 + π 2 (neglecting terms O (N −2 )). The deviation from maximum entropy S max 2 = 1 − 1 N is then O( ln N N ) and proportional to tan θ, in agreement with previous considerations. This result can also be obtained from (38) using sin 2 (N u/2) N sin 2 u/2 → N →∞ 2πδ(u) for |u| < π and integrating over φ = 2πk m . An exact summation using (42) is given in the appendix.

Entanglement spectrum
For an initially localized particle, we may also examine the entanglement spectrum, i.e., the common eigenvalues of the reduced densities (27) for 0 ≤ n, n ≤ N − 1. This leads to two similar blocks (n, n even or odd respectively), identical for N even. For sufficiently large N the eigenvalues of each block (identical for N even) come essentially in almost degenerate pairs for θ not close to π/2, with the number of non-negligible eigenvalues decreasing with increasing θ, as depicted in Fig. 4. The largest eigenvalue lies close to the Gershgorin upper bound, i.e., using Eq. (42), where H 1/2 (m) = m n=1 1 √ n (≈ 2 √ m + ζ( 1 2 ) for large m) is the generalized harmonic number (ζ(1/2) ≈ −1.46 is the Riemann zeta function at 1/2). Thus, there is always a deviation O(N −1/2 ) from the maximally mixed distribution, proportional to tan 1/2 θ.

A. Entanglement of unitary operators
We will show here that the system-time entanglement entropy for the initially localized particle, which is independent of the initial (real) spin state, is the entanglement entropy of the global unitary operator which generates the quantum walk.
First, let us consider a complete set of local orthogonal where d S(T ) is the Hilbert space dimension of S (T ). Any operator U on the whole system can be expanded as where where λ m are the eigenvalues of M † M or M M † and are new local orthogonal operators satisfying (48), withñ s the rank of M . If U is unitary the eigenvalues λ m are again standard probabilities (λ m ≥ 0, m λ m = 1). Thus, for a general trace-form entropy, the entanglement entropy of the unitary operator U can be defined as vanishing iff U is a product of local unitaries (ñ s = 1). The analogy with state entanglement is straightforward if the Choi isomorphism for representing operators is employed. Any operator U on H ST = H S ⊗ H T can be associated to a pure state |U in H ST ⊗ H ST given by where |1 = 1 √ d S d T µ |µ ⊗|µ is a maximally entangled state in H ST ⊗ H ST . In this way, an exact map for inner products is obtained: with U|U = 1 for a unitary operator U. Thus, Eqs. (49)-(50) can be recast, noting that |1 = |1 S ⊗ |1 T , as We can now rewrite (51) as | are the local reduced densities derived from |U . In particular, the quadratic entropy becomes B. Operator entanglement and quantum walk If a system initially in a state |Ψ 0 undergoes a discrete unitary evolution through times n = 0, . . . , N − 1 and states |Ψ n = U n |Ψ 0 , its history state can be generated from an initial system-clock product state as (see Fig. 1) where |0 = H ⊗m |0 = 1 is a controlled-U n unitary operator on the whole system. Its state representation (52) is where |T n = ( √ N |n n| ⊗ 1)|1 = |n ⊗ |n and |U n = 1 √ d S µ (U n |µ S ) ⊗ |µ S . Therefore, the unitary operator W generating the history state from a product state can itself be represented as an operator history state (59).
The reduced operator state of the clock is here in full analogy with (27b), showing again that the entanglement of the generating operator (58)- (59), is fully determined by the overlaps U n |U n . In the present random walk, U n = U n and is exactly the overlap (40)-(41)-(46) between the evolved system states for an initially localized particle with real initial spin state. Thus, the operator entanglement (61) is exactly that of the previous system-clock history state for the initially localized particle, for any choice of entropy. In particular, the quadratic operator entanglement is just the quadratic S-T entropy (43). And the entanglement spectrum of W coincides with that of the history state (Fig. 4).
The quadratic entropy (63) has an additional meaning: It determines the entangling power of the unitary operator W, i.e. the average quadratic entanglement E 2 (S, T ) it generates when applied to initial product system-clock states: with the average taken over the whole set of initial system states |Ψ 0 with the Haar measure dΨ 0 [49]. Thus, for d S 1 the quadratic S-T entanglement entropy (43), equal to (63), is very close to the average value (64).

C. Spin history states in the quantum walk
If we now consider as system only the spin degree of freedom, we first notice from Eq. (13) that for a particle initially localized at x = 0, the state after n steps is exactly a spin history state, with respect to the momentum states |k . The "evolution" operators are here the k-projected unitaries U n k acting on the spin, having a nontrivial k-dependence. Thus, the spin-position entanglement at step N is that of a spin history state. The same holds for any initial localization x 0 (|k → e −i2πkx0/M |k ).
Therefore, its average E 2 (s, p) over all initial spin states is determined by the entanglement of the operator U n generating such spin history [from the initial product state |Ψ 0 = ( 1 √ M k |k )|χ 0 ], itself an operator history state, as is apparent from Eq. (10a): The associated operator state is 1 ν=± U n k |ν |ν (|ν = ± are orthogonal spin states). Its entanglement is then determined by the overlaps (see Eqs. (10) and (70) below) While the unitaries U n k belong to a four-dimensional space spanned by the identity and the three Pauli operators, limiting the Schmidt rank of (66) to n s ≤ 4 ∀ M , they actually live within a three-dimensional subspace spanned by the identity 1 s , the coin operator σ θ ≡ C and the orthogonal Pauli operator σ y : From (7)-(8) we see that since σ z σ θ = cos θ 1 s + i sin θ σ y . And from (10b) and (68) it follows that with σ 2 k = 1. Hence all powers U n k = e −inω k |s + k s + k | + (−1) n e inω k |s − k s − k | = cos(nω k )1 − i sin(nω k )σ k (n even) , (70a) = −i sin(nω k )1 + cos(nω k )σ k (n odd) , (70b) are spanned just by {1 s , σ θ , σ y } ∀ k, n, with Tr σ θ σ y = 0. This entails a Schmidt rank n s ≤ 3 of the n th power (66), implying at most 3 non-zero eigenvalues λ m in its associated entanglement spectrum, as seen in Fig. 5, and a von Neumann entanglement entropy E(U n ) ≤ log 2 3.
Therefore, the entangling power of U n remains bounded by this rank n s ≤ 3: Rescaling the quadratic entropy as S 2 (ρ) = 2(1 − Tr ρ 2 ), such that S 2 (ρ) = 1 for a maximally mixed single spin state, it implies E 2 (U n ) ≤ 4/3. Hence, applying the relation (64) to the spin history, the average over all initial spin states of the spin-position entanglement after n steps satisfies This bound is obviously lower than the maximum E 2 (s, p) = 1 reached for a full rank maximally entangled operator U n (E 2 (U n ) = 3/2 for the rescaled S 2 ), for which |Ψ n in (65) would be maximally entangled (E 2 (s, p) = 1) for any spin state |χ 0 , in agreement with the general results of [49]. The variation of E 2 (s, p) ∝ E 2 (U ) with θ is depicted in Fig. 6. Similarly, the full history state (18) for the initially localized particle can also be regarded, when viewed from the spin, as a spin history state with respect to a composite clock, comprising both the original clock and the position degrees of freedom: where |kn = |k ⊗ |n and for clarity we have altered the order in the tensor product. In this case the unitary operator generating the full spin history is The average (over all initial spin states) E 2 (s, pT ) of the spin-rest entanglement in the state (72) is then de- termined by the entanglement of the operator (73), in turn determined by the full set of overlaps for 0 ≤ k, k ≤ M , 0 ≤ n, n ≤ N − 1.
Nonetheless, since all U n k are spanned just by {1 s , σ θ , σ y } (Eq. (68)), the Schmidt rank of (73) is again n s = 3 (or n s ≤ 3 in general), and the previous bound, i.e. E 2 (W s ) ≤ 4/3 still holds. This entails again This average is depicted as a function of θ in Fig. 7, together with the entanglement spectrum of W s .

V. CONCLUSIONS
We have analyzed the history state formalism in the context of discrete QW. The history state captures the whole evolution of the system, enabling for instance the evaluation of time averages as single quantum expectation values. It satisfies a timeless eigenvalue equation and can be generated through a quantum circuit from an initial system-clock product state. The associated systemclock entanglement entropy is a measure of the number of orthogonal system states visited in the whole QW and is fully determined by the overlaps between the evolved states. Stationary system states then lead to separable history states, while QW in which the system evolves into a new orthogonal state at each step correspond to maximally entangled history states.
We have then shown that in one dimensional QW with real Hadamard-type coin operators, such entanglement is strictly independent of the initial spin orientation for real initial states with definite position parity. We also analyzed its connection with operator entanglement, showing that in the standard case of an initially localized particle it coincides exactly with the entanglement of the unitary operator generating the whole QW. Exact analytic results for overlaps and quadratic entropies as a function of the number N of steps and the coin parameter were as well derived, including asymptotic expressions for large N . The latter show a monotonously decreasing entropy with increasing coin operator parameter θ ∈ [0, π/2], with S 2 (0) − S 2 (θ) ∝ tan θ ln N N for the quadratic entropy. The associated history state entanglement spectrum shows, accordingly, a decreasing rank for increasing θ, with a deviation O( tan θ N ) 1 2 from N −1 in the largest eigenvalue.
Finally, we have examined the QW from the spin perspective, showing that for an initially localized particle it is also described by a history state with a composite clock and a k-dependent unitary. The average over all initial spin states of the ensuing spin-rest entanglement can then be related to that of the global unitary generating this history. For the present Hadamard-type coin operator it has a limited rank with just three non-zero eigenvalues in its entanglement spectrum, leading to a bounded average spin-rest entanglement.
In summary, the history state formalism provides a novel perspective for analyzing QW. The associated system-time entanglement entropy constitutes a new measure for characterizing the whole evolution, which could be employed, for instance, in relation with the identification of dynamical phase transitions [26] and topological phases [27][28][29][30]67], of great current interest. The formalism also opens the way to efficient direct evaluation of time averages and quadratic entanglement entropies through its simulation in a quantum circuit [48,49,54], while a variational determination of the history state becomes as well possible. Finally, the extension of the formalism to open systems with nonunitary dynamics and to more complex scenarios is in principle feasible and is currently under investigation. The sum for the quadratic entanglement entropy (43b) can be done exactly for large n using the approximation (42) and neglecting terms O(n − 3 2 ). This yields ] , where η = N −1