arXiv:1305.5811 · Algebraic Combinatorics

Complex Hadamard matrices, instantaneous uniform mixing and cubes

Ada Chan

Published Jun 2, 2020• 24 citations

Abstract

We study the continuous-time quantum walks on graphs in the adjacency algebra of the n -cube and its related distance regular graphs. For k ≥ 2 , we find graphs in the adjacency algebra of ( 2 k + 2 - 8 ) -cube that admit instantaneous uniform mixing at time π / 2 k and graphs that have perfect state transfer at time π / 2 k . We characterize the folded n -cubes, the halved n -cubes and the folded halved n -cubes whose adjacency algebra contains a complex Hadamard matrix. We obtain the same conditions for the characterization of these graphs admitting instantaneous uniform mixing.

DOI: 10.5802/alco.112

Related papers

Uniform Mixing and Association Schemes

Chris D. Godsil, Natalie Mullin, Aidan Roy

arXiv:1301.5889The Electronic Journal of CombinatoricsAug 11, 201717 citations

A note on graphs resistant to quantum uniform mixing

William Adamczak, Kevin Andrew, Peter Hernberg +1 more

arXiv:quant-ph/0308073Aug 13, 200314 citations

Moment Methods for Uniform Average Mixing on Strongly Regular Graphs

Musung Kang

quant-pharXiv:2610.10017Oct 8, 20260 citations

Perfect state transfer in products and covers of graphs

Gabriel Coutinho, Chris D. Godsil

arXiv:1501.04396Linear and Multilinear AlgebraApr 22, 201527 citations

Real State Transfer

Chris D. Godsil

arXiv:1710.04042Oct 11, 20174 citations

Selected open problems in continuous-time quantum walks

Gabriel Coutinho, Krystal Guo

Abstract Quantum walks on graphs are fundamental to quantum computing and have led to many interesting open problems in algebraic graph theory. This review article highlights three key classes of open problems in this domain: perfect state transfer, instantaneous uniform mixing, and average mixing matrices. In highlighting these open problems, our aim is to stimulate further research and exploration in this rapidly evolving field.

arXiv:2404.02236Special MatricesJan 1, 20243 citations

arXiv:1305.5811 · Algebraic Combinatorics

Complex Hadamard matrices, instantaneous uniform mixing and cubes

Ada Chan

Published Jun 2, 2020• 24 citations

arXiv HTML PDF

Abstract

DOI: 10.5802/alco.112

Related papers

Uniform Mixing and Association Schemes

Chris D. Godsil, Natalie Mullin, Aidan Roy

We consider continuous-time quantum walks on distance-regular graphs. Using results about the existence of complex Hadamard matrices in association schemes, we determine which of these graphs have quantum walks that admit uniform mixing.First we apply a result due to Chan to show that the only strongly regular graphs that admit instantaneous uniform mixing are the Paley graph of order nine and certain graphs corresponding to regular symmetric Hadamard matrices with constant diagonal. Next we prove that if uniform mixing occurs on a bipartite graph $X$ with $n$ vertices, then $n$ is divisible by four. We also prove that if $X$ is bipartite and regular, then $n$ is the sum of two integer squares. Our work on bipartite graphs implies that uniform mixing does not occur on $C_{2m}$ for $m \geq 3$ . Using a result of Haagerup, we show that uniform mixing does not occur on $C_p$ for any prime $p$ such that $p \geq 5$ . In contrast to this result, we see that $\epsilon$ -uniform mixing occurs on $C_p$ for all primes $p$ .We consider continuous-time quantum walks on distance-regular graphs. Using results about the existence of complex Hadamard matrices in association schemes, we determine which of these graphs have quantum walks that admit uniform mixing.First we apply a result due to Chan to show that the only strongly regular graphs that admit instantaneous uniform mixing are the Paley graph of order nine and certain graphs corresponding to regular symmetric Hadamard matrices with constant diagonal. Next we prove that if uniform mixing occurs on a bipartite graph $X$ with $n$ vertices, then $n$ is divisible by four. We also prove that if $X$ is bipartite and regular, then $n$ is the sum of two integer squares. Our work on bipartite graphs implies that uniform mixing does not occur on $C_{2m}$ for $m \geq 3$. Using a result of Haagerup, we show that uniform mixing does not occur on $C_p$ for any prime $p$ such that $p \geq 5$. In contrast to this result, we see that $\epsilon$-uniform mixing occurs on $C_p$ for all primes $p$.

