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

Scattering theory and quantum walks

Mark S. Hillery, Edgar Feldman

Published Dec 8, 2003• 0 citations
OpenAlex

Abstract

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

Related papers

Quantum walks on graphs and quantum scattering theory

Edgar Feldman, Mark S. Hillery

We discuss a particular kind of quantum walk on a general graph. We affix two semi-infinite lines to a general finite graph, which we call tails. On the tails, the particle making the walk simply advances one unit at each time step, so that its behavior there is analogous to free propagation We are interested in how many steps it will take the particle, starting on one tail and propagating through the graph (where its propagation is not free), to emerge onto the other tail. The probability to make such a walk in n steps and the hitting time for such a walk can be expressed in terms of the transmission amplitude for the graph, which is one element of its S matrix. Demonstrating this necessitates a study of the analyticity properties of the transmission and reflection amplitudes of a graph. We show that the graph can have bound states that cannot be accessed by a particle entering the graph from one of its tails. Time-reversal invariance of a quantum walk is defined and used to show that the transmission amplitudes for the particle entering the graph from different directions are the same if the walk is time-reversal invariant.

arXiv:quant-ph/0403066•Mar 8, 2004•0 citations

Modifying quantum walks: a scattering theory approach

Edgar Feldman, Mark S. Hillery

We show how to construct discrete-time quantum walks on directed, Eulerian graphs. These graphs have tails on which the particle making the walk propagates freely, and this makes it possible to analyze the walks in terms of scattering theory. The probability of entering a graph from one tail and leaving from another can be found from the scattering matrix of the graph. We show how the scattering matrix of a graph that is an automorphic image of the original is related to the scattering matrix of the original graph, and we show how the scattering matrix of the reverse graph is related to that of the original graph. Modifications of graphs and the effects of these modifications are then considered. In particular we show how the scattering matrix of a graph is changed if we remove two tails and replace them with an edge or cut an edge and add two tails. This allows us to combine graphs, that is if we connect two graphs we can construct the scattering matrix of the combined graph from those of its parts. Finally, using these techniques, we show how two graphs can be compared by constructing a larger graph in which the two original graphs are in parallel, and performing a quantum walk on the larger graph. This is a kind of quantum walk interferometry.

arXiv:0705.4612•Journal of Physics A Mathematical and Theoretical•Aug 29, 2007•49 citations

Quantum random walk search on satisfiability problems

Stephan Hoyer

Using numerical simulation, we measured the performance of several potential quantum algorithms, based on quantum random walks, to solve Boolean satisfiability (SAT) problems. We develop the fundamentals of quantum computing and the theory of classical algorithms to indicate how these algorithms could be implemented. We also discuss the development of quantum random walks and the principles that go into creating them, presenting existing work on search algorithms using coined discrete-time quantum random walks. Although our quantum algorithms do not solve SAT problems faster than may be done classically, as a step toward that objective, we present the first example of a quantum walk on a directed graph that has a significant increase in speed over the analogous classical walk.

•Jan 1, 2008•6 citations

Scattering model for quantum random walks on a hypercube

Jozef Košík, Vladimír Bužek

Following a recent work by Hillery et al. [Phys. Rev. A 68, 032314 (2003)], we introduce a scattering model of a quantum random walk (SQRW) on a hybercube. We show that this type of quantum random walk can be reduced to the quantum random walk on the line and we derive the corresponding hitting amplitudes. We investigate the scattering properties of the hypercube, connected to the semi-infinite tails. We prove that the SQRW is a generalized version of the coined quantum random walk. We show how to implement the SQRW efficiently using a quantum circuit with standard gates. We discuss one possible version of a quantum search algorithm using the SQRW. Finally, we analyze symmetries that underlie the SQRW and may simplify its solution considerably.

arXiv:quant-ph/0410154•Physical Review A•Jan 4, 2005•23 citations

A simple method for finding the scattering coefficients of quantum graphs

Seth Stannard Cottrell

Quantum walks are roughly analogous to classical random walks, and similar to classical walks they have been used to find new (quantum) algorithms. When studying the behavior of large graphs or combinations of graphs, it is useful to find the response of a subgraph to signals of different frequencies. In doing so, we can replace an entire subgraph with a single vertex with variable scattering coefficients. In this paper, a simple technique for quickly finding the scattering coefficients of any discrete-time quantum graph will be presented. These scattering coefficients can be expressed entirely in terms of the characteristic polynomial of the graph’s time step operator. This is a marked improvement over previous techniques which have traditionally required finding eigenstates for a given eigenvalue, which is far more computationally costly. With the scattering coefficients we can easily derive the “impulse response” which is the key to predicting the response of a graph to any signal. This gives us a powerful set of tools for rapidly understanding the behavior of graphs or for reducing a large graph into its constituent subgraphs regardless of how they are connected.

arXiv:1503.00253•Journal of Mathematical Physics•Sep 1, 2015•9 citations

Quantum searches on highly symmetric graphs

Daniel Reitzner, Mark S. Hillery, Edgar Feldman +1 more

