\documentclass[11pt, a4paper]{article} % FILE: notes.tex % Written by Samuel L. Braunstein % To add notes to an article at the proof stage: % Right after \draft, or \begin{document} % % \input notes % Reads in this macro package. % \shownotes % Turns the notes ON. % % If the command "\shownotes" % % is commented out the notes % % will NOT appear in the output. % ... % % % Then anywhere in the file % % add notes with the following % % command: % % \notes{This is my note to myself ... } % % include multiline notes too. % \notes{This is another note with a displayed equation inside it: % $$ % {\rm time} = {\rm money} \;. % $$ % Hey, this is fun! % } % Don't forget to end the note! % % \notesbullet{text} % Is like \notes except that % % it produces normal sized notes. % % Bugs: multi-paragraph notes are NOT allowed. % THIS MEANS YOU MUST NOT LEAVE BLANK LINES IN A NOTE!!!!! % G O T T H E M E S S A G E ? % \font\manual=manfnt \def\dbend{{\manual\char127}} \let\writenotes=F \def\notes#1{\if T\writenotes \begin{itemize} \small \baselineskip 1.3em %9pt \item[\dbend] #1 \end{itemize} \fi} \def\notesbullet#1{\if T\writenotes \begin{itemize} %\small \baselineskip 1.3em \item[$\bullet$] #1 \end{itemize} \fi} \def\shownotes{\global\let\writenotes=T} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % USEFUL FOR TWOCOLUMN MODE OF LATEX %In REVTeX after \title; \author; % you may use: %\newdate{\DMYtoday} %\newabstract{Each paragraph separated\newline %\newline %By newlines} %\newpacs{PACS number(s): 03.65.Bz ...} \def\newdate#1{\address{\rm (#1)}} \def\newabstract#1{\author{% \leftskip=0.10753\textwidth \rightskip\leftskip \parindent 1em\indent #1 \newline}} \def\newpacs#1{\address{\leftskip=0.10753\textwidth \rightskip\leftskip \rm #1 \newline}} \def\DMYtoday{\number\day \space\ifcase\month\or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \space\number\year} \usepackage{epsf} \usepackage{amsmath} \usepackage{amssymb} \usepackage{latexsym} \usepackage{psfrag} \usepackage{graphics} \usepackage{epsfig} \usepackage{listings} \usepackage[usenames]{color} \definecolor{subtlegrey}{rgb}{0.92,0.92,0.92} \definecolor{darkgreen}{rgb}{0,0.5,0} \lstdefinelanguage{CSharp}{ morecomment = [l]{//}, morecomment = [l]{///}, morecomment = [s]{/*}{*/}, morestring=[b]", sensitive = true, morekeywords = {abstract, event, new, struct, as, explicit, null, switch, base, extern, object, this, bool, false, operator, throw, break, finally, out, true, byte, fixed, override, try, case, float, params, typeof, catch, for, private, uint, char, foreach, protected, ulong, checked, goto, public, unchecked, class, if, readonly, unsafe, const, implicit, ref, ushort, continue, in, return, using, decimal, int, sbyte, virtual, default, interface, sealed, volatile, delegate, internal, short, void, do, is, sizeof, while, double, lock, stackalloc, else, long, static, enum, namespace, string}} \lstset{ language=CSharp, %basicstyle=\ttfamily, % print whole listing in tt basicstyle=\ttfamily\footnotesize, %keywordstyle={}, % do not highlight keywords % identifierstyle=\slshape, % macros that are not keywords, args commentstyle=\rmfamily\itshape % italic comments % stringstyle=\ttfamily, % typewriter type for strings % texcsstyle=\slshape, } \lstset{keywordstyle=\color{darkgreen}} \setlength{\parindent}{0pt} \setlength{\textwidth}{16.5cm} \setlength{\textheight}{24.5cm} \setlength{\topmargin}{0cm} \setlength{\headheight}{0cm} \setlength{\headsep}{0cm} \setlength{\topskip}{0cm} \setlength{\leftmargin}{0cm} \setlength{\baselineskip}{15pt} \addtolength{\oddsidemargin}{-1.5cm} \newtheorem{theo}{Theorem}[section] \newtheorem{prop}[theo]{Proposition} \newtheorem{lemma}[theo]{Lemma} \newtheorem{defn}[theo]{Definition} \newtheorem{exam}[theo]{Example} \newtheorem{examples}[theo]{Examples} \newtheorem{cl}[theo]{Claim} \newtheorem{exercise}[theo]{Exercise} \newtheorem{exercises}[theo]{Exercises} \newtheorem{claim}[theo]{Claim} \newtheorem{corollary}[theo]{Corollary} \newtheorem{conjecture}[theo]{Conjecture} \newtheorem{conjprop}[theo]{Conjectured Proposition} \newenvironment{ex}{\begin{exam}\rm}{\end{exam}} \newenvironment{exs}{\begin{examples}\rm}{\end{examples}} \newenvironment{exc}{\begin{exercise}\rm}{\end{exercise}} \newenvironment{excs}{\begin{exercises}\rm}{\end{exercises}} \newenvironment{pf}{{\em Proof.}}{$\Box$} \newenvironment{sk}{{\em Sketch Proof.}}{$\Box$} \newenvironment{vpf}{{\em Proof}}{$\Box$} \newenvironment{note}{{\bf Note. }\small}{\normalsize} \newenvironment{comment}{{$\triangle$ }\small}{\normalsize} \newenvironment{abs}{{\bf Abstract. }\small}{\normalsize} \newenvironment{question}{{\bf Question. }\small}{\normalsize} \newcommand{\nc}{\newcommand} %% Blackboard Fonts \nc{\real}{{\mathbb R}} %% Real Numbers \nc{\z}{{\mathbb Z}} %% Integers \nc{\nat}{{\mathbb N}} %% Natural Numbers \nc{\q}{{\mathbb Q}} %% Rational Numbers \nc{\h}{{\mathbb H}} %% Hyperbolic Space \nc{\p}{{\mathbb P}} %% Projective Space \nc{\co}{{\mathbb C}} %% Complex numbers %% Matrices \nc{\tr}{\mbox{tr}} %% Lower case trace \nc{\Tr}{\mbox{Tr}} %% Upper case trace %% Miscellaneous \nc{\defi}{\mbox{def}} %% For use in =def \nc{\ep}{\varepsilon} %% Shorthand for epsilon \nc{\half}{\frac{1}{2}} \nc{\bl}{\vspace{2mm}\\} %% Blank Line \nc{\lte}{\leqslant} %% Less than or equal to \nc{\gte}{\geqslant} %% Greater than or equal to \nc{\ltec}{\preceq} %% lte curly (for posets) \nc{\gtec}{\succeq} %% gte curly (for posets) \nc{\ltc}{\prec} %% less than curly \nc{\gtc}{\succ} %% greater than curly \nc{\pmd}{^{\prime}} %% Primed \nc{\pmmd}{^{\prime\prime}} %% Double primed \nc{\ppmd}{^{\prime\prime}} %% Alternative abbreviation \nc{\ra}{\rightarrow} %% Arrow pointing right, e.g. definition of a map \nc{\bks}{\backslash} %\nc{\implies}{\Rightarrow} \nc{\rank}{\mbox{rank}} \nc{\Min}{\mbox{Min}} %% Capital min \nc{\lcm}{\mbox{lcm}} %% Lowest common multiple %\nc{\mod}{\mbox{mod}} \nc{\modn}{\mbox{ }\mod \mbox{ } n} \nc{\Hull}{\mbox{Hull}} \nc{\sgn}{\mbox{sgn}} \nc{\hcf}{\mbox{hcf}} % highest common factor %% MSc dissertation and Canonical Representatives %% in geometric group theory notes \nc{\diff}{\mbox{diff}} \nc{\slice}{\mbox{slice}} \nc{\diam}{\mbox{diam}} \nc{\ce}{\mbox{ce}} \nc{\st}{\mbox{st}} \nc{\Ca}{\mbox{Ca}} \nc{\con}{\mbox{con}} \nc{\State}{\mbox{State}} \nc{\DState}{\mbox{DState}} \nc{\exce}{\mbox{exc}} %% Geometric group theory notes \nc{\cone}{\mbox{Con}} \nc{\Con}{\cone} \nc{\asdim}{\mbox{asdim}} \nc{\dis}{\mbox{dis}} \nc{\Cc}{\mbox{Cc}} \nc{\PD}{\mbox{PD}} \nc{\cd}{\mbox{cd}} \nc{\chr}{\mbox{char}} \nc{\Diffeos}{\mbox{Diffeos}} \nc{\Fix}{\mbox{Fix}} \nc{\Fx}{\mbox{Fix}} \nc{\Eq}{\mbox{Eq}} \nc{\Ends}{\mbox{ends}} \nc{\Vol}{\mbox{Vol}} \nc{\Mon}{\mbox{Mon}} \nc{\WCH}{\mbox{WCH}} %% Analysis Notes \nc{\Iso}{\mbox{Iso}} %% Isometry group of a metric space \nc{\Int}{\mbox{Int}} \nc{\inter}{\mbox{Int}} %% Local \nc{\OS}{\mbox{OS}} \nc{\IS}{\mbox{IS}} \nc{\bool}{\mathbb{B}} \nc{\two}{{\bf 2}} \nc{\prob}{\mathbb{P}} \nc{\comp}{\mathbb{C}} %\nc{\quzero}{|0\rangle} %\nc{\quone}{|1\rangle} \nc{\tens}{\otimes} \nc{\zvect}{\underline{0}} \nc{\QFT}{\mbox{QFT}} \nc{\qf}{{\cal F}} \def \ket#1{|#1\rangle} \def \bra#1{\langle#1|} \def \set#1{\{#1\}} \def \quzero {\ket{0}} \def \quone {\ket{1}} \def \sgp#1{\langle#1\rangle} \def \ip#1{\langle#1\rangle} \def \pres#1{\langle#1\rangle} \def \C {{\bf C}} \def \Z {{\mathbb Z}} \def \R {{\mathbb R}} \def \eqdefn{=^{\rm defn}} \begin{document} \shownotes \begin{center} {\large \bf Quantum Walks with Memory on Groups} \end{center} \begin{center} {\large Michael Batty and Michael McGettrick} \end{center} \begin{center} {\large \today} \end{center} \begin{abstract} We investigate the analogue of a recently studied quantum walk with memory in the context of a finite cyclic group. We show that something or other happens, and that it is very interesting (!!) \end{abstract} \section{Introduction} McGettrick \cite{mcgettrick} has studied the one dimensional quantum Hadamard walk with memory given by the equations \begin{eqnarray*} \ket{n-1,n,0} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n,n-1,0}+\ket{n,n+1,1}\right) \\ \ket{n-1,n,1} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n,n-1,0}-\ket{n,n+1,1}\right) \end{eqnarray*} in the group $\z$ and showed that the asyptotic probability distribution is somewhat different from the case without memory. Specifically, that localization occurs, which means that if the walk starts at 0 then for all $n\gte 0$, the probability that the walk is at the origin after $n$ steps is at least $0.5$. This result was verified and improved upon in \cite{konno} where the authors showed that the exact probability is $2-\sqrt{2}=0.58578\ldots$. \bl Let $G$ be a group with a specified generating set $A$. Then \begin{itemize} \item A (classical) random walk over $G$ with respect to $A$ is the assignation to $A^{\pm 1}$ of a probability distribution $p:A\mapsto[0,1]$, so that we have $g\mapsto ga^{\pm 1}$ with probability $p(a^{\pm 1})$. Thus the walk takes place in the Cayley graph of $G$ with respect to $A$ and if it is at any vertex $g$ of the Cayley graph, it progresses along the edge labelled $a^{\pm 1}$ with probability $p(a^{\pm 1})$. \item %If $A$ is finite then the {\em Cayley graph operator} $X(G,A):\co G \ra \co G$ is given by %\[ \ket{g}\mapsto\frac{1}{\sqrt{2|A|}}\sum_{a\in A^{\pm 1}} \ket{ga} \] Corresponding to the generating set $A$ we take a {\em quantum coin space} spanned by $A$. A quantum walk without memory over $G$ then takes place in the state space $\co G \tens \co A$. In this case there is one $G$-register, and a base state is written as $\ket{g,a}$ where $g\in G$ and $a\in A$. Following \cite{aharonov} in the cyclic case, if $A$ is finite, then define the {\em quantum Hadamard walk without memory} on $G$ to be given for all $g\in G$ and $a\in A$ by \begin{eqnarray*} \ket{g,a^{-1}} & \mapsto & \frac{1}{\sqrt{2}}(\ket{ga^{-1},a^{-1}} + \ket{ga,a}) \\ \ket{g,a} & \mapsto & \frac{1}{\sqrt{2}}(\ket{ga^{-1},a^{-1}} - \ket{ga,a}). \end{eqnarray*} Thus it is the composition of $\oplus _{i=1}^{|A|} W$ with the shift operator \[ \ket{g,a^{\pm 1}}\mapsto \ket{ga^{\pm 1}, a^{\pm 1}}, \] Where $W$ is the Walsh-Hadamard transformation. \notes{MB: One could also potentially take the Fourier transform over any finite group with cardinality $2|A|$. Come to think of it, I am not sure what I have written down even {\em is} a Fourier transform. If the product involved was a tensor product rather than a direct product then it would be the Fourier transform over $\z_2^n$. Maybe it is interesting to consider {\em any} unitary transformation of the coin space, like considering arbitrary $a$, $b$, $c$ and $d$ in the two-state case} It is known in the case $G=\Z_n$ for odd $n$ that, irrespective of initial state, and for a Hadamard coin, that the asymptotic probabilities are uniform, i.e $1/n$ for each of the $n$ points \cite{aharonov}. \notes{MMcG: What about even $n$ (do we always get something periodic)? What about other non-Hadamard coins? What happens in $Z_n$ when we add in memory?} \item A quantum walk with memory over $G$ is a certain unitary vector space automorphism of $\co (K \times A)$ where $K$ is a certain subset of $G\times G$. In this case there are two $G$-registers and a base state is written as $\ket{g_1,g_2,a^{\pm 1}}$ where $g_1,g_2\in G$ and $a\in A$. The walk corresponding to case (c) in \cite{mcgettrick} is given by \begin{eqnarray*} \ket{ga^{-1},g,a^{\pm 1}} \mapsto \frac{1}{\sqrt{2}}\left( \ket{g,ga^{-1},a^{-1}} \mp \ket{g,ga,a^{+1}} \right)\\ \ket{ga,g,a^{\pm 1}} \mapsto \frac{1}{\sqrt{2}}\left( \ket{g,ga,a^{-1}} \mp \ket{g,ga^{-1},a^{+1}} \right)\\ \end{eqnarray*} %\[ \ket{ga^{-1},g,a^{\pm 1}} \mapsto \frac{1}{\sqrt{2}}\left( \ket{g,ga^{-1},a^{\pm 1}} \mp %\ket{g,ga,a^{\mp 1}} \right) . \] \notes{MMcG: In \cite{konno} the quantum coin space is twice as large, and this incorporates memory. That is, the coin space for a cyclic group has four states. But it is not simply the tensor product of two sets of Walsh-Hadamard transformations; there is entanglement} \end{itemize} In a classical random walk on the group $\z$ the probability that the random walk is at any given point tends to zero as the number of steps tends to infinity. In this paper we consider quantum Hadamard walks over a finite cyclic group $\z_k$ with a standard generating set. There are various possibilities for a quantum Hadamard walk without memory on the group $\z$. Here are three of them: This is achieved by replacing $\ket{k}$ in the computations by $\ket{k\mbox{ } \mod\mbox{ } n}$, so that there are $k$ possible states for a group register, resulting in a $2k$-dimensional state space in the case without memory, and a $4k$-dimensional state space in the case with memory. There are various possibilities. Here are three of them: \begin{enumerate} \item The equivalent of the walk in \cite{mcgettrick}, a ``right-flip'' \begin{eqnarray*} \ket{n,R} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n-1,R}+\ket{n+1,L}\right) \\ \ket{n,L} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n-1,R}-\ket{n+1,L}\right) \end{eqnarray*} \item The equivalent of the walk in \cite{ambainis}, a ``left-flip'' \begin{eqnarray*} \ket{n,R} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n-1,R}+\ket{n+1,L}\right) \\ \ket{n,L} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n+1,R}-\ket{n-1,L}\right) \end{eqnarray*} \item The {\em left-reflecting walk} which it seems (by its behaviour) is the one in \cite{aharonov}. \begin{eqnarray*} \ket{n,R} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n-1,R}+\ket{n+1,L}\right) \\ \ket{n,L} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n+1,L}-\ket{n-1,R}\right) \end{eqnarray*} \end{enumerate} \section{The Right-Flip Walk} \subsection{The Special Case $\z_2$.} Here a group register may contain $\ket{n}$ or $\ket{n+1}$ only. \subsubsection{Without Memory} In $\z_2$ without memory we have a $4$-dimensional state space and \begin{eqnarray*} \ket{n,0} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n+1,0}\ket{n+1,1} \right)\\ & \mapsto & \frac{1}{2}\left(\ket{n,0}+\ket{n,1}+\ket{n,0}-\ket{n,1}\right) \\ & = & \ket{n,0} \end{eqnarray*} so that the walk is periodic with period 2. This is not surprising as the operator $W_2$ is easily seen to decompose as a tensor product $X\tens H$ where $H$ is the Walsh-Hadamard transformation and $X$ is a Pauli $X$-gate (cyclic permutation matrix of order 2), both of which have period 2. \subsubsection{With Memory} In $\z_2$ with memory we have a $4$-dimensional state space (states such as $\ket{0,0,i}$ and $\ket{1,1,i}$ are not allowed) \begin{eqnarray*} \ket{n+1,n,0} & \mapsto & \frac{1}{\sqrt{2}}\left( \ket{n,n+1,0}+\ket{n,n+1,1} \right) \\ & \mapsto & \frac{1}{2}\left( \ket{n+1,n,0} + \ket{n+1,n,1} + \ket{n+1,n,0} - \ket{n+1,n,1} \right) \\ & = & \ket{n+1,n,0} \end{eqnarray*} so that the walk is also periodic with period 2. \subsection{The Special Case $\z_3$.} Here a group register may contain $\ket{n}$, $\ket{n+1}$ or $\ket{n+2}$. \subsubsection{Without memory} The state space is $6$-dimensional (in $\z_n$ in general it has dimension $2n$) and \begin{eqnarray*} \ket{n,0} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n+2,0}+\ket{n+1,1}\right) \\ & \mapsto & \frac{1}{2}\left(\ket{n+1,0}+\ket{n,1}+\ket{n,0}-\ket{n+2,1}\right) \\ & \mapsto & \frac{1}{2\sqrt{2}}\left( \ket{n,0} +\ket{n+2,1} + 2\ket{n+2,0} -\ket{n+1,0} + \ket{n,1} \right) \\ & \mapsto & \frac{1}{4}\left( \ket{n,1} - \ket{n,0} + 3\ket{n+1,0} + 2\ket{n+2,0} - \ket{n+2,1} \right) \end{eqnarray*} %In this case there is a basis with respect to which $W$ has the form $P\tens H$ where $H$ is the Walsh-Hadamard transformation %and $P$ is a cyclic permutation matrix of order $3$. So it would seem that it has to be periodic with period 6, and in general %I would guess that $W_k$ is periodic with period $\mbox{l.c.m.}(2,k)$ ?? \subsubsection{With memory} The state space is $12$-dimensional (in $\z_n$ in general it has dimension $4n$) and \begin{eqnarray*} \ket{n+2,n,0} & \mapsto & \frac{1}{\sqrt{2}}\left( \ket{n,n+2,0} + \ket{n,n+1,1} \right) \\ & \mapsto & \frac{1}{2} \left( \ket{n+2,n,0} + \ket{n+2,n+1,1} + \ket{n+1,n,0} - \ket{n+1,n+2,1} \right) \\ & \mapsto & \frac{1}{2\sqrt{2}} \left( \ket{n,n+2,0} + \ket{n,n+1,1} + \ket{n+1,n+2,0} - \ket {n+1,n,1} + \ket{n,n+1,0} \right. \\ & & \left. + \ket{n,n+2,1} - \ket{n+2,n+1,0} + \ket{n+2,n,1} \right) \\ & \mapsto & \frac{1}{\sqrt{13}} \left( \ket{n+2,n,0} + 2 \ket{n+1,n,0} + \ket{n+2,n+1,0} + \ket{n+2,n,1} - \ket{n,n+1,0} \right. \\ & & \left. + \ket{n,n+2,1} + \ket{n+2,n,0} - \ket{n+1,n+2,0} - \ket{n+1,n,1} + \ket{n,n+2,0} \right) \end{eqnarray*} \section{The Left-Flip Walk} \section{Left-Reflecting Walk} \subsection{Without Memory} Consider the {\em left-reflecting} walk without memory given by \begin{eqnarray*} \ket{n,R} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n-1,R}+\ket{n+1,L}\right) \\ \ket{n,L} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n+1,L}-\ket{n-1,R}\right) \end{eqnarray*} implemented as follows: \begin{lstlisting}[backgroundcolor=\color{subtlegrey}, caption={C\# code fragment for the left reflecting walk}, captionpos=b] public static SparseVector cycleWalk(SparseVector state, int mod){ SparseVector result = new SparseVector(); foreach (string s in state.Keys){ int firstReg = Int32.Parse(s.Substring(0, s.Length - 1)); SparseVector vectorToAdd = new SparseVector(); if (s[s.Length - 1] == 'R'){ vectorToAdd[(shiftRightWithMod(firstReg,mod)).ToString() + "R"] = 1 / Math.Sqrt(2) * state[s]; vectorToAdd[(shiftLeftWithMod(firstReg,mod)).ToString() + "L"] = 1 / Math.Sqrt(2) * state[s]; } if (s[s.Length - 1] == 'L'){ vectorToAdd[(shiftLeftWithMod(firstReg,mod)).ToString() + "R"] = 1 / Math.Sqrt(2) * state[s]; vectorToAdd[(shiftRightWithMod(firstReg,mod)).ToString() + "L"] = -1 / Math.Sqrt(2) * state[s]; } result = (SparseVector)result.plus(vectorToAdd); } return result; } \end{lstlisting} For the cyclic group $k$ the possibilities $k=1$ up to $k=16$ were tried. For all odd orders, {\em mixing} occurs, that is, the probability distribution of the location of the walk tends to a uniform distribution. For the even orders mixing did not occur. The probability distribution was periodic and the following was obtained (omitting normalization). \bl \begin{center} \begin{tabular}{l|l|l} order & period & sequence \\ \hline 2 & 2 & $\ket{0},\ket{1},\ket{0},\ket{1},\ldots$ \\ 4 & 4 & $\ket{0},\ket{1}+\ket{3},\ket{2},\ket{1}+\ket{3},\ket{0}$ \\ 6 & 2 & $\ket{0}+\ket{2}+\ket{4},\ket{1}+\ket{3}+\ket{5},\ldots$ \\ 8 & 4 & $\ket{0}+\ket{4}, \ket{1}+\ket{3}+\ket{5}+\ket{7}, \ket{2}+\ket{6}, \ket{1}+\ket{3}+\ket{5}+\ket{7},\ldots$ \\ 10 & 2 & $\ket{0}+\ket{2}+\cdots+\ket{8},\ket{1}+\ket{3}+\cdots+\ket{9},\ldots$ \\ 12 & 4 & $\ket{0}+\ket{4}+\ket{8},\ket{1}+\ket{3}+\cdots+\ket{11},\ket{2}+\ket{6}+\ket{10},\ket{1}+\ket{3}+\cdots+\ket{11},\ldots$ \\ 14 & 2 & $\ket{0}+\ket{2}+\cdots+\ket{12},\ket{1}+\ket{3}+\cdots+\ket{13},\ldots$\\ 16 & 4 & $\ket{0}+\ket{4}+\cdots+\ket{12}, \ket{1}+\ket{3}+\cdots+\ket{15}, \ket{2}+\ket{6}+\cdots+\ket{14},$ \\ & & $\ket{1}+\ket{3}+\cdots+\ket{15}, \ldots$ \end{tabular} \end{center} The general pattern seems to be for $k=2(2n+1)$ we have a period 2 sequence \[ \sum{\ket{2m+1}}, \sum{\ket{2m}}, \ldots \] and for $k=4n$ we have a period 4 sequence \[ \sum{\ket{2m+1}}, \sum{\ket{4m}}, \sum{\ket{2m+1}}, \sum{\ket{2(2m+1)}}, \ldots \] where $m$ is an integer (in the right range). \section{Amplitudes} \subsection{Hadamard Quantum Walk on $\z$} We start from the known explict formula for amplitudes, given in various references (\cite[Eqn. 5.27, page 74]{venegas}, \cite[Equation II.15, page 7]{brun}, \cite[Equation (2), Lemma 4]{ambainis}). Considering a $t$-step walk, we want to know the amplitude at point $n$ with $|n| \leq t$. \begin{displaymath} \Psi_R(n,t)=\left\{ \begin{array}{l l l} 0 & \quad \mbox{if $n+t$ is odd}\\ \frac{1}{\sqrt{2^t}} & \quad \mbox{if $n=t$ }\\ \frac{1}{\sqrt{2^t}}\sum_k\binom{(t-n)/2-1}{k-1} \binom{(t+n)/2}{k}(-1)^{(t-n)/2-k} & \quad \mbox{if $n+t$ is even and $n\neq t$}\\ \end{array} \right. \end{displaymath} (The $R$ above as a subscript refers to ``right moving'': Analogous formulae are present for $L$ (``left moving''), that we won't write for now.) (We assume from now on in this section that $t+n$ is even...) The references listed do not make explicit the summation limits in $k$, so here we give them explicitly: \begin{equation}\label{amp1} \Psi_R(n,t)= \frac{1}{\sqrt{2^t}}\sum_{k=1}^{(t-|n|)/2}\binom{(t-n)/2-1}{k-1} \binom{(t+n)/2}{k}(-1)^{(t-n)/2-k} \end{equation} \subsection{Hadamard Quantum Walk on $\z_p$} We must distinguish the cases for $p$ even or odd: For $p$ even, the amplitudes will still be zero for $n+t$ odd, simply because $(n\mod p)$ has the same parity as $n$. But for $p$ odd, once $t$ is appreciably larger than $n$, none of the amplitudes will be zero. Set $n=x+rp$ where $r\in\z$ and $0\leq x\leq p-1$. Then we write Eqn.\ \ref{amp1} as \begin{equation}\label{amp2} \Psi_R(x,t,p)= \frac{1}{\sqrt{2^t}}\sum_r\sum_{k=1}^{(t-|x+rp|)/2} \binom{(t-(x+rp))/2-1}{k-1} \binom{(t+x+rp)/2}{k} (-1)^{(t-(x+rp))/2-k} \end{equation} We break this rather long expression by writing \begin{equation} \Psi_R(x,t,p)= \sum_r\sum_{k=1}^{(t-|x+rp|)/2} f(x,t,p,r,k) \end{equation} where \begin{equation} f(x,t,p,r,k)= \frac{1}{\sqrt{2^t}} \binom{(t-(x+rp))/2-1}{k-1} \binom{(t+x+rp)/2}{k} (-1)^{(t-(x+rp))/2-k} \end{equation} \begin{enumerate} \item Even p\\ \begin{itemize} \item \underline{odd $x+t$:} $ \Psi_R(x,t,p)=0$ \item \underline{even $x+t$:} Since $p$ is even, contributions to point $x$ come from \begin{equation} \dots x-2p, x-p, x, x+p, x+2p,\dots \end{equation} Simple investigation gives the upper and lower limits on $r$ to be \begin{eqnarray} r^+&=1+\lfloor (t-x-1)/p\rfloor\\ r^-&=-\lfloor (t+x-1)/p\rfloor. \end{eqnarray} We then add in separately the contribution (if it exists) from $n=t$ (this will exist iff $x=t\bmod p$) to get \begin{equation} \Psi_R(x,t,p)=\frac{\delta_{t\bmod p,\ x}}{\sqrt{2^t}} + \sum_{r=r^-}^{r^+}\sum_{k=1}^{(t-|x+rp|)/2} f(x,t,p,r,k) \end{equation} where $\delta$ is the standard Kronecker delta function, $\delta_{x,y} = 1$ iff $x=y$, otherwise zero. \end{itemize} \item Odd p\\ \begin{itemize} \item \underline{odd $t$:} Contributions to $\Psi_R(x,t,p)$ come from every \textbf{second} value of $r$. If $x$ is odd, contributions come from $r\in \{\dots -2,0,2,\dots\}$. If $x$ is even, contributions come from $r\in \{\dots -3,-1,1,3,\dots\}$. \item \underline{even $t$:} Contributions to $\Psi_R(x,t,p)$ come from every \textbf{second} value of $r$. If $x$ is even, contributions come from $r\in \{\dots -2,0,2,\dots\}$. If $x$ is odd, contributions come from $r\in \{\dots -3,-1,1,3,\dots\}$. \end{itemize} In either case, we have \begin{equation}\label{oddp} \Psi_R(x,t,p)=\frac{\delta_{t\bmod p,\ x}}{\sqrt{2^t}} + \sum_{r\in S}\sum_{k=1}^{(t-|x+rp|)/2} f(x,t,p,r,k) \end{equation} where \begin{equation} S=\{v\in \z | r^- \leq v \leq r^+, \mbox{ and } (t-x-v)\bmod 2 =0\} \end{equation} \end{enumerate} \subsection{Some Examples on $\z_p$} Consider the transitions \begin{eqnarray*} \ket{n,0} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n+1,0}+\ket{n-1,1}\right) \\ \ket{n,1} & \mapsto & \frac{1}{\sqrt{2}}\left(\ket{n+1,0}-\ket{n-1,1}\right) \end{eqnarray*} so that 0 means ``move right'' while 1 means ``move left'', and we get the phase of $-1$ for 2 successive left moves. Starting at $\ket{0,0}$ we get \begin{eqnarray*} {\color{red}\ket{0,0}} & \mapsto & \frac{1}{\sqrt{2}}\left( {\color{red}\ket{1,0}} + \ket{-1,1} \right) \\ & \mapsto & \frac{1}{2} \left( {\color{red}\ket{2,0}} + \ket{0,1} + {\color{red}\ket{0,0}} - \ket{-2,1} \right) \\ & \mapsto & \frac{1}{2\sqrt{2}} \left( {\color{red}\ket{3,0}} - {\color{red}\ket{-1,0}} + 2{\color{red}\ket{1,0}} - \ket {1,1} + \ket{-3,1} \right) \\ & \mapsto & \frac{1}{4} \left( {\color{red}\ket{4,0}} + 3{\color{red}\ket{2,0}} + \ket{2,1} - {\color{red}\ket{0,0}} + \ket{0,1} + {\color{red}\ket{-2,0}} -\ket{-2,1} -\ket{-4,1} \right)\\ & \mapsto & \frac{1}{4\sqrt{2}} \left( {\color{red}\ket{5,0}} + 4{\color{red}\ket{3,0}} + \ket{3,1} +2\ket{1,1} -2\ket{-1,1} -{\color{red}\ket{-3,0}} +2\ket{-3,1} +\ket{-5,1} \right) \end{eqnarray*} where we color in {\color{red}red} the right movers for ease of legibility. Considering only the right movers, the un-normalized amplitudes are \begin{center} \begin{tabular}{l|l} $t$ & $\Psi_R(n,t)$ \\ \hline 0 & 1\\ 1 & 0, 1\\ 2 & 0, 1, 1\\ 3 & 0, -1, 2, 1\\ 4 & 0, 1, -1, 3, 1\\ 5 & 0, -1, 0, 0, 4, 1\\ \end{tabular} \end{center} where the $t+1$ values in each row correspond to $n$ taking on the values $-t, -t+2,\dots, t-2, t$. \subsubsection{$\z_3$} Considering the 5-step example we are following, so $t=5$ and $p=3$, the un-normalized right moving amplitudes at the 3 possible positions are \begin{description} \item[At $x=0$:] $4-1=3$ \item[At $x=1$:] $0+0=0$ \item[At $x=2$:] $1+0=1$ \end{description} Equation (\ref{oddp}) becomes \begin{equation} \Psi_R(x,5,3)=\frac{\delta_{2,\ x}}{\sqrt{2^5}} + \sum_{r\in S}\sum_{k=1}^{(5 -|x+3r|)/2} f(x,5,3,r,k) \end{equation} with $r^-=-\lfloor (4+x)/3\rfloor$ and $r^+=1 + \lfloor (4-x)/3\rfloor$. (Again in what follows we ignore $\sqrt{2}$ factors.) \begin{itemize} \item \textbf{Amplitude at $x=1$:} $r^-=-1,\ r^+=2$, and $S=\{0,2\}$. So we get \begin{equation} \Psi_R(1,5,3)= \sum_{k=1}^{2} f(1,5,3,0,k) = f(1,5,3,0,1) + f(1,5,3,0,2) = -2 + 2 = 0 \end{equation} \item \textbf{Amplitude at $x=0$:} $r^-=-1,\ r^+=2$, and $S=\{-1,1\}$. So we get \begin{equation} \Psi_R(0,5,3)= f(0,5,3,-1,1) + f(0,5,3,1,1) = -1 + 4 = 3 \end{equation} \end{itemize} \subsection{Asymptotics} Given the explicit formulae for the amplitudes, we should calculate: \begin{itemize} \item What is $\lim_{t\to\infty}\Psi_R(x,t,p)$ for odd $p$? \item What is $\lim_{t\to\infty}\frac{1}{t}\sum_t\Psi_R(x,t,p)$ for odd $p$? (this should be the uniform distribution talked about in other papers...) \item What is $\lim_{t\to\infty}\frac{1}{p}\sum_{k=0}^{p-1}\Psi_R(x,t+k,p)$ for odd $p$? (this should be the uniform distribution also - we are summing over the cycle?!) \item The periodicity that seems to occur for even $p$ should be provable from the explicit amplitudes, i.e. that there is some fixed $l$ for which \begin{equation} \Psi_R(x,t,p)=\Psi_R(x,t+l,p)\ \ \forall x. \end{equation} \end{itemize} \section{Full Program Listing} \begin{lstlisting}[backgroundcolor=\color{subtlegrey}, caption={C\# code for main GroupWalker class}, captionpos=b] using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace GroupWalker { class Program { static int period = 2; static string initialState = "0R"; static void Main(string[] args) { SparseVector state = new SparseVector(); state[initialState] = 1; Console.WriteLine("Step 0"); printFirstRegister(period, state); for (int i = 0; i < 2; i++) { Console.WriteLine("Step "+(i+1).ToString()); state = cycleWalk(state,period); printFirstRegister(period,state); } Console.ReadKey(true); } public static SparseVector cycleWalk(SparseVector state, int mod) { SparseVector result = new SparseVector(); foreach (string s in state.Keys) { int firstReg = Int32.Parse(s.Substring(0, s.Length - 1)); SparseVector vectorToAdd = new SparseVector(); if (s[s.Length - 1] == 'R') { vectorToAdd[(shiftRightWithMod(firstReg,mod)).ToString() + "R"] = 1 / Math.Sqrt(2) * state[s]; vectorToAdd[(shiftLeftWithMod(firstReg,mod)).ToString() + "L"] = 1 / Math.Sqrt(2) * state[s]; } if (s[s.Length - 1] == 'L') { vectorToAdd[(shiftLeftWithMod(firstReg,mod)).ToString() + "R"] = 1 / Math.Sqrt(2) * state[s]; vectorToAdd[(shiftRightWithMod(firstReg,mod)).ToString() + "L"] = -1 / Math.Sqrt(2) * state[s]; } result = (SparseVector)result.plus(vectorToAdd); } return result; } public static string bar(double d) { int length = Convert.ToInt32(d * 50); string result=""; for (int i = 0; i < length; i++) result += "X"; return result; } public static void printState(int mod, SparseVector state) { for (int i = 0; i < mod; i++) { if (state.ContainsKey(i.ToString()+"R")) System.Console.WriteLine("|" + i + "R> " + bar(state[i.ToString() + "R"])); } for (int i = 0; i < mod; i++) { if (state.ContainsKey(i.ToString() + "L")) System.Console.WriteLine("|" + i + "L> " + bar(state[i.ToString() + "L"])); } } public static void printFirstRegister(int mod, SparseVector state) { for (int i = 0; i < mod; i++) { double amplitude = 0; if (state.ContainsKey(i.ToString() + "R")) amplitude += Math.Pow(state[i.ToString() + "R"],2); if (state.ContainsKey(i.ToString() + "L")) amplitude += Math.Pow(state[i.ToString()+"L"],2); amplitude = Math.Sqrt(amplitude); System.Console.WriteLine("|" + i + "> " + bar(amplitude)); } } public static int shiftLeft(int n) { return n - 1; } public static int shiftRight(int n) { return n + 1; } public static int shiftLeftWithMod(int n, int mod) { if (n>0) return n-1; return mod - 1; } public static int shiftRightWithMod(int n, int mod) { if (n < mod - 1) return n + 1; return 0; } } } \end{lstlisting} \begin{lstlisting}[backgroundcolor=\color{subtlegrey}, caption={C\# code for sparse vector class}, captionpos=b] using System; using System.Linq; using System.Collections.Generic; using System.Text; namespace GroupWalker { public class SparseVector : Dictionary, ISparseVector { public ISparseVector plus(ISparseVector v2) { SparseVector result = new SparseVector(); foreach (T t in this.Keys) if (v2.ContainsKey(t)) { if (this[t] + v2[t] != 0) result[t] = this[t] + v2[t]; } else result[t] = this[t]; foreach (T t in v2.Keys) if (!this.ContainsKey(t)) result[t] = v2[t]; return result; } public ISparseVector times(double f) { if (f == 0) return new SparseVector(); else { SparseVector result = new SparseVector(); foreach (T t in this.Keys) result[t] = f * this[t]; return result; } } public ISparseVector minus(ISparseVector v1, ISparseVector v2) { return v1.plus(v2.times(-1)); } new public double this[T index] { set { if (value != 0) base[index] = value; } get { return base[index]; } } public double dot(ISparseVector v) { double result = 0; foreach (T t in Keys) if (v.ContainsKey(t)) result += this[t] * v[t]; return result; } public double modulus() { return Math.Sqrt(this.dot(this)); } public ISparseVector normalize() { if (this.modulus() == 0) return this; else return this.times(1 / this.modulus()); } public override string ToString() { string result = ""; foreach (T t in Keys) result += this[t] + "|" + t.ToString() + "> "; return result; } public double distance(ISparseVector v) { return 1 - this.normalize().dot(v.normalize()); } public ISparseVector closest(List> vList) { double leastDistance = 2; SparseVector result = new SparseVector(); foreach (SparseVector v in vList) { double currentDistance = distance(v); if (currentDistance <= leastDistance) { leastDistance = currentDistance; result = v; } } return result; } } } \end{lstlisting} \begin{thebibliography}{99} \bibitem{aharonov} Aharonov, D., Ambainis, A., Kempe, J. and Vazirani, U. {\em Quantum Walks on Graphs}, In Proceedings of the 33rd ACM Symposium on Theory of Computing (2000) 50-59. \bibitem{konno} Konno, N. and Machida, T. {\em Limit Theorems for Quantum Walks with Memory} arXiv:1004.0443v2 [quant-ph] (2010). \bibitem{mcgettrick} McGettrick, M., {\em One Dimensional Quantum Walks with Memory} Quantum Information and Computation Vol. 10, No. 5\&6 (2010) 509-524. \bibitem{ambainis} Ambainis, A., Bach, E., Nayak, A., Vishwanath, A. and Watrous, J. {\em One Dimensional Quantum Walks} Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 37�49, 2001. \bibitem{venegas} Venegas-Andraca, S.E., {\em Quantum Walks for Computer Scientists}, Morgan and Claypool (2008). \bibitem{brun} Brun, T.A., Carteret, H.A. and Ambainis, A., {\em Quantum Walks driven by many coins}, arXiv:0210161 [quant-ph] (2002). [Equation II.15, page 7] \end{thebibliography} \begin{flushleft} {\small Michael Batty,\\ School of Engineering and Computer Science,\\ Durham University,\\ Durham,\\ UK,\\ DH1 3LE,\\ email: michael.batty@dur.ac.uk} \end{flushleft} \begin{flushleft} {\small Michael McGettrick,\\ School of Mathematics, \\ The National University of Ireland, \\ Galway, \\ Ireland. \\ e-mail: } \end{flushleft} \end{document}