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:1103.0262

Cellular Algebras and Graph Invariants Based on Quantum Walks

Jamie Smith

Published Mar 1, 2011• 2 citations
arXivHTMLPDF

Abstract

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.
DOI
10.48550/arxiv.1103.0262

Related papers

Algebraic Aspects of Multi-Particle Quantum Walks

Jamie Smith

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.

•Dec 4, 2012•4 citations

k-Boson Quantum Walks Do Not Distinguish Arbitrary Graphs

Jamie Smith

In this paper, we define k-equivalence, a relation on graphs that relies on their associated cellular algebras. We show that a k-Boson quantum walk cannot distinguish pairs of graphs that are k- equivalent. The existence of pairs of k-equivalent graphs has been shown by Ponomarenko et al. [2, 6]. This gives a negative answer to a question posed by Gamble et al. [7].

arXiv:1004.0206•Apr 1, 2010•9 citations

Connection Between Continuous and Discrete Time Quantum Walks on d-Dimensional Lattices; Extensions to General Graphs

I obtain the dynamics of the continuous time quantum walk on a d-dimensional lattice, with periodic boundary conditions, as an appropriate limit of the dynamics of the discrete time quantum walk on the same lattice. This extends the main result of [8] which proved this limit for the case of the quantum walk on the infinite line and the quantum cellular automaton proposed in [1]. By highlighting the main features of the limiting procedure, I then extend it to general graphs. For a given discrete time quantum walk on a general graph, I single out the type of continuous dynamics (Hamiltonians) that can be obtained as a limit of the discrete time dynamics. 1 Generalities on quantum walks; continuous and discrete time Consider a graph G: = {V, E} with a set of vertices V of cardinality N and a set of edges E. We assume G to be undirected and without self-loops. In the interval of time ∆t a certain fraction γ∆t of a quantity pj leaves the location of the j-th vertex to move to a neighboring vertex k. The quantity pj, j = 1,..., N, at time t + ∆t is given by 1 pj(t + ∆t) = pj(t) − deg (j)γ∆tpj(t) + ∑ (k,j)∈E γ∆tpk(t). (1) Define ⃗p the N−vector whose components are the pj’s quantities, and L the Laplacian matrix defined by Ljj = − deg (j), Ljk = 1 if (j, k) ∈ E and Ljk = 0 otherwise. L is

•Jan 1, 2009•11 citations

Discrete Time Quantum Lattice Systems

Holger Vogts

Discrete time quantum lattice systems recently have come into the focus of quantum computation because they provide a versatile tool for many different applications and they are potentially implementable in current experimental realizations. In this thesis we study the fundamental structures of such quantum lattice systems as well as consequences of experimental imperfections. Essentially, there are two models of discrete time quantum lattice systems, namely quantum cellular automata and quantum walks, which are quantum versions of their classical counterparts, i.e., cellular automata and random walks. In both cases, the dynamics acts locally on the lattice and is usually also translationally invariant. The main difference between these structures is that quantum cellular automata can describe the dynamics of many interacting particles, where quantum walks describe the evolution of a single particle. The first part of this thesis is devoted to quantum cellular automata. We characterize one-dimensional quantum cellular automata in terms of an index theory up to local deformations. Further, we characterize in detail a subclass of quantum cellular automata by requiring that Pauli operators are mapped to Pauli operators. This structure can be understood in terms of certain classical cellular automata. The second part of this thesis is concerned with quantum walks. We identify a quantum walk with the one-particle sector of a quantum cellular automaton. We also establish an index theory for quantum walks and we discuss decoherent quantum walks, i.e., the behavior of quantum walks with experimental imperfections.

•Jun 25, 2009•6 citations

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

Factoring Discrete Quantum Walks on Distance Regular Graphs into Continuous Quantum Walks

Hanmeng Zhan

We consider a discrete-time quantum walk, called the Grover walk, on a distance regular graph $X$. Given that $X$ has diameter $d$ and invertible adjacency matrix, we show that the square of the transition matrix of the Grover walk on $X$ is a product of at most $d$ commuting transition matrices of continuous-time quantum walks, each on some distance digraph of the line digraph of $X$. We also obtain a similar factorization for any graph $X$ in a Bose Mesner algebra.

arXiv:2008.01224•Aug 3, 2020•0 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.
I obtain the dynamics of the continuous time quantum walk on a d-dimensional lattice, with periodic boundary conditions, as an appropriate limit of the dynamics of the discrete time quantum walk on the same lattice. This extends the main result of [8] which proved this limit for the case of the quantum walk on the infinite line and the quantum cellular automaton proposed in [1]. By highlighting the main features of the limiting procedure, I then extend it to general graphs. For a given discrete time quantum walk on a general graph, I single out the type of continuous dynamics (Hamiltonians) that can be obtained as a limit of the discrete time dynamics. 1 Generalities on quantum walks; continuous and discrete time Consider a graph G: = {V, E} with a set of vertices V of cardinality N and a set of edges E. We assume G to be undirected and without self-loops. In the interval of time ∆t a certain fraction γ∆t of a quantity pj leaves the location of the j-th vertex to move to a neighboring vertex k. The quantity pj, j = 1,..., N, at time t + ∆t is given by 1 pj(t + ∆t) = pj(t) − deg (j)γ∆tpj(t) + ∑ (k,j)∈E γ∆tpk(t). (1) Define ⃗p the N−vector whose components are the pj’s quantities, and L the Laplacian matrix defined by Ljj = − deg (j), Ljk = 1 if (j, k) ∈ E and Ljk = 0 otherwise. L is
Discrete time quantum lattice systems recently have come into the focus of quantum computation because they provide a versatile tool for many different applications and they are potentially implementable in current experimental realizations. In this thesis we study the fundamental structures of such quantum lattice systems as well as consequences of experimental imperfections. Essentially, there are two models of discrete time quantum lattice systems, namely quantum cellular automata and quantum walks, which are quantum versions of their classical counterparts, i.e., cellular automata and random walks. In both cases, the dynamics acts locally on the lattice and is usually also translationally invariant. The main difference between these structures is that quantum cellular automata can describe the dynamics of many interacting particles, where quantum walks describe the evolution of a single particle. The first part of this thesis is devoted to quantum cellular automata. We characterize one-dimensional quantum cellular automata in terms of an index theory up to local deformations. Further, we characterize in detail a subclass of quantum cellular automata by requiring that Pauli operators are mapped to Pauli operators. This structure can be understood in terms of certain classical cellular automata. The second part of this thesis is concerned with quantum walks. We identify a quantum walk with the one-particle sector of a quantum cellular automaton. We also establish an index theory for quantum walks and we discuss decoherent quantum walks, i.e., the behavior of quantum walks with experimental imperfections.
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 consider a discrete-time quantum walk, called the Grover walk, on a distance regular graph XXX. Given that XXX has diameter ddd and invertible adjacency matrix, we show that the square of the transition matrix of the Grover walk on XXX is a product of at most ddd commuting transition matrices of continuous-time quantum walks, each on some distance digraph of the line digraph of XXX. We also obtain a similar factorization for any graph XXX in a Bose Mesner algebra.