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:1805.02929 · Physical review. E

Interacting quantum walk on a graph

Alberto Verga

Published Jan 16, 2019• 9 citations
arXivHTMLPDF

Abstract

We introduce an elementary quantum system consisting of a set of spins on a graph and a particle hopping between its nodes. The quantum state is build sequentially, applying a unitary transformation that couples neighboring spins and, at each node, couples the local spin with the particle. We observe the relaxation of the system toward a stationary paramagnetic or ferromagnetic state and demonstrate that it is related to eigenvectors thermalization and random matrix statistics. The relation between these macroscopic properties and interaction generated entanglement is discussed.

DOI
10.1103/physreve.99.012127

Related papers

Quantum walk on a graph of spins: Magnetism and entanglement

Kevissen Sellapillay, Alberto Verga

We introduce a model of a quantum walk on a graph in which a particle jumps between neighboring nodes and interacts with independent spins sitting on the edges. Entanglement propagates with the walker. We apply this model to the case of a one-dimensional lattice to investigate its magnetic and entanglement properties. In the continuum limit, we recover a Landau-Lifshitz equation that describes the precession of spins. A rich dynamics is observed, with regimes of particle propagation and localization, together with spin oscillations and relaxation. Entanglement of the asymptotic states follows a volume law for most parameters (the coin rotation angle and the particle-spin coupling).

arXiv:2006.14883•Physical review. E•Mar 17, 2021•7 citations

Thermal state entanglement entropy on a quantum graph

Alberto Verga, Ricardo Gabriel Elías

A particle jumps between the nodes of a graph interacting with local spins. We show that the entanglement entropy of the particle with the spin network is related to the length of the minimum cycle basis. The structure of the thermal state is reminiscent of the string net of spin liquids.

arXiv:1909.00449•Physical review. E•Dec 26, 2019•5 citations

Characterizing the Relationship Between Unitary Quantum Walks and Non-Homogeneous Random Walks

Matheus Guedes de Andrade, Franklin de Lima Marquezino, Daniel R. Figueiredo

Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.

•Jun 29, 2021•0 citations

Sequentially generated entanglement, macroscopicity, and squeezing in a spin chain

Tahereh Abad, Klaus Mølmer, Vahid Karimipour

We study quantum states generated by a sequence of nearest neighbor bipartite entangling operations along a one-dimensional chain of spin qubits. After a single sweep of such a set of operations, the system is effectively described by a matrix product state (MPS) with the same virtual dimension as the spin qubits. We employ the explicit form of the MPS to calculate expectation values and two-site correlation functions of local observables, and we use the results to study fluctuations of collective observables. Through the so-called macroscopicity and the squeezing properties of the collective spin variables they witness the quantum correlations and multiparticle entanglement within the chain. Macroscopicity only occurs over the entire chain if the nearest neighbor interaction is maximally entangling, while a finite, sequential interaction between nearest neighbor particles leads to squeezing of the collective spin.

arXiv:1707.09396•Physical Review A•Oct 26, 2017•3 citations

Quantum State Diffusion on a Graph

John C Vining, Howard A. Blair

Quantum walks have frequently envisioned the behavior of a quantum state traversing a classically defined, generally finite, graph structure. While this approach has already generated significant results, it imposes a strong assumption: all nodes where the walker is not positioned are quiescent. This paper will examine some mathematical structures that underlie state diffusion on arbitrary graphs, that is the circulation of states within a graph. We will seek to frame the multi-walker problem as a finite quantum cellular automaton. Every vertex holds a walker at all times. The walkers will never collide and at each time step their positions update non-deterministically by a quantum swap of walkers at opposite ends of a randomly chosen edge. The update is accomplished by a unitary transformation of the position of a walker to a superposition of all such possible swaps and then performing a quantum measurement on the superposition of possible swaps. This behavior generates strong entanglement between vertex states which provides a path toward developing local actions producing diffusion throughout the graph without depending on the specific structure of the graph through blind computation.

arXiv:2405.16394•May 26, 2024•0 citations

Quantum walks on graphs

Dorit Aharonov, Andris Ambainis, Julia Kempe +1 more

We set the ground for a theory of quantum walks on graphs-the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.

ACM Symposium on Theory of Computing (STOC)•Jul 6, 2001•638 citations
We introduce an elementary quantum system consisting of a set of spins on a graph and a particle hopping between its nodes. The quantum state is build sequentially, applying a unitary transformation that couples neighboring spins and, at each node, couples the local spin with the particle. We observe the relaxation of the system toward a stationary paramagnetic or ferromagnetic state and demonstrate that it is related to eigenvectors thermalization and random matrix statistics. The relation between these macroscopic properties and interaction generated entanglement is discussed.
We introduce a model of a quantum walk on a graph in which a particle jumps between neighboring nodes and interacts with independent spins sitting on the edges. Entanglement propagates with the walker. We apply this model to the case of a one-dimensional lattice to investigate its magnetic and entanglement properties. In the continuum limit, we recover a Landau-Lifshitz equation that describes the precession of spins. A rich dynamics is observed, with regimes of particle propagation and localization, together with spin oscillations and relaxation. Entanglement of the asymptotic states follows a volume law for most parameters (the coin rotation angle and the particle-spin coupling).
Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.
We study quantum states generated by a sequence of nearest neighbor bipartite entangling operations along a one-dimensional chain of spin qubits. After a single sweep of such a set of operations, the system is effectively described by a matrix product state (MPS) with the same virtual dimension as the spin qubits. We employ the explicit form of the MPS to calculate expectation values and two-site correlation functions of local observables, and we use the results to study fluctuations of collective observables. Through the so-called macroscopicity and the squeezing properties of the collective spin variables they witness the quantum correlations and multiparticle entanglement within the chain. Macroscopicity only occurs over the entire chain if the nearest neighbor interaction is maximally entangling, while a finite, sequential interaction between nearest neighbor particles leads to squeezing of the collective spin.
Quantum walks have frequently envisioned the behavior of a quantum state traversing a classically defined, generally finite, graph structure. While this approach has already generated significant results, it imposes a strong assumption: all nodes where the walker is not positioned are quiescent. This paper will examine some mathematical structures that underlie state diffusion on arbitrary graphs, that is the circulation of states within a graph. We will seek to frame the multi-walker problem as a finite quantum cellular automaton. Every vertex holds a walker at all times. The walkers will never collide and at each time step their positions update non-deterministically by a quantum swap of walkers at opposite ends of a randomly chosen edge. The update is accomplished by a unitary transformation of the position of a walker to a superposition of all such possible swaps and then performing a quantum measurement on the superposition of possible swaps. This behavior generates strong entanglement between vertex states which provides a path toward developing local actions producing diffusion throughout the graph without depending on the specific structure of the graph through blind computation.
We set the ground for a theory of quantum walks on graphs-the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.