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:2504.13000

Tree-Line graphs and their quantum walks

Musung Kang

Published Apr 17, 2025• 0 citations
arXivHTMLPDF

Abstract

For a simple graph $Γ$, a (bipartite)tree-line graph and a tree-graph of $Γ$ can be defined. With a (bipartite)tree-line graph constructed by the function $(b)\ell$, we study the continuous quantum walk on $(b)\ell ^n Γ$. An equitable partition of a bipartite tree-line graph is obtained by its corresponding derived tree graph. This paper also examines quantum walks on derived graphs, whose vertices represent their basis state.

DOI
10.48550/arxiv.2504.13000

Related papers

Quantum snake walk on graphs

Ansis Rosmanis

I introduce a continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. First, I analyze the quantum snake walk on the line, and I show that, even though most states stay localized throughout the evolution, there are specific states that most likely move on the line as wave packets with momentum inversely proportional to the length of the snake. Next, I discuss how an algorithm based on the quantum snake walk might potentially be able to solve an extended version of the glued trees problem, which asks to find a path connecting both roots of the glued trees graph. To the best of my knowledge, no efficient quantum algorithm solving this problem is known yet.

arXiv:1004.4054•Physical Review A•Feb 7, 2011•6 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

Scattering theory and quantum walks

Mark S. Hillery, Edgar Feldman

We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem

•Dec 8, 2003•0 citations

Finding tree symmetries using continuous-time quantum walk

Junjie Wu, Bai-Da Zhang, Yuhua Tang +2 more

Quantum walk, the quantum counterpart of random walk, is an important model and widely studied to develop new quantum algorithms. This paper studies the relationship between the continuous-time quantum walk and the symmetry of a graph, especially that of a tree. Firstly, we prove in mathematics that the symmetry of a graph is highly related to quantum walk. Secondly, we propose an algorithm based on the continuous-time quantum walk to compute the symmetry of a tree. Our algorithm has better time complexity O( N 3 ) than the current best algorithm. Finally, through testing three types of 10024 trees, we find that the symmetry of a tree can be found with an extremely high efficiency with the help of the continuous-time quantum walk.

Chinese Physics B•May 1, 2013•8 citations

Partition of graphs and quantum walk based search algorithms

Yusuke Ide

In this paper, we show reduction methods for search algorithms on graphs using quantum walks. By using a graph partitioning method called equitable partition for the the given graph, we determine “effective subspace” for the search algorithm to reduce the size of the problem. We introduce the equitable partition for quantum walk based search algorithms and show how to determine “effective subspace” and reduced operator.

arXiv:1812.06376•Nonlinear Theory and Its Applications IEICE•Dec 31, 2018•3 citations

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
For a simple graph ΓΓΓ, a (bipartite)tree-line graph and a tree-graph of ΓΓΓ can be defined. With a (bipartite)tree-line graph constructed by the function (b)ℓ(b)\ell(b)ℓ, we study the continuous quantum walk on (b)ℓnΓ(b)\ell ^n Γ(b)ℓnΓ. An equitable partition of a bipartite tree-line graph is obtained by its corresponding derived tree graph. This paper also examines quantum walks on derived graphs, whose vertices represent their basis state.
I introduce a continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. First, I analyze the quantum snake walk on the line, and I show that, even though most states stay localized throughout the evolution, there are specific states that most likely move on the line as wave packets with momentum inversely proportional to the length of the snake. Next, I discuss how an algorithm based on the quantum snake walk might potentially be able to solve an extended version of the glued trees problem, which asks to find a path connecting both roots of the glued trees graph. To the best of my knowledge, no efficient quantum algorithm solving this problem is known yet.
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.
We study quantum walks on general graphs from the point of view of scattering theory. For a general finite graph we choose two vertices and attach one half line to each. We are interested in walks that proceed from one half line, through the graph, to the other. The particle propagates freely on the half lines but is scattered at each vertex in the original graph. The probability of starting on one line and reaching the other after n steps can be expressed in terms of the transmission amplitude for the graph. An example is presented. Classical random walks on graphs can be used to construct algorithms that solve 2-SAT, graph connectivity problems, and for finding satsifying assignments for Boolean functions. A hope is that recently defined quantum walks will prove similarly useful in the development of quantum algorithms. In fact, it has recently been shown that it is possible to use a quantum walk to perform a search on the hypercube faster than can be done classically [1]. In this problem
Quantum walk, the quantum counterpart of random walk, is an important model and widely studied to develop new quantum algorithms. This paper studies the relationship between the continuous-time quantum walk and the symmetry of a graph, especially that of a tree. Firstly, we prove in mathematics that the symmetry of a graph is highly related to quantum walk. Secondly, we propose an algorithm based on the continuous-time quantum walk to compute the symmetry of a tree. Our algorithm has better time complexity O( N 3 ) than the current best algorithm. Finally, through testing three types of 10024 trees, we find that the symmetry of a tree can be found with an extremely high efficiency with the help of the continuous-time quantum walk.
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.