Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.09066 · Journal of Physics A Mathematical and Theoretical

Entanglement entropy in two-particle Grover walks on graphs

Sho Kubota, Haruhiko Matsubara, Etsuo Segawa

quant-phSubmitted Jul 10, 2026• Announced Jul 13, 2026• 0 citations
arXivHTMLPDF

Abstract

We define a two-particle quantum walk of identical particles on a graph $G$ via the one-particle Grover walk on the Kronecker product $G \otimes G$, and call it the two-particle Grover walk. In systems of identical particles, quantum mechanics requires that quantum states have a certain invariance with respect to the exchange of particles. Focusing on the symmetry of the Kronecker product $G \otimes G$ as a graph, we show that the time evolution operator of this walk commutes with the swap operator, which ensures that this requirement is satisfied. Furthermore, we study the entanglement entropy of quantum states evolved by this walk. For the complete bipartite graph $K_{n,n}$, we completely determine the values of $n$ for which the quantum states evolved from specific initial states attain the upper bound of the entropy at some time, and prove that they are exactly $1$ and $2$.

Comments
18 pages, 3 figures

Related papers

Entanglement in coined quantum walks on regular graphs

Ivens Carneiro, Meng Loo, Xibai Xu +3 more

Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. Here we use numerical simulations to study the properties of discrete, coined quantum walks. We investigate the variation in the entanglement between the coin and the position of the particle by calculating the entropy of the reduced density matrix of the coin. We consider both dynamical evolution and asymptotic limits for coins of dimensions from two to eight on regular graphs. For low coin dimensions, quantum walks which spread faster (as measured by the mean square deviation of their distribution from uniform) also exhibit faster convergence towards the asymptotic value of the entanglement between the coin and particle's position. For high-dimensional coins, the DFT coin operator is more efficient at spreading than the Grover coin. We study the entanglement of the coin on regular finite graphs such as cycles, and also show that on complete bipartite graphs, a quantum walk with a Grover coin is always periodic with period four. We generalize the 'glued trees' graph used by Childs et al (2003 Proc. STOC , pp 59–68) to higher branching rate (fan out) and verify that the scaling with branching rate and with tree depth is polynomial.

arXiv:quant-ph/0504042•New Journal of Physics•Jul 12, 2005•147 citations

Quantum correlations in entangled two-particle non-unitary quantum walks

Gene M. M. Itable, Francis N. C. Paraan

We study the evolution of quantum correlations in two-particle discrete-time non-unitary quantum walks on a line with gain and loss. The two particles are initially prepared in a maximally entangled state and evolve independently. Using numerically exact calculations of position probability densities, average interparticle distance, entanglement entropy, and concurrence, we examine how dissipation and particle-exchange symmetry of the state (symmetric or antisymmetric) influence the resulting correlations. Notably, we find that the entanglement entropy of the antisymmetric state decays slower than that of the symmetric state at the exceptional point of the model. We also show that, in the antisymmetric state, the concurrence measured on the one-particle reduced density operator is unaffected by dissipation. Furthermore, we discuss how these correlations indicate quantum-to-classical transitions through the appearance of Gaussian position probability densities, sub-linear growth of average interparticle distance after a few steps, and decay of the entanglement entropy. On the other hand, the robustness of the qubit entanglement entropy can differentiate the model's topological phases better than in the one-particle quantum walk scenario.

arXiv:2505.03219•May 6, 2025•0 citations

Long-time entanglement in the Quantum Walk

Gonzalo Abal, R. Donangelo, Hugo Fort

Abstract. The coin-position entanglement generated by the evolution operator of a discrete–time quantum walk is quantified, using the von Neumann entropy of the reduced density operator (entropy of entanglement). In the case of a single walker, the entropy of entanglement converges, in the long time limit, to a well defined value which depends on the initial state. Exact expressions are obtained for local and non-local initial conditions. We also discuss the asymptotic bi-partite entanglement generated by non-separable coin operations for two coherent quantum walkers. In this case, the entropy of entanglement is observed to increase logarithmically with time. 1.

•Nov 21, 2012•2 citations

Two-particle quantum walks: Entanglement and graph isomorphism testing

Scott M. Berry, Jingbo B. Wang

We study discrete-time quantum walks on the line and on general undirected graphs with two interacting or noninteracting particles. We introduce two simple interaction schemes and show that they both lead to a diverse range of probability distributions that depend on the correlations and relative phases between the initial coin states of the two particles. We investigate the characteristics of these quantum walks and the time evolution of the entanglement between the two particles from both separable and entangled initial states. We also test the capability of two-particle discrete-time quantum walks to distinguish nonisomorphic graphs. For strongly regular graphs, we show that noninteracting discrete-time quantum walks can distinguish some but not all nonisomorphic graphs with the same family parameters. By incorporating an interaction between the two particles, all nonisomorphic strongly regular graphs tested are successfully distinguished.

Physical Review A•Apr 14, 2011•153 citations

Quantum walk search on the complete bipartite graph

Mason L. Rhodes, Thomas G. Wong

The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of $N$ vertices for one of $k$ marked vertices with different initial states. We prove an intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one time step to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches $1/2$, but if they are in different partite sets, it instead reaches 1. This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is $8/9$. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schr\"odinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.

arXiv:1812.06079•Physical Review A•Mar 1, 2019•31 citations

Quantum walk on the line: Entanglement and nonlocal initial conditions

Gonzalo Abal, R. Siri, A. Romanelli +1 more

