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

Algebraic Aspects of Multi-Particle Quantum Walks

Jamie Smith

Published Dec 4, 2012• 4 citations
OpenAlex

Abstract

A continuous time quantum walk consists of a particle moving among the vertices of a graph G. Its movement is governed by the structure of the graph. More formally, the adjacency matrix A is the Hamiltonian that determines the movement of our particle. Quantum walks have found a number of algorithmic applications, including unstructured search, element distinctness and Boolean formula evaluation. We will examine the properties of periodicity and state transfer. In particular, we will prove a result of the author along with Godsil, Kirkland and Severini, which states that pretty good state transfer occurs in a path of length n if and only if the n+1 is a power of two, a prime, or twice a prime. We will then examine the property of strong cospectrality, a necessary condition for pretty good state transfer from u to v. \n \nWe will then consider quantum walks involving more than one particle. In addition to moving around the graph, these particles interact when they encounter one another. Varying the nature of the interaction term gives rise to a range of different behaviours. We will introduce two graph invariants, one using a continuous-time multi-particle quantum walk, and the other using a discrete-time quantum walk. Using cellular algebras, we will prove several results which characterize the strength of these two graph invariants. \n \nLet A be an association scheme of n × n matrices. Then, any element of A can act on the space of n × n matrices by left multiplication, right multiplication, and Schur multiplication. The set containing these three linear mappings for all elements of A generates an algebra. This is an example of a Jaeger algebra. Although these algebras were initially developed by Francois Jaeger in the context of spin models and knot invariants, they prove to be useful in describing multi-particle walks as well. We will focus on triply-regular association schemes, proving several new results regarding the representation of their Jaeger algebras. As an example, we present the simple modules of a Jaeger algebra for the 4-cube.

Related papers

Quantum Walks and Pretty Good State transfer on Paths

van Bommel, Christopher Martin

Quantum computing is believed to provide many advantages over traditional computing, particularly considering the speed at which computations can be performed. One of the challenges that needs to be resolved in order to construct a quantum computer is the transmission of information from one part of the computer to another. Quantum walks, the quantum analogues of classical random walks, provide one potential method for resolving this challenge. \n \nIn this thesis, we use techniques from algebraic graph theory and number theory to analyze the mathematical model for continuous time quantum walks on graphs. For the continuous time quantum walk model, we define a transition operator, which is a function of a Hamiltonian. We focus on the cases where the adjacency matrix or the Laplacian of a graph act as the Hamiltionian. We mainly consider quantum walks on paths as a model for spin chains, which are the underlying basis of a quantum communication protocol. \n \nFor communication to be efficient, we desire states to be transferred with high fidelity, a measure of the amount of similarity between the transmitted state and the received state. At the maximum fidelity of 1, we say we have achieved perfect state transfer. Examples of perfect state transfer are relatively rare, so the concept of pretty good state transfer was introduced as a natural relaxation, which exists if fidelities arbitrarily close to 1 are obtained. \n \nOur first main result is to characterize pretty good state transfer on paths. Previously, pretty good state transfer on paths was considered mainly for the end vertices, though results for both models indicated that if there was pretty good state transfer between the end vertices, then there was pretty good state transfer between internal vertices equidistant from each end. We complete the characterization by demonstrating, for the adjacency matrix model, a family of paths where pretty good state transfer exists between internal vertices but not between end vertices, and verifying that no other example exists. For the Laplacian model, we show that there are no paths with pretty good state transfer between internal vertices but not between the end vertices. \n \nOur second main result considers initial states involving multiple vertices. Under the adjacency matrix model, we provide necessary and sufficient conditions for pretty good state transfer in a particular family of paths in terms of the eigenvalue support of the initial state. We also discuss recent results on fractional revival, which is another form of multiple qubit state transfer.

•Aug 23, 2019•3 citations

Irrational Quantum Walks

Gabriel Coutinho, Pedro Ferreira Baptista, Chris D. Godsil +2 more

