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:1206.6298 · Physical Review A

Quantum walks as a probe of structural anomalies in graphs

Mark S. Hillery, Hongjun Zheng, Edgar Feldman, Daniel Reitzner, Vladimír Bužek

Published Jun 27, 2012• 24 citations
arXivHTMLPDF

Abstract

We study how quantum walks can be used to find structural anomalies in graphs via several examples. Two of our examples are based on star graphs, graphs with a single central vertex to which the other vertices, which we call external vertices, are connected by edges. In the basic star graph, these are the only edges. If we now connect a subset of the external vertices to form a complete subgraph, a quantum walk can be used to find these vertices with a quantum speedup. Thus, under some circumstances, a quantum walk can be used to locate where the connectivity of a network changes. We also look at the case of two stars connected at one of their external vertices. A quantum walk can find the vertex shared by both graphs, again with a quantum speedup. This provides an example of using a quantum walk in order to find where two networks are connected. Finally, we use a quantum walk on a complete bipartite graph to find an extra edge that destroys the bipartite nature of the graph.

DOI
10.1103/physreva.85.062325

Related papers

Finding structural anomalies in graphs by means of quantum walks

Edgar Feldman, Mark S. Hillery, Hai-Woong Lee +3 more

We explore the possibility of using quantum walks on graphs to find structural anomalies, such as extra edges or loops, on a graph. We focus our attention on star graphs, whose edges are like spokes coming out of a central hub. If there are $N$ spokes, we show that a quantum walk can find an extra edge connecting two of the spokes or a spoke with a loop on it in $O(\sqrt{N})$ steps. We initially find that if all except one of the spokes have loops, the walk will not find the spoke without a loop, but this can be fixed if we choose the phase with which the particle is reflected from the vertex without the loop. Consequently, quantum walks can, under some circumstances, be used to find structural anomalies in graphs.

arXiv:1009.0482•Physical Review A•Oct 6, 2010•33 citations

Finding structural anomalies in complete graphs using scattering quantum walks

Xiling Xue, Hanwu Chen, Zhihao Liu

The search for structural anomalies in a complete graph, [Formula: see text], using scattering quantum walks (SQWs) is investigated in this study. A complete graph with a second graph, [Formula: see text], attached to one of its vertices is referred to as external structural anomaly. The structural change within a complete graph is called internal structural anomaly. First, an example with [Formula: see text] being a triangle is presented to illustrate the problem. Then, a general proof is provided to show that the vertex to which [Formula: see text] is attached can be found in [Formula: see text] time steps as long as the connectivity between [Formula: see text] and [Formula: see text] is far less than [Formula: see text]. Finally, two types of internal structural anomalies, namely, a complete graph with a missing edge and that with an extra loop, are considered. These two anomalies can be solved in a similar manner as external anomalies in [Formula: see text] time steps. These examples demonstrate that Cottrell’s formalism in star graphs can be applied more generally.

International Journal of Quantum Information•Oct 1, 2016•3 citations

Finding Structural Anomalies in Star Graphs Using Quantum Walks

Seth Stannard Cottrell, Mark S. Hillery

We develop a general theory for a quantum-walk search on a star graph. A star graph has N edges each of which is attached to a central vertex. A graph G is attached to one of these edges, and we would like to find out to which edge it is attached. This is done by means of a quantum walk, a quantum version of a random walk. This walk contains O(sqrt[N]) steps, which represents a speedup over a classical search, which would require O(N) steps. The overall graph, star plus G, is divided into two parts, and we find that for a quantum speedup to occur, the eigenvalues associated with these two parts in the N→∞ limit must be the same. Our theory tells us how the initial state of the walk should be chosen, and how many steps the walk must make in order to find G.

arXiv:1310.3147•Physical Review Letters•Jan 23, 2014•23 citations

Search algorithm of structure anomalies in complete graph based on scattering quantum walk

Xiling Xue, Hanwu Chen, Zhihao Liu +1 more

Quantum walks have been proven to be a useful framework in designing new quantum algorithms, of which the search algorithm is the most notable. Besides a general search for a special vertex, recent researches have shown that quantum walks can also be used to find structural anomalies. Suppose a vertex of complete graph KN is attached to a second graph G, then the kind of structure anomaly will break the symmetry of the complete graph. The search algorithm based on scattering quantum walk model is presented to speed up locating this kind of structure anomaly. The concepts of scattering quantum walk model and collapsed graphs are presented. The definition of the evolutionary operator, which is different from that of a general search, is given. Based on the specific definition of evolutionary operator and the obvious symmetry of complete graph, it is shown that the search space is confined to a low-dimensional collapsed space, and the initial state is chosen to lie in this subspace. To illustrate the evolutionary process of the search algorithm, an example is given in the case that G is a single vertex. Taking advantage of our earlier study on the evolutionary operator of coined quantum walks with Grover coin, calculations of the unitary operator in the collapsed space are greatly simplified. To quantify the evolutionary process of the algorithm, we use the matrix perturbation theory involving a perturbative approach to find the eigenvalues and eigenstates. It is the degenerate zeroth-order eigenvalue 0 = 1 that leads to the interesting parts of the Hilbert space. Most of the recent researches of searching the structure anomalies focus on star graph SN with an unspecified graph G attached to one of its external vertices, where the overall graph is divided into two parts by the central vertex. It is shown that quantum speedup will occur if and only if the eigenvalues associated with these two parts in the N limit are the same. In this paper, we find that the collapsed graph of complete graphs can also be divided into two parts by a single collapsed vertex. As these two parts roughly correspond to the initial state and the desired state respectively, the techniques and results in star graphs can be generalized to the collapse graph on complete graph. What is more, under our definition of unitary evolution operator these two parts in the N limit will always share the same eigenvalue, i.e. 0 = 1, no matter what the structure of graph G is. Based on this, we prove that the search algorithm can find the target vertex in O(N) time steps with a success probability of 1-O(1N). That is to say, the quantum search algorithm gains a quadratic speedup over classical counterpart.

