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

Finding structural anomalies in graphs by means of quantum walks

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

Published Oct 6, 2010• 33 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.82.040301

Related papers

Quantum walks as a probe of structural anomalies in graphs

Mark S. Hillery, Hongjun Zheng, Edgar Feldman +2 more

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.

arXiv:1206.6298•Physical Review A•Jun 27, 2012•24 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

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

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 paths with quantum walks or quantum walking through a maze

Daniel Reitzner, Mark S. Hillery, Daniel Koch

We show that it is possible to use a quantum walk to find a path from one marked vertex to another. In the specific case of $M$ stars connected in a chain, one can find the path from the first star to the last one in $O(M\sqrt{N})$ steps, where $N$ is the number of spokes of each star. First we provide an analytical result showing that by starting in a phase-modulated highly superposed initial state we can find the path in $O(M\sqrt{N}logM)$ steps. Next, we improve this efficiency by showing that the recovery of the path can also be performed by a series of successive searches when we start at the last known position and search for the next connection in $O(\sqrt{N})$ steps leading to the overall efficiency of $O(M\sqrt{N})$. For this result we use the analytical solution that can be obtained for a ring of stars of double the length of the chain.

arXiv:1707.01581•Physical Review A•Sep 13, 2017•13 citations

Finding structural anomalies in star graphs using quantum walks: a general approach

Seth Stannard Cottrell

In previous papers about searches on star graphs several patterns have been made apparent; the speed up only occurs when graphs are 'tuned' so that their time step operators have degenerate eigenvalues, and only certain initial states are effective. More than that, the searches are never faster than time. In this paper the problem is defined rigorously, the causes for all of these patterns are identified, sufficient and necessary conditions for quadratic-speed searches for any connected subgraph are demonstrated, the tolerance of these conditions is investigated, and it is shown that (unfortunately) we can do no better than time. Along the way, a useful formalism is established that may be useful in future work involving highly symmetric graphs.

arXiv:1404.5281•Journal of Physics A Mathematical and Theoretical•Dec 22, 2014•9 citations
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.
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 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.
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.
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.
We show that it is possible to use a quantum walk to find a path from one marked vertex to another. In the specific case of MMM stars connected in a chain, one can find the path from the first star to the last one in O(MN)O(M\sqrt{N})O(MN​) steps, where NNN is the number of spokes of each star. First we provide an analytical result showing that by starting in a phase-modulated highly superposed initial state we can find the path in O(MNlogM)O(M\sqrt{N}logM)O(MN​logM) steps. Next, we improve this efficiency by showing that the recovery of the path can also be performed by a series of successive searches when we start at the last known position and search for the next connection in O(N)O(\sqrt{N})O(N​) steps leading to the overall efficiency of O(MN)O(M\sqrt{N})O(MN​). For this result we use the analytical solution that can be obtained for a ring of stars of double the length of the chain.
In previous papers about searches on star graphs several patterns have been made apparent; the speed up only occurs when graphs are 'tuned' so that their time step operators have degenerate eigenvalues, and only certain initial states are effective. More than that, the searches are never faster than time. In this paper the problem is defined rigorously, the causes for all of these patterns are identified, sufficient and necessary conditions for quadratic-speed searches for any connected subgraph are demonstrated, the tolerance of these conditions is investigated, and it is shown that (unfortunately) we can do no better than time. Along the way, a useful formalism is established that may be useful in future work involving highly symmetric graphs.