Abstract. The adjacency matrix of a graph [Formula: see text] is the Hamiltonian for a continuous-time quantum walk on the vertices of [Formula: see text]. Although the entries of the adjacency matrix are integers, its eigenvalues are generally irrational and, because of this, the behavior of the walk is typically not periodic. In this paper, we develop a theory to exactly study any quantum walk generated by an integral Hamiltonian, and we put emphasis on those with irrational eigenvalues—what we call irrational quantum walks. As a result, we provide exact methods to compute the average of the mixing matrices, and to decide whether pretty good (or almost perfect) state transfer occurs in a given graph. We also use our methods to study geometric properties of beautiful curves arising from entries of the quantum walk matrix and discuss possible applications of these results. Throughout the paper, we emphasize the interplay between different fields of mathematics applied to the study of quantum walks.

arXiv:2208.08971•SIAM Journal on Applied Algebra and Geometry•Jul 25, 2023•5 citations

Quantum pure state transfer

Hermie Monterde

Quantum spin systems carry information in the form of quantum states, and the propagation of these quantum states is described by a quantum walk. In order to construct an operational quantum computer, the task of reliably transmitting quantum states from one part of a quantum computer to another must be accomplished. Quantum walks are known to be powerful tools in achieving this task. Pure states are quantum states represented by unit complex vectors. In this thesis, we use algebraic and combinatorial techniques to develop the theory of perfect state transfer on pure states in quantum walks, with emphasis on the adjacency and Laplacian matrices as Hamiltonians of a graph representing a spin network. We prove basic results about eigenvalue supports, periodicity, and strong cospectrality on pure states. We investigate a special type of strong cospectrality called m-strong cospectrality, and show that m-strongly cospectral pure states admit desirable quantum state transfer properties. Several characterisations of perfect state transfer are also given, one for general pure states, one for m-strongly pure states, and another one for real pure states. These characterisations give rise to algebraic and analytic properties of pure states admitting perfect state transfer. Moreover, we determine all complete graphs, complete bipartite graphs, cycles, and paths that admit perfect state transfer between m-strongly pure states. Constructions of infinite families of graphs admitting perfect state transfer are also given. We also characterise perfect state transfer between vertex states in joins and blowup graphs. We determine when the join operation preserves or induces perfect state transfer in the resulting graph. We also use blow-up graphs to construct new families of regular graphs with perfect state transfer. We use these two graph operations to demonstrate that graphs with perfect state transfer can be constructed from graphs that do not exhibit such a property. Finally, we investigate perfect state transfer on s-pair states – pure states that represent entanglement between two vertices. We establish combinatorial and spectral properties of s-pair states with perfect state transfer, and characterise its existence in complete graphs, complete bipartite graphs, paths and distance-regular graphs. Further, we construct infinite families of graphs with s-pair state transfer.

•Aug 14, 2025•0 citations

Cellular Algebras and Graph Invariants Based on Quantum Walks

Jamie Smith

We consider two graph invariants inspired by quantum walks- one in continuous time and one in discrete time. We will associate a matrix algebra called a cellular algebra with every graph. We show that, if the cellular algebras of two graphs have a similar structure, then they are not distinguished by either of the proposed invariants.

arXiv:1103.0262•Mar 1, 2011•2 citations

Quantum Walk Schemes for Universal Quantum Computation

Michael S. Underwood

