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:2605.14640 · Journal of Physics A Mathematical and Theoretical

Perfect transmission and parallel composition for quantum walks on graphs with two leads

Allan John Gerrard, Ryo Asaka, Kazumitsu Sakai

quant-phmath-phSubmitted May 14, 2026• Announced May 15, 2026• 0 citations
arXivHTMLPDF

Abstract

We study scattering for continuous-time quantum walks on finite graphs with two attached leads. We derive explicit formulae for the two-terminal scattering matrix in terms of characteristic polynomials of the finite graph and its vertex-deleted subgraphs. For real-weighted two-terminal graphs, we then introduce three real quantities, $μ_1$, $μ_2$, and $ν$, which are each additive under parallel composition of graphs. In these variables, perfect transmission at fixed momentum is characterized by the condition $μ_1=μ_2$ together with a hyperbola in the corresponding $(μ,ν)$-plane, whose points determine the transmission phase. This turns the search for graphs with prescribed transmission properties into a geometric vector-sum problem for smaller building blocks.

Comments
20 pages

Related papers

Quantum scattering theory on graphs with tails

Martin Varbanov, Todd A. Brun

We consider continuous-time quantum walks on a finite graph to which infinite tails are attached. We explore how the propagating and bound states depend on the structure of the finite graph. The $S$ matrix for such graphs is defined. Its unitarity is proved as well as some other of its properties such as its transformation under time reversal. A spectral decomposition of the identity for the Hamiltonian of the graph is derived using its eigenvectors. We derive formulas for the $S$ matrix of a graph under certain operation such as cutting a tail, attaching a tail or connecting two tails to form an edge.

arXiv:0906.2825•Physical Review A•Nov 24, 2009•12 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

Quantum graph walks II: Quantum walks on graph coverings

Yusuke Higuchi, Norio Konno, Iwao Sato +1 more

We give a new determinant expression for the characteristic polynomial of the bond scattering matrix of a quantum graph G. Also, we give a decomposition formula for the characteristic polynomial of the bond scattering matrix of a regular covering of G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we express the characteristic polynomial of the bond scattering matrix of a regular covering of G by means of its L-functions. As an application, we introduce three types of quantum graph walks, and treat their relation.

arXiv:1211.4719•Nov 20, 2012•3 citations

Perfect state transfer in products and covers of graphs

Gabriel Coutinho, Chris D. Godsil

A continuous-time quantum walk on a graph is represented by the complex matrix , where is the adjacency matrix of and is a non-negative time. If the graph models a network of interacting qubits, transfer of state among such qubits throughout time can be formalized as the action of the continuous-time quantum walk operator in the characteristic vectors of the vertices. Here, we are concerned with the problem of determining which graphs admit a perfect transfer of state. More specifically, we will study graphs whose adjacency matrix is a sum of tensor products of -matrices, focusing on the case where a graph is the tensor product of two other graphs. As a result, we will construct many new examples of perfect state transfer.

arXiv:1501.04396•Linear and Multilinear Algebra•Apr 22, 2015•27 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 State Transfer in Graphs

Gabriel Coutinho

Let X be a graph, A its adjacency matrix, and t a non-negative real number. The matrix exp(i t A) determines the evolution in time of a certain quantum system defined on the graph. It represents a continuous-time quantum walk in X. We say that X admits perfect state transfer from a vertex u to a vertex v if there is a time t such that \n| exp(i t A)_(u,v) | = 1. \n \nThe main problem we study in this thesis is that of determining which simple graphs admit perfect state transfer. For some classes of graphs the problem is solved. For example, a path on n vertices admits perfect state transfer if and only if n=2 or n=3. However, the general problem of determining all graphs that admit perfect state transfer is substantially hard. \n \nIn this thesis, we focus on some special cases. We provide necessary and sufficient conditions for a distance-regular graph to admit perfect state transfer. In particular, we provide a detailed account of which distance-regular graphs of diameter three do so. \n \nA graph is said to be spectrally extremal if the number of distinct eigenvalues is equal to the diameter plus one. Distance-regular graphs are examples of such graphs. We study perfect state transfer in spectrally extremal graphs and explore rich connections to the topic of orthogonal polynomials. We characterize perfect state transfer in such graphs. \n \nWe also provide a general framework in which perfect state transfer in graph products can be studied. We use this to determine when direct products and double covers of graphs admit perfect state transfer. As a consequence, we provide many new examples of simple graphs admitting perfect state transfer. We also provide some advances in the understanding of perfect state transfer in Cayley graphs for the groups (Z_2)^d and Z_n. \n \nFinally, we consider the problem of determining which trees admit perfect state transfer. We show more generally that, except for the path on two vertices, if a connected bipartite graph contains a unique perfect matching, then it cannot admit perfect state transfer. We also consider this problem in the context of another model of quantum walks determined by the matrix exp(i t L), where L is the Laplacian matrix of the graph. In particular, we show that no tree on an odd number of vertices admits perfect state transfer according to this model.