arXiv:1301.5889The Electronic Journal of CombinatoricsAug 11, 201717 citations

A note on graphs resistant to quantum uniform mixing

William Adamczak, Kevin Andrew, Peter Hernberg +1 more

Continuous-time quantum walks on graphs is a generalization of continuous-time Markov chains on discrete structures. Moore and Russell proved that the continuous-time quantum walk on the $n$ -cube is instantaneous exactly uniform mixing but has no average mixing property. On complete (circulant) graphs $K_{n}$ , the continuous-time quantum walk is neither instantaneous (except for $n=2,3,4$ ) nor average uniform mixing (except for $n=2$ ). We explore two natural {\em group-theoretic} generalizations of the $n$ -cube as a $G$ -circulant and as a bunkbed $G \rtimes \Int_{2}$, where $G$ is a finite group. Analyses of these classes suggest that the $n$ -cube might be special in having instantaneous uniform mixing and that non-uniform average mixing is pervasive, i.e., no memoryless property for the average limiting distribution; an implication of these graphs having zero spectral gap. But on the bunkbeds, we note a memoryless property with respect to the two partitions. We also analyze average mixing on complete paths, where the spectral gaps are nonzero.Continuous-time quantum walks on graphs is a generalization of continuous-time Markov chains on discrete structures. Moore and Russell proved that the continuous-time quantum walk on the $n$-cube is instantaneous exactly uniform mixing but has no average mixing property. On complete (circulant) graphs $K_{n}$, the continuous-time quantum walk is neither instantaneous (except for $n=2,3,4$) nor average uniform mixing (except for $n=2$). We explore two natural {\em group-theoretic} generalizations of the $n$-cube as a $G$-circulant and as a bunkbed $G \rtimes \Int_{2}$, where $G$ is a finite group. Analyses of these classes suggest that the $n$-cube might be special in having instantaneous uniform mixing and that non-uniform average mixing is pervasive, i.e., no memoryless property for the average limiting distribution; an implication of these graphs having zero spectral gap. But on the bunkbeds, we note a memoryless property with respect to the two partitions. We also analyze average mixing on complete paths, where the spectral gaps are nonzero.

arXiv:quant-ph/0308073Aug 13, 200314 citations

Moment Methods for Uniform Average Mixing on Strongly Regular Graphs

Musung Kang