Acta Physica Sinica•Jan 1, 2016•5 citations

Finding more than one path through a simple maze with a quantum walk

Mark S. Hillery

Abstract We study quantum walks through chains consisting of two and three star graphs. The first star has a distinguished vertex labelled START and the last has one labelled END. There are multiple paths between these two vertices, and the object is to find these paths. We show that a quantum walk can do this with a quantum speedup.

arXiv:2007.07340•Journal of Physics A Mathematical and Theoretical•Jan 21, 2021•3 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
We study how quantum walks can be used to find structural anomalies in graphs via several examples. Two of our examples are based on star graphs, graphs with a single central vertex to which the other vertices, which we call external vertices, are connected by edges. In the basic star graph, these are the only edges. If we now connect a subset of the external vertices to form a complete subgraph, a quantum walk can be used to find these vertices with a quantum speedup. Thus, under some circumstances, a quantum walk can be used to locate where the connectivity of a network changes. We also look at the case of two stars connected at one of their external vertices. A quantum walk can find the vertex shared by both graphs, again with a quantum speedup. This provides an example of using a quantum walk in order to find where two networks are connected. Finally, we use a quantum walk on a complete bipartite graph to find an extra edge that destroys the bipartite nature of the graph.
We explore the possibility of using quantum walks on graphs to find structural anomalies, such as extra edges or loops, on a graph. We focus our attention on star graphs, whose edges are like spokes coming out of a central hub. If there are NNN spokes, we show that a quantum walk can find an extra edge connecting two of the spokes or a spoke with a loop on it in O(N)O(\sqrt{N})O(N​) steps. We initially find that if all except one of the spokes have loops, the walk will not find the spoke without a loop, but this can be fixed if we choose the phase with which the particle is reflected from the vertex without the loop. Consequently, quantum walks can, under some circumstances, be used to find structural anomalies in graphs.
The search for structural anomalies in a complete graph, [Formula: see text], using scattering quantum walks (SQWs) is investigated in this study. A complete graph with a second graph, [Formula: see text], attached to one of its vertices is referred to as external structural anomaly. The structural change within a complete graph is called internal structural anomaly. First, an example with [Formula: see text] being a triangle is presented to illustrate the problem. Then, a general proof is provided to show that the vertex to which [Formula: see text] is attached can be found in [Formula: see text] time steps as long as the connectivity between [Formula: see text] and [Formula: see text] is far less than [Formula: see text]. Finally, two types of internal structural anomalies, namely, a complete graph with a missing edge and that with an extra loop, are considered. These two anomalies can be solved in a similar manner as external anomalies in [Formula: see text] time steps. These examples demonstrate that Cottrell’s formalism in star graphs can be applied more generally.
We develop a general theory for a quantum-walk search on a star graph. A star graph has N edges each of which is attached to a central vertex. A graph G is attached to one of these edges, and we would like to find out to which edge it is attached. This is done by means of a quantum walk, a quantum version of a random walk. This walk contains O(sqrt[N]) steps, which represents a speedup over a classical search, which would require O(N) steps. The overall graph, star plus G, is divided into two parts, and we find that for a quantum speedup to occur, the eigenvalues associated with these two parts in the N→∞ limit must be the same. Our theory tells us how the initial state of the walk should be chosen, and how many steps the walk must make in order to find G.
Quantum walks have been proven to be a useful framework in designing new quantum algorithms, of which the search algorithm is the most notable. Besides a general search for a special vertex, recent researches have shown that quantum walks can also be used to find structural anomalies. Suppose a vertex of complete graph KN is attached to a second graph G, then the kind of structure anomaly will break the symmetry of the complete graph. The search algorithm based on scattering quantum walk model is presented to speed up locating this kind of structure anomaly. The concepts of scattering quantum walk model and collapsed graphs are presented. The definition of the evolutionary operator, which is different from that of a general search, is given. Based on the specific definition of evolutionary operator and the obvious symmetry of complete graph, it is shown that the search space is confined to a low-dimensional collapsed space, and the initial state is chosen to lie in this subspace. To illustrate the evolutionary process of the search algorithm, an example is given in the case that G is a single vertex. Taking advantage of our earlier study on the evolutionary operator of coined quantum walks with Grover coin, calculations of the unitary operator in the collapsed space are greatly simplified. To quantify the evolutionary process of the algorithm, we use the matrix perturbation theory involving a perturbative approach to find the eigenvalues and eigenstates. It is the degenerate zeroth-order eigenvalue 0 = 1 that leads to the interesting parts of the Hilbert space. Most of the recent researches of searching the structure anomalies focus on star graph SN with an unspecified graph G attached to one of its external vertices, where the overall graph is divided into two parts by the central vertex. It is shown that quantum speedup will occur if and only if the eigenvalues associated with these two parts in the N limit are the same. In this paper, we find that the collapsed graph of complete graphs can also be divided into two parts by a single collapsed vertex. As these two parts roughly correspond to the initial state and the desired state respectively, the techniques and results in star graphs can be generalized to the collapse graph on complete graph. What is more, under our definition of unitary evolution operator these two parts in the N limit will always share the same eigenvalue, i.e. 0 = 1, no matter what the structure of graph G is. Based on this, we prove that the search algorithm can find the target vertex in O(N) time steps with a success probability of 1-O(1N). That is to say, the quantum search algorithm gains a quadratic speedup over classical counterpart.
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.