•Aug 13, 2014•34 citations
We study scattering for continuous-time quantum walks on finite graphs with two attached leads. We derive explicit formulae for the two-terminal scattering matrix in terms of characteristic polynomials of the finite graph and its vertex-deleted subgraphs. For real-weighted two-terminal graphs, we then introduce three real quantities, μ1μ_1μ1​, μ2μ_2μ2​, and ννν, which are each additive under parallel composition of graphs. In these variables, perfect transmission at fixed momentum is characterized by the condition μ1=μ2μ_1=μ_2μ1​=μ2​ together with a hyperbola in the corresponding (μ,ν)(μ,ν)(μ,ν)-plane, whose points determine the transmission phase. This turns the search for graphs with prescribed transmission properties into a geometric vector-sum problem for smaller building blocks.
We consider continuous-time quantum walks on a finite graph to which infinite tails are attached. We explore how the propagating and bound states depend on the structure of the finite graph. The SSS matrix for such graphs is defined. Its unitarity is proved as well as some other of its properties such as its transformation under time reversal. A spectral decomposition of the identity for the Hamiltonian of the graph is derived using its eigenvectors. We derive formulas for the SSS matrix of a graph under certain operation such as cutting a tail, attaching a tail or connecting two tails to form an edge.
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 give a new determinant expression for the characteristic polynomial of the bond scattering matrix of a quantum graph G. Also, we give a decomposition formula for the characteristic polynomial of the bond scattering matrix of a regular covering of G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we express the characteristic polynomial of the bond scattering matrix of a regular covering of G by means of its L-functions. As an application, we introduce three types of quantum graph walks, and treat their relation.
A continuous-time quantum walk on a graph is represented by the complex matrix , where is the adjacency matrix of and is a non-negative time. If the graph models a network of interacting qubits, transfer of state among such qubits throughout time can be formalized as the action of the continuous-time quantum walk operator in the characteristic vectors of the vertices. Here, we are concerned with the problem of determining which graphs admit a perfect transfer of state. More specifically, we will study graphs whose adjacency matrix is a sum of tensor products of -matrices, focusing on the case where a graph is the tensor product of two other graphs. As a result, we will construct many new examples of perfect state transfer.
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.
Let X be a graph, A its adjacency matrix, and t a non-negative real number. The matrix exp(i t A) determines the evolution in time of a certain quantum system defined on the graph. It represents a continuous-time quantum walk in X. We say that X admits perfect state transfer from a vertex u to a vertex v if there is a time t such that \n| exp(i t A)_(u,v) | = 1. \n \nThe main problem we study in this thesis is that of determining which simple graphs admit perfect state transfer. For some classes of graphs the problem is solved. For example, a path on n vertices admits perfect state transfer if and only if n=2 or n=3. However, the general problem of determining all graphs that admit perfect state transfer is substantially hard. \n \nIn this thesis, we focus on some special cases. We provide necessary and sufficient conditions for a distance-regular graph to admit perfect state transfer. In particular, we provide a detailed account of which distance-regular graphs of diameter three do so. \n \nA graph is said to be spectrally extremal if the number of distinct eigenvalues is equal to the diameter plus one. Distance-regular graphs are examples of such graphs. We study perfect state transfer in spectrally extremal graphs and explore rich connections to the topic of orthogonal polynomials. We characterize perfect state transfer in such graphs. \n \nWe also provide a general framework in which perfect state transfer in graph products can be studied. We use this to determine when direct products and double covers of graphs admit perfect state transfer. As a consequence, we provide many new examples of simple graphs admitting perfect state transfer. We also provide some advances in the understanding of perfect state transfer in Cayley graphs for the groups (Z_2)^d and Z_n. \n \nFinally, we consider the problem of determining which trees admit perfect state transfer. We show more generally that, except for the path on two vertices, if a connected bipartite graph contains a unique perfect matching, then it cannot admit perfect state transfer. We also consider this problem in the context of another model of quantum walks determined by the matrix exp(i t L), where L is the Laplacian matrix of the graph. In particular, we show that no tree on an odd number of vertices admits perfect state transfer according to this model.