Entanglement entropy in two-particle Grover walks on graphs

Technical Summary: Entanglement Entropy in Two-Particle Grover Walks on Graphs

Problem Statement
This paper addresses the dynamics of discrete-time two-particle quantum walks involving identical particles on arbitrary connected graphs. While single-particle quantum walks are well-studied, multi-particle systems introduce complexities regarding particle distinguishability, exchange symmetry, and entanglement. A central challenge is defining a time evolution operator for identical particles that satisfies the fundamental quantum mechanical requirement of invariance under particle exchange (symmetry for bosons, antisymmetry for fermions). Furthermore, the authors investigate the generation of entanglement entropy in such systems, specifically seeking conditions under which the system evolves into a maximally entangled state (attaining the theoretical upper bound of entropy).

Methodology
The authors propose a construction for the two-particle Grover walk based on an isomorphism between the "two-particle Hilbert space on a graph $G$" and the "one-particle Hilbert space on the Kronecker product graph $G \otimes G$."

1. Graph-Theoretic Construction: Instead of defining interactions via local potentials or tensor products of independent single-particle evolutions, the authors define the two-particle walk $U$ on $G$ via the one-particle Grover walk $\mathcal{U}$ on $G \otimes G$. A linear isomorphism $R$ maps the tensor product space $H^{(2)}(G)$ to the single-particle space of $G \otimes G$.
2. Symmetry Verification: To ensure the walk respects the indistinguishability of identical particles, the time evolution operator $U$ must commute with the swap operator $P$. The authors utilize algebraic graph theory to prove this. They demonstrate that the mapping $g(x, y) = (y, x)$ is an automorphism of the Kronecker product graph $G \otimes G$. By leveraging the property that the Grover walk's time evolution commutes with graph automorphisms, they prove that $U$ commutes with $P$, thereby satisfying the symmetry requirements for both bosonic and fermionic states.
3. Entanglement Analysis: The entanglement entropy $S(\psi)$ is defined via the eigenvalues of the amplitude matrix $\Psi$ associated with the state $\psi$. The upper bound for this entropy is $\log(2|E|)$, where $|E|$ is the number of edges in $G$. The condition for attaining this bound is that the matrix $\Psi\Psi^*$ must be proportional to the identity matrix.
4. Specific Case Study: The authors apply this framework to complete bipartite graphs $K_{n,n}$. They utilize the spectral properties of $K_{n,n}$ and the fact that the Grover walk on such graphs is 4-periodic ($U^4 = I$) to explicitly compute the state evolution and amplitude matrices for initial times $\tau = 0, 1, 2, 3$.

Key Contributions and Results

• Theorem 1.1 (Commutativity): The paper establishes that the time evolution operator of the two-particle Grover walk on any graph $G$ commutes with the swap operator. This confirms that the proposed construction via $G \otimes G$ naturally satisfies the exchange symmetry required for identical particles without imposing ad-hoc constraints.
• Theorem 1.2 and Theorem 4.5 (Maximal Entanglement on $K_{n,n}$): The authors completely determine the values of $n$ for which the two-particle Grover walk on the complete bipartite graph $K_{n,n}$, starting from specific symmetric/antisymmetric edge-based initial states, achieves the maximum possible entanglement entropy at some time step.
  • The entropy attains its upper bound if and only if $n = 1$ or $n = 2$.
  • Case $n=1$ ($K_{1,1}$): The system is maximally entangled at every time step.
  • Case $n=2$ ($K_{2,2}$): The system attains maximal entanglement if and only if the time step $\tau \equiv 2 \pmod 4$.
  • Case $n \ge 3$: The entanglement entropy never attains the upper bound for any time step.
• Explicit State Evolution: The paper provides explicit formulas for the quantum states $\psi_\tau$ and their corresponding amplitude matrices for the first few time steps on $K_{n,n}$, verifying the non-attainment of the upper bound for $n \ge 3$ through direct calculation of the diagonal entries of $\Psi\Psi^*$.

Significance and Claims
The paper claims that its primary contribution is the rigorous definition of a two-particle Grover walk that inherently respects particle indistinguishability through the symmetry of the Kronecker product graph. By linking the multi-particle dynamics to the single-particle dynamics on $G \otimes G$, the authors provide a framework where global interactions emerge naturally, distinct from models with local interactions or non-interacting tensor products.

Regarding entanglement, the authors demonstrate that while the system can generate maximal entanglement, this capability is highly sensitive to the graph structure. For the specific family of complete bipartite graphs, maximal entanglement is a rare phenomenon, occurring only for the smallest instances ($n=1, 2$). The authors note that while their direct computational approach works well for periodic graphs like $K_{n,n}$, it is difficult to generalize to arbitrary graphs. They suggest that future work should focus on finding analytic methods or necessary conditions based on graph eigenvalues to predict entropy bounds, noting an observed correlation between graphs that exhibit maximal entanglement, periodicity, and perfect state transfer (e.g., $K_{1,1}$, $K_{2,2}$, and the path graph $P_5$).