We study continuous-time quantum walks on connected strongly regular graphs that are not complete, observed at a random time drawn from a freely chosen probability law. Uniform average mixing (UAM) asks for a law under which every averaged transition probability equals $1/n$ , where $n$ is the number of vertices. On a strongly regular graph this is equivalent to two affine constraints on three cosine moments. We construct a bounded, compactly supported time density for every strongly regular graph with nonintegral eigenvalues. For integral spectra we give an exact finite Toeplitz criterion and its Hankel form. Every averaged mixing matrix of such a graph is realized by at most two observation times. Three elementary inequalities on the moment line, which also give a short proof of Chan's classification of complex Hadamard matrices in the Bose-Mesner algebra, lead to a determination of all strongly regular graphs that admit UAM. Apart from the conference graphs of nonsquare order and the graphs with instantaneous uniform mixing, these are the members of two infinite families of parameter sets and their complements, and for them we give explicit laws with two observation times. The Petersen graph and its complement are the smallest members. A strongly regular graph with UAM admits a bounded time density exactly when it has no instantaneous uniform mixing. We also correct the classification of instantaneous uniform mixing on strongly regular graphs by Godsil, Mullin and Roy. Its sign condition excludes the halved $5$ -cube, which mixes uniformly at time $π/4$ . With the order $4θ^2$ read literally, its parity condition also excludes the Clebsch graph and includes the parameters $(36,14,4,6)$ , for which no time law gives uniform average mixing.We study continuous-time quantum walks on connected strongly regular graphs that are not complete, observed at a random time drawn from a freely chosen probability law. Uniform average mixing (UAM) asks for a law under which every averaged transition probability equals $1/n$, where $n$ is the number of vertices. On a strongly regular graph this is equivalent to two affine constraints on three cosine moments. We construct a bounded, compactly supported time density for every strongly regular graph with nonintegral eigenvalues. For integral spectra we give an exact finite Toeplitz criterion and its Hankel form. Every averaged mixing matrix of such a graph is realized by at most two observation times. Three elementary inequalities on the moment line, which also give a short proof of Chan's classification of complex Hadamard matrices in the Bose-Mesner algebra, lead to a determination of all strongly regular graphs that admit UAM. Apart from the conference graphs of nonsquare order and the graphs with instantaneous uniform mixing, these are the members of two infinite families of parameter sets and their complements, and for them we give explicit laws with two observation times. The Petersen graph and its complement are the smallest members. A strongly regular graph with UAM admits a bounded time density exactly when it has no instantaneous uniform mixing. We also correct the classification of instantaneous uniform mixing on strongly regular graphs by Godsil, Mullin and Roy. Its sign condition excludes the halved $5$-cube, which mixes uniformly at time $π/4$. With the order $4θ^2$ read literally, its parity condition also excludes the Clebsch graph and includes the parameters $(36,14,4,6)$, for which no time law gives uniform average mixing.

quant-pharXiv:2610.10017Oct 8, 20260 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.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.04396Linear and Multilinear AlgebraApr 22, 201527 citations

Real State Transfer

Chris D. Godsil

A continuous quantum walk on a graph $X$ with adjacency matrix $A$ is specified by the 1-parameter family of unitary matrices $U(t)=\exp(itA)$ . These matrices act on the state space of a quantum system, the states of which we may represent by density matrices, positive semidefinite matrices with rows and columns indexed by $V(X)$ and with trace $1$ . The square of the absolute values of the entries of a column of $U(t)$ define a probability density on $V(X)$ , and it is precisely these densities that predict the outcomes of measurements. There are two special cases of physical interest: when the column density is supported on a vertex, and when it is uniform. In the first case we have perfect state transfer; in the second, uniform mixing. There are many results concerning state transfer and uniform mixing. In this paper we show that these results on perfect state transfer hold largely because at the time it occurs, the density matrix is real. We also show that the results on uniform mixing obtained so far hold because the entries of the density matrix are algebraic numbers. As a consequence of these we derive strong restrictions on the occurence of uniform mixing on bipartite graphs and on oriented graphs.A continuous quantum walk on a graph $X$ with adjacency matrix $A$ is specified by the 1-parameter family of unitary matrices $U(t)=\exp(itA)$. These matrices act on the state space of a quantum system, the states of which we may represent by density matrices, positive semidefinite matrices with rows and columns indexed by $V(X)$ and with trace $1$. The square of the absolute values of the entries of a column of $U(t)$ define a probability density on $V(X)$, and it is precisely these densities that predict the outcomes of measurements. There are two special cases of physical interest: when the column density is supported on a vertex, and when it is uniform. In the first case we have perfect state transfer; in the second, uniform mixing. There are many results concerning state transfer and uniform mixing. In this paper we show that these results on perfect state transfer hold largely because at the time it occurs, the density matrix is real. We also show that the results on uniform mixing obtained so far hold because the entries of the density matrix are algebraic numbers. As a consequence of these we derive strong restrictions on the occurence of uniform mixing on bipartite graphs and on oriented graphs.