The conditional shift in the evolution operator of a quantum walk generates entanglement between the coin and position degrees of freedom. This entanglement can be quantified by the von Neumman entropy of the reduced density operator (entropy of entanglement). We show analytically that for a Hadamard walk with local initial conditions the asymptotic entanglement is 0.872 for all initial coin states. When nonlocal initial conditions are considered, the asymptotic entanglement varies smoothly between almost complete entanglement and no entanglement (product state). An exact expression for the asymptotic (long-time) entanglement is obtained for initial conditions in the position subspace spanned by $\ensuremath{\mid}\ifmmode\pm\else\textpm\fi{}1⟩$.

arXiv:quant-ph/0507264•Physical Review A•Apr 4, 2006•113 citations
We define a two-particle quantum walk of identical particles on a graph GGG via the one-particle Grover walk on the Kronecker product G⊗GG \otimes GG⊗G, and call it the two-particle Grover walk. In systems of identical particles, quantum mechanics requires that quantum states have a certain invariance with respect to the exchange of particles. Focusing on the symmetry of the Kronecker product G⊗GG \otimes GG⊗G as a graph, we show that the time evolution operator of this walk commutes with the swap operator, which ensures that this requirement is satisfied. Furthermore, we study the entanglement entropy of quantum states evolved by this walk. For the complete bipartite graph Kn,nK_{n,n}Kn,n​, we completely determine the values of nnn for which the quantum states evolved from specific initial states attain the upper bound of the entropy at some time, and prove that they are exactly 111 and 222.
Quantum walks, both discrete (coined) and continuous time, form the basis of several recent quantum algorithms. Here we use numerical simulations to study the properties of discrete, coined quantum walks. We investigate the variation in the entanglement between the coin and the position of the particle by calculating the entropy of the reduced density matrix of the coin. We consider both dynamical evolution and asymptotic limits for coins of dimensions from two to eight on regular graphs. For low coin dimensions, quantum walks which spread faster (as measured by the mean square deviation of their distribution from uniform) also exhibit faster convergence towards the asymptotic value of the entanglement between the coin and particle's position. For high-dimensional coins, the DFT coin operator is more efficient at spreading than the Grover coin. We study the entanglement of the coin on regular finite graphs such as cycles, and also show that on complete bipartite graphs, a quantum walk with a Grover coin is always periodic with period four. We generalize the 'glued trees' graph used by Childs et al (2003 Proc. STOC , pp 59–68) to higher branching rate (fan out) and verify that the scaling with branching rate and with tree depth is polynomial.
We study the evolution of quantum correlations in two-particle discrete-time non-unitary quantum walks on a line with gain and loss. The two particles are initially prepared in a maximally entangled state and evolve independently. Using numerically exact calculations of position probability densities, average interparticle distance, entanglement entropy, and concurrence, we examine how dissipation and particle-exchange symmetry of the state (symmetric or antisymmetric) influence the resulting correlations. Notably, we find that the entanglement entropy of the antisymmetric state decays slower than that of the symmetric state at the exceptional point of the model. We also show that, in the antisymmetric state, the concurrence measured on the one-particle reduced density operator is unaffected by dissipation. Furthermore, we discuss how these correlations indicate quantum-to-classical transitions through the appearance of Gaussian position probability densities, sub-linear growth of average interparticle distance after a few steps, and decay of the entanglement entropy. On the other hand, the robustness of the qubit entanglement entropy can differentiate the model's topological phases better than in the one-particle quantum walk scenario.
Abstract. The coin-position entanglement generated by the evolution operator of a discrete–time quantum walk is quantified, using the von Neumann entropy of the reduced density operator (entropy of entanglement). In the case of a single walker, the entropy of entanglement converges, in the long time limit, to a well defined value which depends on the initial state. Exact expressions are obtained for local and non-local initial conditions. We also discuss the asymptotic bi-partite entanglement generated by non-separable coin operations for two coherent quantum walkers. In this case, the entropy of entanglement is observed to increase logarithmically with time. 1.
We study discrete-time quantum walks on the line and on general undirected graphs with two interacting or noninteracting particles. We introduce two simple interaction schemes and show that they both lead to a diverse range of probability distributions that depend on the correlations and relative phases between the initial coin states of the two particles. We investigate the characteristics of these quantum walks and the time evolution of the entanglement between the two particles from both separable and entangled initial states. We also test the capability of two-particle discrete-time quantum walks to distinguish nonisomorphic graphs. For strongly regular graphs, we show that noninteracting discrete-time quantum walks can distinguish some but not all nonisomorphic graphs with the same family parameters. By incorporating an interaction between the two particles, all nonisomorphic strongly regular graphs tested are successfully distinguished.
The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of NNN vertices for one of kkk marked vertices with different initial states. We prove an intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one time step to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches 1/21/21/2, but if they are in different partite sets, it instead reaches 1. This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is 8/98/98/9. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schr\"odinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.
The conditional shift in the evolution operator of a quantum walk generates entanglement between the coin and position degrees of freedom. This entanglement can be quantified by the von Neumman entropy of the reduced density operator (entropy of entanglement). We show analytically that for a Hadamard walk with local initial conditions the asymptotic entanglement is 0.872 for all initial coin states. When nonlocal initial conditions are considered, the asymptotic entanglement varies smoothly between almost complete entanglement and no entanglement (product state). An exact expression for the asymptotic (long-time) entanglement is obtained for initial conditions in the position subspace spanned by $\ensuremath{\mid}\ifmmode\pm\else\textpm\fi{}1⟩$.