We study scattering quantum walks on highly symmetric graphs and use the walks to solve search problems on these graphs. The particle making the walk resides on the edges of the graph, and at each time step scatters at the vertices. All of the vertices have the same scattering properties except for a subset of special vertices. The object of the search is to find a special vertex. A quantum circuit implementation of these walks is presented in which the set of special vertices is specified by a quantum oracle. We consider the complete graph, a complete bipartite graph, and an $M$-partite graph. In all cases, the dimension of the Hilbert space in which the time evolution of the walk takes place is small (between three and six), so the walks can be completely analyzed analytically. Such dimensional reduction is due to the fact that these graphs have large automorphism groups. We find the usual quadratic quantum speedups in all cases considered.

arXiv:0805.1237•Physical Review A•Jan 26, 2009•72 citations
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
We discuss a particular kind of quantum walk on a general graph. We affix two semi-infinite lines to a general finite graph, which we call tails. On the tails, the particle making the walk simply advances one unit at each time step, so that its behavior there is analogous to free propagation We are interested in how many steps it will take the particle, starting on one tail and propagating through the graph (where its propagation is not free), to emerge onto the other tail. The probability to make such a walk in n steps and the hitting time for such a walk can be expressed in terms of the transmission amplitude for the graph, which is one element of its S matrix. Demonstrating this necessitates a study of the analyticity properties of the transmission and reflection amplitudes of a graph. We show that the graph can have bound states that cannot be accessed by a particle entering the graph from one of its tails. Time-reversal invariance of a quantum walk is defined and used to show that the transmission amplitudes for the particle entering the graph from different directions are the same if the walk is time-reversal invariant.
We show how to construct discrete-time quantum walks on directed, Eulerian graphs. These graphs have tails on which the particle making the walk propagates freely, and this makes it possible to analyze the walks in terms of scattering theory. The probability of entering a graph from one tail and leaving from another can be found from the scattering matrix of the graph. We show how the scattering matrix of a graph that is an automorphic image of the original is related to the scattering matrix of the original graph, and we show how the scattering matrix of the reverse graph is related to that of the original graph. Modifications of graphs and the effects of these modifications are then considered. In particular we show how the scattering matrix of a graph is changed if we remove two tails and replace them with an edge or cut an edge and add two tails. This allows us to combine graphs, that is if we connect two graphs we can construct the scattering matrix of the combined graph from those of its parts. Finally, using these techniques, we show how two graphs can be compared by constructing a larger graph in which the two original graphs are in parallel, and performing a quantum walk on the larger graph. This is a kind of quantum walk interferometry.
Using numerical simulation, we measured the performance of several potential quantum algorithms, based on quantum random walks, to solve Boolean satisfiability (SAT) problems. We develop the fundamentals of quantum computing and the theory of classical algorithms to indicate how these algorithms could be implemented. We also discuss the development of quantum random walks and the principles that go into creating them, presenting existing work on search algorithms using coined discrete-time quantum random walks. Although our quantum algorithms do not solve SAT problems faster than may be done classically, as a step toward that objective, we present the first example of a quantum walk on a directed graph that has a significant increase in speed over the analogous classical walk.
Following a recent work by Hillery et al. [Phys. Rev. A 68, 032314 (2003)], we introduce a scattering model of a quantum random walk (SQRW) on a hybercube. We show that this type of quantum random walk can be reduced to the quantum random walk on the line and we derive the corresponding hitting amplitudes. We investigate the scattering properties of the hypercube, connected to the semi-infinite tails. We prove that the SQRW is a generalized version of the coined quantum random walk. We show how to implement the SQRW efficiently using a quantum circuit with standard gates. We discuss one possible version of a quantum search algorithm using the SQRW. Finally, we analyze symmetries that underlie the SQRW and may simplify its solution considerably.
Quantum walks are roughly analogous to classical random walks, and similar to classical walks they have been used to find new (quantum) algorithms. When studying the behavior of large graphs or combinations of graphs, it is useful to find the response of a subgraph to signals of different frequencies. In doing so, we can replace an entire subgraph with a single vertex with variable scattering coefficients. In this paper, a simple technique for quickly finding the scattering coefficients of any discrete-time quantum graph will be presented. These scattering coefficients can be expressed entirely in terms of the characteristic polynomial of the graph’s time step operator. This is a marked improvement over previous techniques which have traditionally required finding eigenstates for a given eigenvalue, which is far more computationally costly. With the scattering coefficients we can easily derive the “impulse response” which is the key to predicting the response of a graph to any signal. This gives us a powerful set of tools for rapidly understanding the behavior of graphs or for reducing a large graph into its constituent subgraphs regardless of how they are connected.
We study scattering quantum walks on highly symmetric graphs and use the walks to solve search problems on these graphs. The particle making the walk resides on the edges of the graph, and at each time step scatters at the vertices. All of the vertices have the same scattering properties except for a subset of special vertices. The object of the search is to find a special vertex. A quantum circuit implementation of these walks is presented in which the set of special vertices is specified by a quantum oracle. We consider the complete graph, a complete bipartite graph, and an MMM-partite graph. In all cases, the dimension of the Hilbert space in which the time evolution of the walk takes place is small (between three and six), so the walks can be completely analyzed analytically. Such dimensional reduction is due to the fact that these graphs have large automorphism groups. We find the usual quadratic quantum speedups in all cases considered.