Random walks are a powerful tool for the efficient implementation of algorithms in classical computation. Their quantum-mechanical analogues, called quantum walks, hold similar promise. Quantum walks provide a model of quantum computation that has recently been shown to be equivalent in power to the standard circuit model. As in the classical case, quantum walks take place on graphs and can undergo discrete or continuous evolution, though quantum evolution is unitary and therefore deterministic until a measurement is made. This thesis considers the usefulness of continuous-time quantum walks to quantum computation from the perspectives of both their fundamental power under various formulations, and their applicability in practical experiments. In one extant scheme, logical gates are effected by scattering processes. The results of an exhaustive search for single-qubit operations in this model are presented. It is shown that the number of distinct operations increases exponentially with the number of vertices in the scattering graph. A catalogue of all graphs on up to nine vertices that implement single-qubit unitaries at a specific set of momenta is included in an appendix. I develop a novel scheme for universal quantum computation called the discontinuous quantum walk, in which a continuous-time quantum walker takes discrete steps of evolution via perfect quantum state transfer through small `widget' graphs. The discontinuous quantum-walk scheme requires an exponentially sized graph, as do prior discrete and continuous schemes. To eliminate the inefficient vertex resource requirement, a computation scheme based on multiple discontinuous walkers is presented. In this model, n interacting walkers inhabiting a graph with 2n vertices can implement an arbitrary quantum computation on an input of length n, an exponential savings over previous universal quantum walk schemes. This is the first quantum walk scheme that allows for the application of quantum error correction. The many-particle quantum walk can be viewed as a single quantum walk undergoing perfect state transfer on a larger weighted graph, obtained via equitable partitioning. I extend this formalism to non-simple graphs. Examples of the application of equitable partitioning to the analysis of quantum walks and many-particle quantum systems are discussed.

•Jan 1, 2013•0 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 continuous time quantum walk consists of a particle moving among the vertices of a graph G. Its movement is governed by the structure of the graph. More formally, the adjacency matrix A is the Hamiltonian that determines the movement of our particle. Quantum walks have found a number of algorithmic applications, including unstructured search, element distinctness and Boolean formula evaluation. We will examine the properties of periodicity and state transfer. In particular, we will prove a result of the author along with Godsil, Kirkland and Severini, which states that pretty good state transfer occurs in a path of length n if and only if the n+1 is a power of two, a prime, or twice a prime. We will then examine the property of strong cospectrality, a necessary condition for pretty good state transfer from u to v. \n \nWe will then consider quantum walks involving more than one particle. In addition to moving around the graph, these particles interact when they encounter one another. Varying the nature of the interaction term gives rise to a range of different behaviours. We will introduce two graph invariants, one using a continuous-time multi-particle quantum walk, and the other using a discrete-time quantum walk. Using cellular algebras, we will prove several results which characterize the strength of these two graph invariants. \n \nLet A be an association scheme of n × n matrices. Then, any element of A can act on the space of n × n matrices by left multiplication, right multiplication, and Schur multiplication. The set containing these three linear mappings for all elements of A generates an algebra. This is an example of a Jaeger algebra. Although these algebras were initially developed by Francois Jaeger in the context of spin models and knot invariants, they prove to be useful in describing multi-particle walks as well. We will focus on triply-regular association schemes, proving several new results regarding the representation of their Jaeger algebras. As an example, we present the simple modules of a Jaeger algebra for the 4-cube.
Quantum computing is believed to provide many advantages over traditional computing, particularly considering the speed at which computations can be performed. One of the challenges that needs to be resolved in order to construct a quantum computer is the transmission of information from one part of the computer to another. Quantum walks, the quantum analogues of classical random walks, provide one potential method for resolving this challenge. \n \nIn this thesis, we use techniques from algebraic graph theory and number theory to analyze the mathematical model for continuous time quantum walks on graphs. For the continuous time quantum walk model, we define a transition operator, which is a function of a Hamiltonian. We focus on the cases where the adjacency matrix or the Laplacian of a graph act as the Hamiltionian. We mainly consider quantum walks on paths as a model for spin chains, which are the underlying basis of a quantum communication protocol. \n \nFor communication to be efficient, we desire states to be transferred with high fidelity, a measure of the amount of similarity between the transmitted state and the received state. At the maximum fidelity of 1, we say we have achieved perfect state transfer. Examples of perfect state transfer are relatively rare, so the concept of pretty good state transfer was introduced as a natural relaxation, which exists if fidelities arbitrarily close to 1 are obtained. \n \nOur first main result is to characterize pretty good state transfer on paths. Previously, pretty good state transfer on paths was considered mainly for the end vertices, though results for both models indicated that if there was pretty good state transfer between the end vertices, then there was pretty good state transfer between internal vertices equidistant from each end. We complete the characterization by demonstrating, for the adjacency matrix model, a family of paths where pretty good state transfer exists between internal vertices but not between end vertices, and verifying that no other example exists. For the Laplacian model, we show that there are no paths with pretty good state transfer between internal vertices but not between the end vertices. \n \nOur second main result considers initial states involving multiple vertices. Under the adjacency matrix model, we provide necessary and sufficient conditions for pretty good state transfer in a particular family of paths in terms of the eigenvalue support of the initial state. We also discuss recent results on fractional revival, which is another form of multiple qubit state transfer.
Abstract. The adjacency matrix of a graph [Formula: see text] is the Hamiltonian for a continuous-time quantum walk on the vertices of [Formula: see text]. Although the entries of the adjacency matrix are integers, its eigenvalues are generally irrational and, because of this, the behavior of the walk is typically not periodic. In this paper, we develop a theory to exactly study any quantum walk generated by an integral Hamiltonian, and we put emphasis on those with irrational eigenvalues—what we call irrational quantum walks. As a result, we provide exact methods to compute the average of the mixing matrices, and to decide whether pretty good (or almost perfect) state transfer occurs in a given graph. We also use our methods to study geometric properties of beautiful curves arising from entries of the quantum walk matrix and discuss possible applications of these results. Throughout the paper, we emphasize the interplay between different fields of mathematics applied to the study of quantum walks.
Quantum spin systems carry information in the form of quantum states, and the propagation of these quantum states is described by a quantum walk. In order to construct an operational quantum computer, the task of reliably transmitting quantum states from one part of a quantum computer to another must be accomplished. Quantum walks are known to be powerful tools in achieving this task. Pure states are quantum states represented by unit complex vectors. In this thesis, we use algebraic and combinatorial techniques to develop the theory of perfect state transfer on pure states in quantum walks, with emphasis on the adjacency and Laplacian matrices as Hamiltonians of a graph representing a spin network. We prove basic results about eigenvalue supports, periodicity, and strong cospectrality on pure states. We investigate a special type of strong cospectrality called m-strong cospectrality, and show that m-strongly cospectral pure states admit desirable quantum state transfer properties. Several characterisations of perfect state transfer are also given, one for general pure states, one for m-strongly pure states, and another one for real pure states. These characterisations give rise to algebraic and analytic properties of pure states admitting perfect state transfer. Moreover, we determine all complete graphs, complete bipartite graphs, cycles, and paths that admit perfect state transfer between m-strongly pure states. Constructions of infinite families of graphs admitting perfect state transfer are also given. We also characterise perfect state transfer between vertex states in joins and blowup graphs. We determine when the join operation preserves or induces perfect state transfer in the resulting graph. We also use blow-up graphs to construct new families of regular graphs with perfect state transfer. We use these two graph operations to demonstrate that graphs with perfect state transfer can be constructed from graphs that do not exhibit such a property. Finally, we investigate perfect state transfer on s-pair states – pure states that represent entanglement between two vertices. We establish combinatorial and spectral properties of s-pair states with perfect state transfer, and characterise its existence in complete graphs, complete bipartite graphs, paths and distance-regular graphs. Further, we construct infinite families of graphs with s-pair state transfer.
Random walks are a powerful tool for the efficient implementation of algorithms in classical computation. Their quantum-mechanical analogues, called quantum walks, hold similar promise. Quantum walks provide a model of quantum computation that has recently been shown to be equivalent in power to the standard circuit model. As in the classical case, quantum walks take place on graphs and can undergo discrete or continuous evolution, though quantum evolution is unitary and therefore deterministic until a measurement is made. This thesis considers the usefulness of continuous-time quantum walks to quantum computation from the perspectives of both their fundamental power under various formulations, and their applicability in practical experiments. In one extant scheme, logical gates are effected by scattering processes. The results of an exhaustive search for single-qubit operations in this model are presented. It is shown that the number of distinct operations increases exponentially with the number of vertices in the scattering graph. A catalogue of all graphs on up to nine vertices that implement single-qubit unitaries at a specific set of momenta is included in an appendix. I develop a novel scheme for universal quantum computation called the discontinuous quantum walk, in which a continuous-time quantum walker takes discrete steps of evolution via perfect quantum state transfer through small `widget' graphs. The discontinuous quantum-walk scheme requires an exponentially sized graph, as do prior discrete and continuous schemes. To eliminate the inefficient vertex resource requirement, a computation scheme based on multiple discontinuous walkers is presented. In this model, n interacting walkers inhabiting a graph with 2n vertices can implement an arbitrary quantum computation on an input of length n, an exponential savings over previous universal quantum walk schemes. This is the first quantum walk scheme that allows for the application of quantum error correction. The many-particle quantum walk can be viewed as a single quantum walk undergoing perfect state transfer on a larger weighted graph, obtained via equitable partitioning. I extend this formalism to non-simple graphs. Examples of the application of equitable partitioning to the analysis of quantum walks and many-particle quantum systems are discussed.
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.