Random physics

Alberto Verga, research notebook

\(\newcommand{\I}{\mathrm{i}} \newcommand{\E}{\mathrm{e}} \newcommand{\D}{\mathop{}\!\mathrm{d}} \newcommand{\GR}{\mathrm{GR}} \newcommand{\FT}{\mathrm{FT}} \newcommand{\Tr}{\mathrm{Tr}} \newcommand{\len}{\mathrm{len}} \newcommand{\bra}[1]{\langle{#1}|} \newcommand{\ket}[1]{|{#1}\rangle} \newcommand{\braket}[1]{\langle{#1}\rangle} \newcommand{\bbraket}[1]{\langle\!\langle{#1}\rangle\!\rangle} \newcommand{\bm}[1]{\boldsymbol #1}\)

Interacting quantum walk on graphs: thermalization and entanglement

in collaboration with R.G. Elías (Santiago, Chile) and K. Sellapillay (Aix-Marseille)

[Slides of the talk .pdf]


We extend quantum walks by introducing an interaction of the particle degrees of freedom with local spins sitting on the nodes of a graph. This system allows us to investigate, in an isolated quantum system, the appearance of a thermal state and its entanglement properties. A modification of the model, in which the spins are on the network edges, exhibit a rich dynamical behavior in simple lattices, including oscillations, relaxation and localization of states.


In a simple quantum walk, the particle motion is determined by an internal degree of freedom (we call color), however, the geometry of the motion is imposed in the form of a lattice or more generally a graph. The position amplitudes are then distributed over the neighbors of each node. We can make an analogy with a tight binding model, in which an electron jumps between sites of a crystal. The main physical difference is that the crystal is itself a lattice of ions whose intricate interaction with the electron gas (for instance in a semiconductor) gives rise to both, the crystal structure and the characteristic energies of the electron hopping. This observation motivates our choice of assigning a material support to the graph in which the walker moves. A natural way is to associate a spin degree of freedom to the graph nodes (our first model) or to the links between nodes (our second model): the particle is there or the particle transit there. The interaction of the walker (position and color degrees of freedom) with the geometry (spin degrees of freedom) give rise to an extension of the simple quantum walk to an interacting one. The main consequence of this generalization is that we leave the simple world of one particle to the complex many—body interacting quantum system.

  • Entanglement and thermalization of an isolated system

  • Structure of the thermal state and eigenstate thermalization hypothesis

  • Entanglement dynamics in spin networks induced by an itinerant particle

Node spin model: entanglement and thermalization

A walker jumps between the nodes of a graph of interacting spins; the particle color interacts with the local spin favoring entanglement along graph paths

Hilbert space \(\ket{xcs} = \ket{x} \otimes \ket{c} \otimes \ket{s_0s_1\ldots s_{N-1}}\)

Coin operator \(C\)

\begin{align*} \braket{x'c's'| \GR |x c s} &= \left(\frac{2}{d_x} - \delta_{c,c'}\right) \delta_{x,x'} \delta_{s,s'}\\ \braket{x'c's'| \FT |x c s} &= \frac{1}{\sqrt{d_x}} \exp (\I 2 \pi c c' / d_x) \delta_{x,x'} \delta_{s,s'} \end{align*}

Motion operator

\begin{equation*} M \ket{x c_y s} = \ket{y c_x s},\quad (x,y)\in E \end{equation*}

Quantum walk on a graph of interacting spins

We consider a graph \(G=(V,E)\) of vertices \(x\in V\) and edges \(e=(x,y) \in E\). The particle degrees of freedom are its position \(x=0,\ldots,|V|-1\) and its color, which takes values according to the number of neighbors of each node \(d=0,\ldots,d_x-1\). On each node resides a spin, whose state is labeled by a binary number \(s_x=0,1\); a spin configuration is then given by the binary representation of a number \(s=s_0\cdots s_{|V|-1}\). In summary, the hilbert space is deployed by the basis \(\ket{xcs}\).

The walk is defined by a unitary operator \(U=ZXMC\) that can be split into a coin \(C\), which we choose to be either a grover or a fourier one, a motion \(M\) which exchange the amplitudes between neighboring nodes, and two interaction operators, one \(X\) between the particle and the node spin (local to the node), and the other \(Z\) which introduces an ising—like exchange between spins. These interaction operators are local: they apply to two qubits.

Interaction operator: spin—particle (color)

\begin{align*} X \ket{x,0,\ldots s_x=1 \ldots} & = \ket{x,1,\ldots 0 \ldots}\\ X \ket{x,1,\ldots s_x=0 \ldots} & = \ket{x,0,\ldots 1 \ldots} \end{align*}
Interaction operator: spin—spin (Ising type)
\begin{equation*} Z \ket{xc,s=\ldots s_x \ldots s_y \ldots} = \begin{cases} - \ket{xcs} & \text{if } s_x= s_y = 1 \\ \ket{xcs} & \text{otherwise} \end{cases} \end{equation*}

Walk operator \(U=ZXMC\), \(\ket{\psi(t+1)} = U \ket{\psi(t)}\).

Entanglement and thermalization of an isolated system

Many—body systems at low energy are described by their ground state and excitations, emerging quasiparticles, quantum phase transitions, localization and topological nontrivial band structure; high energy behavior includes thermal properties, linear response, relaxation and transport. Some important properties of these systems are related with quantum entanglement: the spin liquid ground state can be thought as strings of entangled spins, and the thermalization as a process of entanglement of subsystems with the whole, perhaps closed, system.

In particular, thermalization of a quantum isolated system can be related with the properties of chaotic high energy eigenstates, which is the so called eigenstate thermalization hypothesis. We show that our model of interacting quantum walk is able to account for this thermalization scenario.

The thermalization hypothesis says that the expected value of most observables \(O\), given by the microcanonical distribution at thermodynamic energy \(E\) inside a band of energy \(\Delta\), having, in the thermodynamic limit, an infinity of levels such that \(\Delta(N)/N \rightarrow 0\), is well approximated by the expected value of \(O\) in an arbitrary eigenenergy vector \(\ket{n}\) within the \(\Delta(E)\) band. Fluctuations are of the same order as ordinary thermodynamic fluctuations.

Isolated many—body system with hamiltonian \(H\),

$$H \ket{n} = E_n \ket{n}$$

in a chaotic sate \(\ket{\psi}\)

The (local) observable \(O\) satisfies

$$\braket{\psi|O|\psi} \approx \braket{n|O|n} \approx \Tr \rho_{MC} O(E)$$

for \(E \approx E_n\).

We say that \(\ket{\psi}\) is a thermal state: most observables satisfy ETH.

Position distribution in a random graph (Fourier coin):

$$ \rho(t) = \ket{\psi(t)}\bra{\psi(t)}, \quad \ket{\psi(t)} = \sum_{xcs}(t) \psi_{xcs} \ket{xcs} $$

$$p(x,t) = \Tr_{\bar{x}} \rho(t) = \sum_{cs} |\psi_{xcs}(t)|^2$$

Using exact numerical computation of the quantum state evolution, from an initial localized product state, we observe that the long time behavior of the system is well described by the microcanonical ensemble. For instance, the position distribution is uniform over the graph: node to node variation is proportional to the node degree.

A more straightforward test of the eigenstate thermalization is given by the Shannon entropy and the distribution of the eigenvalues \(E_n\) of \(U\).

Shannon entropy:

$$ S(n) = - \sum_{xcs} |v_n(xcs)|^2 \log|v_n(xcs)|^2,\; v_n(xcs) = \braket{ xcs | n }$$

Gaussian unitary ensemble distribution of eigenvalues spacing \(s\):

$$ p(s) = \frac{32 s^2}{\pi^2} \E^{-4 s^2/\pi}$$

The Shannon entropy constructed with the energy eigenvectors amplitudes is uniformly distributed over the whole energy range. The expected value of the observable do not depend on the specific eigenvector we choose. We may say that the overlap between the initial state and \(\ket{n}\) is, in the thermodynamic sense, negligible: the expectation \(\braket{O}\) do not depend on the initial condition. Even if the whole system is always in a pure state.

The spectrum of \(U\) is almost flat, and, using a fourier coin, the levels are non degenerate. The histogram of the quasienergies separation \(s\sim \Delta E_n\), is perfectly fitted by the Wigner surmise corresponding to the unitary gaussian ensemble (GUE).

This result might be rather surprising, because the GUE applies to gaussian random matrices. In contrast, \(U\) is a rather sparse matrix, filled with simple numbers (mostly 1) related to the coin operator. Note, however, that even if \(U\) is a simple matrix, \(H=\I \ln(U)\), the effective hamiltonian is, in general, a much more complicate and dense matrix.

Structure of the thermal state and the eigenstate thermalization hypothesis

One may think that the thermal state should be completely random, however, in analogy with for instance the spin liquid topological ground state, some entanglement structure may be present. We show that the specific interactions between the walker and the spins, yields an interesting structure, related with the graph cycles, revealed by the entanglement entropy of the spins.

The particle color—spin interaction favors one dimensional paths drown on the graph. We show that the von Neumann entropy

$$S_l(t) = - \Tr \rho_l(t) \log \rho_l(t) \le \log D_l - \frac{D_l^2}{2D\ln(2)}$$

(\(l = \{x,c,s\}\)) is related with the \emph{minimal cycle basis} entropy:

$$S_s \approx S_C = \log\left[ \sum_{n = 1}^{|B^\star|} \len(b^\star_n)\right]$$


$$B^\star = \left\{ b_n^\star \,\big|\, \sum_n\len b_n^\star = \min_B \len(B) \right\}$$

and \(B = \{b_n \in B_C,\; n=1,\ldots,|B| = |E| - |V| + 1\}\) is the cycle basis associated with \(G\).

The graph on the left has a cycle basis of dimension 2, a rectangle and a triangle; a linear combination of the two basis cycles gives another cycle in the set of cycles in \(G\)

The formula of \(S_C\) means that the spin entanglement entropy can be computed from the graph cycle structure. This is related with color—spin interaction with favors one dimensional paths of particle—spin entanglement. Therefore, the thermal state, which is close to the maximum entangled state predicted by Don Page, can be described as a superposition of entangled spins chains.

Strings of entangled spins


\(|V|=5,\ldots,15\) nodes

Application of the \(S_C\) formula to a series of random graphs having a number of vertices between 5 and 15, shows good agreement with the numerical results.

Edge spin model: dynamics

A different model can be constructed assuming that the spins represent the edges, and not the nodes, of the geometry where the quantum walker moves. As a first step towards the construction of this model, we suppress the spin—spin interaction, and modify the spin—color interaction, using the notion of edge basis states. For instance, the spin on edge \(e=(x,y)\) interacts with the color of a particle passing across this edge, \(c_e=(c_y,c_x)\); this allows us to introduce an ising—type interaction between the edge coler \(c_e\) and the local spin \(s_e\).

Hilbert space \(\ket{xcs} = \ket{x} \otimes \ket{c} \otimes \ket{ s_0 \ldots s_{|E|-1} } \in \mathcal{H}_G\)

Spin—color interaction on edge \(e=(x,y)\):

$$S(J) = \exp(-\I H),\; H = -\frac{J}{4} \bm{\tau}_e \cdot \bm{\sigma}_e$$

Quantum walk step operator:

$$U = SMC$$

One dimensional quantum walks with a rotation coin operator \(R(\theta)=\exp(-\I\sigma_y \theta)\), show interesting topological properties. We investigate, in our interacting case, the motion of a quantum walker in a line having two topologically different regions.

One dimensional lattice walk with a rotation coin \(R(\theta)=\exp(\I\sigma_y \theta)\). In the free case (\(J=0\)) a change of topology arises at \(\theta=\pi/2\).

We introduce an interface at the center of the lattice separating a left and right regions with different coin angles. In the trivial case \(\theta_L, \theta_R <\pi/2\) and in the topological case \(\theta_L < \pi/2 < \theta_R\).

We observe clearly that in the topologically trivial case there is no edge channel; in contrast with the topological case, in which, in addition to the traveling modes, a concentration of the position probability is present at the interface.

Other interesting observation is that the entanglement of one or two (separated) spins with the other spins (and the particle) grows linearly in time and reach, for long times, almost its maximum value.


The interacting quantum walk allows us to investigate, within a simple framework, fundamental physical mechanisms arising in condensed matter.


  • Interacting quantum walk on a graph, A.D. Verga, Phys. Rev. E 99, 012127 (2019)

  • Thermal state entanglement entropy on a quantum graph, A.D. Verga and R.G. Elías, Phys. Rev. E 100, 062137 (2019)

  • Dynamics of an interacting quantum quantum walk on a graph, K. Sellapillay, this conference. arXiv