arXiv:1710.04042Oct 11, 20174 citations

Selected open problems in continuous-time quantum walks

Gabriel Coutinho, Krystal Guo

arXiv:2404.02236Special MatricesJan 1, 20243 citations

X

with

n

vertices, then

n

is divisible by four. We also prove that if

X

is bipartite and regular, then

n

is the sum of two integer squares. Our work on bipartite graphs implies that uniform mixing does not occur on

C_{2m}

for

m \geq 3

. Using a result of Haagerup, we show that uniform mixing does not occur on

C_p

for any prime

p

such that

p \geq 5

. In contrast to this result, we see that

\epsilon

-uniform mixing occurs on

C_p

for all primes

p

Continuous-time quantum walks on graphs is a generalization of continuous-time Markov chains on discrete structures. Moore and Russell proved that the continuous-time quantum walk on the

n

-cube is instantaneous exactly uniform mixing but has no average mixing property. On complete (circulant) graphs

K_{n}

, the continuous-time quantum walk is neither instantaneous (except for

n=2,3,4

) nor average uniform mixing (except for

n=2

). We explore two natural {\em group-theoretic} generalizations of the

n

-cube as a

G

-circulant and as a bunkbed $G \rtimes \Int_{2}$, where

G

is a finite group. Analyses of these classes suggest that the

n

-cube might be special in having instantaneous uniform mixing and that non-uniform average mixing is pervasive, i.e., no memoryless property for the average limiting distribution; an implication of these graphs having zero spectral gap. But on the bunkbeds, we note a memoryless property with respect to the two partitions. We also analyze average mixing on complete paths, where the spectral gaps are nonzero.

1/n

, where

n

is the number of vertices. On a strongly regular graph this is equivalent to two affine constraints on three cosine moments. We construct a bounded, compactly supported time density for every strongly regular graph with nonintegral eigenvalues. For integral spectra we give an exact finite Toeplitz criterion and its Hankel form. Every averaged mixing matrix of such a graph is realized by at most two observation times. Three elementary inequalities on the moment line, which also give a short proof of Chan's classification of complex Hadamard matrices in the Bose-Mesner algebra, lead to a determination of all strongly regular graphs that admit UAM. Apart from the conference graphs of nonsquare order and the graphs with instantaneous uniform mixing, these are the members of two infinite families of parameter sets and their complements, and for them we give explicit laws with two observation times. The Petersen graph and its complement are the smallest members. A strongly regular graph with UAM admits a bounded time density exactly when it has no instantaneous uniform mixing. We also correct the classification of instantaneous uniform mixing on strongly regular graphs by Godsil, Mullin and Roy. Its sign condition excludes the halved

5

-cube, which mixes uniformly at time

π/4

. With the order

4θ^2

read literally, its parity condition also excludes the Clebsch graph and includes the parameters

(36,14,4,6)

, for which no time law gives uniform average mixing.

A continuous quantum walk on a graph

X

with adjacency matrix

A

is specified by the 1-parameter family of unitary matrices

U(t)=\exp(itA)

. These matrices act on the state space of a quantum system, the states of which we may represent by density matrices, positive semidefinite matrices with rows and columns indexed by

V(X)

and with trace

1

. The square of the absolute values of the entries of a column of

U(t)

define a probability density on

V(X)

, and it is precisely these densities that predict the outcomes of measurements. There are two special cases of physical interest: when the column density is supported on a vertex, and when it is uniform. In the first case we have perfect state transfer; in the second, uniform mixing. There are many results concerning state transfer and uniform mixing. In this paper we show that these results on perfect state transfer hold largely because at the time it occurs, the density matrix is real. We also show that the results on uniform mixing obtained so far hold because the entries of the density matrix are algebraic numbers. As a consequence of these we derive strong restrictions on the occurence of uniform mixing on bipartite graphs and on oriented graphs.