{A new approach to quantum walks is presented. Considering a quantum system undergoing some unitary discrete-time evolution in a directed graph G, we think of the vertices of G as sites that are occupied by the quantum system, whose internal state is described by density operators. To formulate the unitary evolution, we define reflections in the tensor product of an internal Hilbert space and a spatial Hilbert space. We then construct unitary channels that govern the evolution of the system in the graph. The discrete dynamics of the system (called quantum walks) is obtained by iterating the unitary channel on the density operator of the quantum system. It turns out that in this framework, the action of the unitary channel on a density operator is described by the usual matrix multiplication.
1506.02493.tex

\documentclass[12pt]{article}

\usepackage{latexsym}
\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\usepackage{graphicx}% Include figure files
\usepackage{dcolumn}% Align table columns on decimal point

\usepackage{amssymb}
\usepackage{amsmath}

\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\font\bbbold=msbm10 at 12pt

\newcommand{\bm}[1]{\mbox{\boldmath $#1$}}

\newcommand{\sfrac}[2]{ \mbox{$\frac{#1}{#2}$} }

\newcommand{\bbA}{\mbox{\bbbold A}}
\newcommand{\bbC}{\mbox{\bbbold C}}
\newcommand{\bbN}{\mbox{\bbbold N}}
\newcommand{\bbQ}{\mbox{\bbbold Q}}
\newcommand{\bbR}{\mbox{\bbbold R}}
\newcommand{\bbZ}{\mbox{\bbbold Z}}
\newcommand{\bbE}{\mbox{\bbbold E}}
\newcommand{\ssz}[1]{\mbox{\scriptsize $#1$}}

\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}

\newcommand{\D}[1]{\,${\displaystyle #1}$\,}

\newcommand{\K}[1]{\,${#1}$\,}

\newcommand{\ov}[1]{\overline{#1}}

\newcommand{\no}{\nonumber}

\newcommand{\bq}{\begin{equation}}
\newcommand{\eq}{\end{equation}}

\newcommand{\bqr}{\begin{eqnarray}}
\newcommand{\eqr}{\end{eqnarray}}

\newcommand{\bqrx}{\begin{eqnarray*}}
\newcommand{\eqrx}{\end{eqnarray*}}

\newcommand{\br}{\begin{array}}
\newcommand{\er}{\end{array}}

                       %%%%%%%%%%%%%%%%

\newcommand{\bA}{{\bf A}}
\newcommand{\dd}{{\bf D}}
\newcommand{\ee}{{\bf E}}
\newcommand{\rr}{{\bf R}}
\newcommand{\zz}{{\bf Z}}
\newcommand{\cc}{{\bf C}}
\newcommand{\qq}{{\bf Q}}
\newcommand{\G}{{\bf G}}  %% changed from \gg
\newcommand{\hh}{{\bf H}}
\newcommand{\uu}{{\bf U}}

\newcommand{\rd}{{\rr^{d}}}
\newcommand{\rn}{{\rr^{n}}}

\newcommand{\aaa}{{\cal A}}
\newcommand{\eee}{{\cal E}}
\newcommand{\fff}{{\cal F}}
\newcommand{\bbb}{{\bf \cal B}}
\newcommand{\mmm}{{\bf \cal M}}
\newcommand{\nnn}{{\cal N}}
\newcommand{\ppp}{{\bf \cal P}}
\newcommand{\qqq}{{\bf \cal Q}}
\newcommand{\rrr}{{\cal R}}
\newcommand{\uuu}{{\bf \cal U}}
\newcommand{\vvv}{{\bf \cal V}}

\newcommand{\ra}{{\rightarrow}}
\newcommand{\st}{{\star}}
\newcommand{\ty}{{\infty}}
\newcommand{\bs}{{\backslash}}
\renewcommand{\ss}{{\subset}} %%%%%%%%%%%%%%%%%
\newcommand{\op}{{\oplus}}
\newcommand{\ot}{{\otimes}}

\newcommand{\ka}{\kappa}
\newcommand{\la}{\lambda}
\newcommand{\La}{\Lambda}
\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\ga}{\gamma}
\newcommand{\Ga}{\Gamma}
\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\ep}{\epsilon}
\newcommand{\vep}{\varepsilon}
\newcommand{\ze}{\zeta}
\newcommand{\vth}{\vartheta}
\newcommand{\si}{\sigma}
\newcommand{\vsi}{\varsigma}
\newcommand{\om}{\omega}
\newcommand{\vi}{\varphi}
\newcommand{\vo}{\varrho}

\newcommand{\pa}{\partial}

                       %%%%%%%%%%%%%%%%%

\newcommand{\M}[2]{{\rm M}(#1,{\bf #2})}
\newcommand{\GL}[2]{{\rm GL}(#1,{\bf #2})}
\newcommand{\SL}[2]{{\rm SL}(#1,{\bf #2})}

                       %%%%%%%%%%%%%%%%%

                %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
                %%%%%% o=1    t=2    T=3 %%%%%%
                %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\obt}[2]{ \begin{array}{rr}
                                   #1 & #2
                            \end{array} }

\newcommand{\oxt}[3]{ \begin{array}{#1#1}
                                   #2 & #3
                            \end{array} }


\newcommand{\tbo}[2]{ \left[\begin{array}{l}
                                   #1 \\
                                   #2
                            \end{array} \right]}

\newcommand{\txo}[3]{ \begin{array}{#1}
                                   #2 \\
                                   #3
                            \end{array} }


\newcommand{\tbt}[4]{ \begin{array}{rr}
                                   #1 & #2 \\
                                   #3 & #4
                            \end{array} }

\newcommand{\txt}[5]{ \begin{array}{#1#1}
                                   #2 & #3 \\
                                   #4 & #5
                            \end{array} }


\newcommand{\obT}[3]{ \begin{array}{ccc}
                                   #1 & #2 & #3
                            \end{array} }

\newcommand{\oxT}[4]{ \begin{array}{#1#1#1}
                                   #2 & #3 & #4
                            \end{array} }

\newcommand{\Txo}[4]{ \begin{array}{#1}
                                   #2 \\
                                   #3 \\
                                   #4
                            \end{array} }


\newcommand{\tbT}[6]{ \begin{array}{ccc}
                                   #1 & #2 & #3 \\
                                   #4 & #5 & #6
                            \end{array} }

\newcommand{\TbT}[9]{ \begin{array}{ccc}
                                   #1 & #2 & #3 \\
                                   #4 & #5 & #6 \\
                                   #7 & #8 & #9
                            \end{array} }


\newcommand{\mt}[4]{\left[ \begin{array}{cc}
                                   #1 & #2 \\
                                   #3 & #4
                            \end{array} \right]}

\newcommand{\mxt}[5]{\left[ \begin{array}{#1#1}
                                   #2 & #3 \\
                                   #4 & #5
                            \end{array} \right]}


\newcommand{\mT}[9]{\left[ \begin{array}{ccc}
                                   #1 & #2 & #3 \\
                                   #4 & #5 & #6 \\
                                   #7 & #8 & #9
                            \end{array} \right]}

\newcommand{\smT}[9]{\ssz{\mT{#1}{#2}{#3}
                             {#4}{#5}{#6}
                             {#7}{#8}{#9} }}

\newcommand{\B}[2]{\( \stackrel{ #1}{_{#2}} \)}



                       %%%%%%%%%%%%%%%%%%%

\newcommand{\qed}{\rule{1ex}{1ex}}

\newcommand{\haf}{\sfrac{1}{2}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\ooo}{\mbox{\ }}
\newcommand{\five}{\ooo \ooo \ooo \ooo \ooo}
\newcommand{\ten}{\five \five}
\newcommand{\fifty}{\ten\ten\ten\ten\ten}
\newcommand{\two}{\ooo\ooo}
\newcommand{\hs}[1]{\hspace{#1ex}}
\newcommand{\hoo}{\hspace*{10pt}}
\newcommand{\voo}{\vspace*{5pt}}
\newcommand{\vtoo}{\vspace*{2.5pt}}
\newcommand{\woo}{\vspace*{-5pt}}
\newcommand{\hm}[1]{\mbox{\hspace{#1ex}}}
\newcommand{\hmn}{\!\!\!\!\!\!\!\!\!\!} % approx -1/4 in.
\newcommand{\hmp}{\,\,\,\,\,\,\,\,\,\,} % approx +1/4 in.
\newcommand{\ax}{\hspace*{1pt}}
\newcommand{\oox}{\mbox{\ } \\}
\newcommand{\lord}{\nonumber \ooo & \ooo & \ooo \\}

\newcommand{\smt}[4]{\ssz{\mt{#1}{#2}{#3}{#4}}}

\newcommand{\stxo}[2]{\left[\ssz{\txo{l}{#1}{#2}}\right]}

\newcommand{\iph}{\:\:\:{\rm if}\:\:\:}

\newcommand{\lcm}{\mbox{lcm}}

\newcommand{\qres}[2]{ \mbox{ \boldmath $ \( \mbox{$\frac{#1}{#2}$}  \)$ } }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\axes}{\put(-9,0){\vector(1,0){18}} % x-axis
                                \put(8.6667,-.8333){\makebox(0,0){{\scriptsize $x$}}} % horizontal label
                                \put(0,-9){\vector(0,1){18}} % y-axis
                                \put(-.8333,8.6667){\makebox(0,0){{\scriptsize $y$}}}} % vertical label

\newcommand{\graph}[2]{\unitlength=6pt%
                                    \begin{picture}(20.8333,18)(-11.5,-9)%
                                    \put(-10,8){\makebox(0,0){\bf #1}}% choice label a), b), c), or d)
                                    \scaledaxes%
                                    \thicklines%
                                      #2
                                    \thinlines%
                                    \end{picture}}

\newcommand{\Axes}{\unitlength=8pt%
                                    \begin{picture}(20.8333,18)(-11.5,-9)%
                                    \axes%
                                    \end{picture}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newcommand{\blsk}{\baselineskip}
\renewcommand{\baselinestretch}{1.0}
\renewcommand{\textwidth}{470pt}
\renewcommand{\textheight}{675pt}
\addtolength{\topmargin}{-80pt}

%%%%%%%%%%%%%%%%% BEGIN DOC %%%%%%%%%%%%%%%%%%%

\begin{document}

\pagestyle{plain}
\pagenumbering{arabic}

\setlength{\parindent}{0in}
\setlength{\parskip}{3ex}
\setlength{\footskip}{.6in}

%\setlength{\blsk}{.15in} = tightly-spaced
%\setlength{\blsk}{.2in} = slightly extra-spaced
%\setlength{\blsk}{.3in} = very extra-spaced

%=========================================================

\setlength{\blsk}{.25in}%
\vspace*{.6in}
\begin{center}
Quantum walks in the density operator picture
\end{center}
\begin{center}
Chaobin\, Liu  \footnote{cliu@bowiestate.edu, Department of Mathematics, Bowie State University\\Bowie, MD 20715 USA}

\end{center}

%\setlength{\blsk}{.27in}%

\begin{abstract}
{A new approach to quantum walks is presented. Considering a quantum system undergoing some unitary discrete-time evolution in a directed graph G, we think of the vertices of G as sites that are occupied by the quantum system, whose internal state is described by density operators. To formulate the unitary evolution, we define reflections in the tensor product of an internal Hilbert space and a spatial Hilbert space. We then construct unitary channels that govern the evolution of the system in the graph. The discrete dynamics
of the system (called quantum walks) is obtained by iterating the unitary channel on the density operator of the quantum system. It turns out that in this framework, the action of the unitary channel on a density operator is described by the usual matrix multiplication.
}
\end{abstract}%

\section{Introduction}

Considering a quantum system undergoing some discrete-time evolution in a directed graph G, we think of the vertices of G as sites that are occupied by the quantum system, whose inner state is determined by density operators. The quantum system is assumed to be isolated and closed. According to the principle of quantum mechanics, the evolution of the quantum system is described by a unitary transformation \cite{NC2000}. To the best of our knowledge, none of the existing quantum schemes or quantum frameworks (such as quantum walks and open quantum walks) exactly models the evolution of the quantum system in this scenario. 
\vskip 0.1in
Specifically, even though open quantum walks \cite{APS12, APSS12, G2008} do concern density operators, their transformations are usually not unitary since they are formulated as unital, trace-preserving and completely positive maps on graphs. The frameworks of discrete-time quantum walks in \cite{ABNVW01, W2001, AAKV01, K03, Konno05, K06, VA12} and the references cited therein are used to describe the unitary evolution of a quantum system, but the quantum evolutions address pure states of the system. It is noted that the unitary maps in the frameworks are defined by conditional shifts and coin operators. There are two other notable schemes for unitary evolution of quantum walks \cite{S04} and \cite{PRR05}, where the unitary transformations also deal with pure states of the quantum system. In \cite{S04}, the unitary transformation is defined by a swap operator and a reflection operator, while in \cite{PRR05}, the unitary map is given by two consecutive reflection-like operators. It may be of interest to read the lecture note \cite{W12} regarding the relationship between these unitary transformations. 

\vskip 0.1in
In this note, we aim to introduce an approach to the evolution of the aforesaid quantum system in the density operator picture. Enlightened by the idea presented in \cite{S04}, we will employ reflection operators in an enlarged Hilbert space to construct unitary transformations which govern the evolution of the system. Following convention, we will also call the evolution of this system quantum walks. 

%\vskip 0.2in
%The rest of this note is organized as follows.  We first define reflections in the tensor product of internal Hilbert space and spatial Hilbert space. We then construct unitary quantum operation, which maps density matrices to density matrices. We conclude by showing that our formalism generalizes the framework in \cite{S04} for quantum random walk.


\section{General setup for quantum walks in the density operator picture}

We may assume that the unitary transformation of a quantum system takes place on a directed graph $G(V, E)$. Here $V$ is the set of the vertices of $G$, $E$ is the set of the oriented edge of $G$, $E=\{(j,k): j,k \in V\}$.  Let $\mathcal{H}_V$ be a complex Hilbert space with the standard orthonormal basis $\{|j\rangle\}_{j\in V}$. The set of bounded linear operators on $\mathcal{H}_V$ is denoted by $\mathfrak{B}(\mathcal{H}_V)$. Let $\mathcal{H}_C$ be an $n$-dimensional complex Hilbert space, spanned by the set of degrees of freedom $C=\{c_1, c_2, ..., c_n\}$, the set of bounded linear operators on $\mathcal{H}_C$ is denoted by $\mathfrak{B}(\mathcal{H}_C)$.

\vskip 0.1in

For a Hilbert space $\mathcal{H}$, let $\mathfrak{B}(\mathcal{H})$ be the set of bounded linear operators on $\mathcal{H}$ with the {\it Hilbert-Schmidt} inner product, defined by 
$$\langle A,B\rangle=\mathrm{tr}(A^{\dagger}B).$$
It can be verified that $\mathfrak{B}(\mathcal{H})$ becomes a Hilbert space with this inner product.

\vskip 0.2in

Associated with the quantum system on $G$ is the Hilbert space $\mathcal{H}_C\otimes \mathcal{H}_V^{\otimes 2}$, which is called the {\it state space} of the system. The system is completely described by its {\it state vector}, which is a unit vector in the system's state space. For instance, a typical state vector may be of the form $u\otimes |lm\rangle$ where $u\in \mathcal{H}_C$ as an $n$-dimensional column vector. In the density operator picture, the Hilbert space becomes $\mathfrak{B}(\mathcal{H}_C)\otimes \mathfrak{B}(\mathcal{H}_V\otimes\mathcal{H}_V)$, and the system is completely described by a positive operator with trace one (called a {\it density operator}), acting on the state space of the system. For example, a typical density operator may be written in the form of $\rho\otimes |lm\rangle\langle lm|$ where $\rho\in \mathfrak{B}(\mathcal{H}_C)$, which is a positive operator with $\mathrm{tr}(\rho)=1$.

\vskip 0.2in

The quantum system described in the aforesaid framework can be understood as a system consisting of a particle that has an internal quantum state ($u$ or $\rho$) and occupies a classical state ($|lm\rangle$ or $|lm\rangle\langle lm|$). This particle evolves from one state to another under certain unitary transformation to be defined as follows.
\vskip 0.2in



To define the unitary transformation, we first introduce the states in the Hilbert space $\mathcal{H}_C\otimes \mathcal{H}_V^{\otimes 2}$ :
\begin{equation}
|\psi_j\rangle:=\sum_k v_j^k\otimes |j,k\rangle,\label{key}
\end{equation}
where the column vectors $v_j^k$ satisfy the unital condition condition, i.e., $\sum_k(v_j^k)^{\ast}v_j^k=1$.  $v^{\ast}$ is the Hermitian transpose of $v$. 

\vskip 0.2in
It is noted that the pairs $(j,k)$ in Eq.(\ref{key}) indicate the edges of $G$ directed from the vertex $j$ since the unitary transformation on $G$ is expected to be subject to the geometric structure of $G$.

\vskip 0.2in

Secondly, we define 
\begin{equation}
\Pi:=\sum_j^{|V|}|\psi_j\rangle \langle \psi_j|, \label{}
\end{equation}
which is the projection on $\mathrm{span}\{|\psi_j\rangle:j=1, 2,..., |V|\}$, denoted by $\mathcal{H}_{\psi}$. This is a subspace of the augmented Hilbert space $\mathcal{H}_C\otimes\mathcal{H}_V^{\otimes 2}$. It can be verified that $2\Pi-1$ is a reflection operator on $\mathcal{H}_C\otimes\mathcal{H}_V^{\otimes 2}$. 

\vskip 0.2in
Then let us define 
\begin{equation}
S:=\mathbb{I}_c\otimes\sum_{j,k=1}^{|V|}|j,k\rangle\langle k,j| \label{}
\end{equation}
to be the operator that exchanges the two registers. Here $\mathbb{I}_c$ is the identity operator on $\mathfrak{B}(\mathcal{H}_C)$.
\vskip 0.2in

Finally, we define 
\begin{equation}
U:=S(2\Pi-\mathbb{I}).\label{}
\end{equation}
Here $\mathbb{I}$ is the identity operator on $\mathfrak{B}(\mathcal{H}_C)\otimes \mathfrak{B}(\mathcal{H}_V\otimes\mathcal{H}_V)$. It is noted that $U\in \mathfrak{B}(\mathcal{H}_C)\otimes \mathfrak{B}(\mathcal{H}_V\otimes\mathcal{H}_V)$, and $U$ is a unitary operator.

\vskip 0.2in

For $v\in \mathcal{H}_C\otimes\mathcal{H}_V^{\otimes 2}$, we think of $v$ as a column
vector and define $Uv$  by the usual matrix multiplication. It can be shown that
$Uv$ is again a vector state in $\mathcal{H}_C\otimes\mathcal{H}_V^{\otimes 2}$. For $\tau\in \mathfrak{B}(\mathcal{H}_C)\otimes \mathfrak{B}(\mathcal{H}_V\otimes\mathcal{H}_V)$, we define $U\tau$ and $\tau U^{\dagger}$ by the usual matrix multiplication. It is evident that $\mathrm{tr}(U\tau U^{\dagger})=\mathrm{tr}(\tau).$ 

%It can be verified that $R=2\sum_j |\psi_j\rangle\langle \psi_j|-1$ is a reflection operator on $\mathcal{H}_C\otimes\mathcal{H}_V\otimes\mathcal{H}_V$,

%\begin{equation}
%S:=\mathrm{I}\otimes\sum_{j,k=1}^{|V|}|j,k\rangle\langle k,j| \label{}
%\end{equation}

%The unitary operator is $U=S(2\sum_j |\psi_j\rangle\langle \psi_j|-1)$



%The unitary operator on Hilbert space $\mathfrak{B}(\mathcal{H}_C)\otimes \mathfrak{B}(\mathcal{H}_V\otimes\mathcal{H}_V)$ is given by

%$$\Phi(\rho)=U\rho U^{\dagger}$$

\vskip 0.2in

With the operators defined above, a single step of the quantum walk is defined as $\Phi(\rho)=U\rho U^{\dagger}$. For a given $\rho_0\in \mathfrak{B}(\mathcal{H}_C)\otimes \mathfrak{B}(\mathcal{H}_V\otimes\mathcal{H}_V)$ satisfying  $\mathrm{tr}(\rho_0)=1$, the expression $\rho_t=\Phi^t(\rho_0)$ is called the state of the walk at time $t$. The corresponding quantum walk with the initial state $\rho_0$ is represented by the sequence $\{\rho_t\}_{t=0}^{\infty}$. Then the sequence of time iterated states models the temporal evolution of the walk in the density operator picture.


\vskip 0.2in
To formulate the probability distribution of the quantum walks, we introduce quantum measurements for the quantum walks. The quantum measurements are given by a sequence of {\it quantum effects}, denoted by $E_{jk}=\mathbb{I}_c\otimes |j,k\rangle \langle j,k|$ satisfying $\sum_{jk}E_{jk}=\mathbb{I}$.

\vskip 0.2in

If the state of the quantum system is $\rho$ immediately before the measurement, then the probability that the effect $E_{jk}$ occurs (has a yes answer) is given by $P(E_{jk}) = \mathrm{tr}(E_{jk}\rho)$. The state of the system after the measurement is  
$$\frac{E_{jk}\rho E_{jk}}{\mathrm{tr}(E_{jk}\rho E_{jk})}.$$
The probability of finding a walker at the position $|j\rangle$ is $P(j)=\sum_kP(E_{jk})$. 

\vskip 0.2 in

To illustrate our framework described above, we study quantum walks on one-dimensional infinite lattice (see Figure \ref{fig:QWonLine}) with the defining states given in Eq.(\ref{key}),
\begin{equation}
|\psi_j\rangle:=|[\frac{-i}{2},\frac{1}{2}]^T\rangle \otimes |j,j+1\rangle+|[\frac{1}{2},\frac{1}{2}]^T\rangle \otimes |j,j-1\rangle. \label{}
\end{equation}

Then we have \begin{eqnarray}
|\psi_j\rangle\langle \psi_j|=\left[\begin{array}{cc}
\frac{1}{4}& \frac{-i}{4}\\
\frac{i}{4}    & \frac{1}{4}
\end{array}\right]\otimes |j,j+1\rangle\langle j,j+1|+
\left[\begin{array}{cc}
\frac{-i}{4}& \frac{-i}{4}\\
\frac{1}{4}    & \frac{1}{4}
\end{array}\right]\otimes|j, j+1\rangle\langle j,j-1|   \nonumber \\ 
+\left[\begin{array}{cc}
\frac{i}{4}& \frac{1}{4}\\
\frac{i}{4}    & \frac{1}{4}
\end{array}\right]\otimes |j,j-1\rangle\langle j,j+1|+
\left[\begin{array}{cc}
\frac{1}{4}& \frac{1}{4}\\
\frac{1}{4}    & \frac{1}{4}
\end{array}\right]\otimes|j, j-1\rangle\langle j,j-1|.\, \label{}
\end{eqnarray}


\begin{figure}
\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=1.8cm,
semithick]
\tikzstyle{every state}=[fill=red,draw=black,thick,text=white,scale=1]
\node                      (al)                {$\cdots$};
\node[state]         (A)  [right of=al]             {$-2$};
\node[state]         (B) [right of=A] {$-1$};
\node[state]         (C) [right of=B] {$0$};
\node[state]          (D) [right of=C] {$1$};
\node[state]          (E) [right of=D]  {$2$};
\node                   (ar)     [right of=E]           {$\cdots$};
%\node                   (bl)      [below of=al]                {$\cdots$};
%\node                    (br)     [below of=ar]   {$\cdots$};
%\node[state]         (F)[below of=A]    {$|-1-2\rangle$};
%\node[state]         (G) [below of=B] {$|0-1\rangle$};
%\node[state]         (H) [below of=C] {$|10\rangle$};
%\node[state]          (I) [below of=D] {$|21\rangle$};
%\node[state]          (J) [below of=E]  {$|32\rangle$};
\path (al)     edge                        node        {}              (A);
%\path (bl)     edge                        node        {}              (F);
\path (A) edge   node[above] {} (B);
\path (B) edge   node[below] {} (C);
\tikzstyle{every state}=[fill=blue,draw=black,thick,text=white,scale=1]
\path (C) edge  node[left] {} (D);
\path (D) edge  node[right] {} (E);
\path (E) edge node {} (ar);
%\tikzstyle{every state}=[fill=red,draw=black,thick,text=white,scale=1]
\path (A) edge node {} (al);
\path (B) edge  node {} (A);
\path (C) edge  node {} (B);
\path (D) edge  node {} (C);
\path (E) edge   node {} (D);
\path  (ar) edge node {} (E);
\end{tikzpicture}
\end{center}
\caption{Quantum walks on the line}  \label{fig:QWonLine}
\end{figure}


For the initial state \begin{equation}
\rho_0= \left[\begin{array}{cc}
\frac{1}{2}& \frac{1}{2}\\
\frac{1}{2}    & \frac{1}{2}
\end{array}\right]\otimes|0,1\rangle\langle 0,1|,\label{}
\end{equation}

one step of evolution leads to the state 
\begin{eqnarray}
\rho_1=\Phi(\rho_0)=\left[\begin{array}{cc}
\frac{1}{4}& \frac{i}{4}\\
\frac{-i}{4}    & \frac{1}{4}
\end{array}\right]\otimes |1,0\rangle\langle 1,0|+
\left[\begin{array}{cc}
\frac{-1}{4}& \frac{-i}{4}\\
\frac{-1}{4}    & \frac{-i}{4}
\end{array}\right]\otimes|-1, 0\rangle\langle 1,0|   \nonumber \\ 
+\left[\begin{array}{cc}
\frac{-1}{4}& \frac{-1}{4}\\
\frac{i}{4}    & \frac{i}{4}
\end{array}\right]\otimes |1,0\rangle\langle -1,0|+
\left[\begin{array}{cc}
\frac{1}{4}& \frac{1}{4}\\
\frac{1}{4}    & \frac{1}{4}
\end{array}\right]\otimes|-1,0\rangle\langle -1,0|;\, \label{}
\end{eqnarray}

Two consecutive steps of evolution lead to the following state
\begin{eqnarray}
\rho_2=\Phi(\rho_1)=\left[\begin{array}{cc}
\frac{1}{8}& \frac{-i}{8}\\
\frac{i}{8}    & \frac{1}{8}
\end{array}\right]\otimes |2,1\rangle\langle 2,1|+
\left[\begin{array}{cc}
\frac{1}{8}& \frac{-1}{8}\\
\frac{i}{8}    & \frac{-i}{8}
\end{array}\right]\otimes|2,1\rangle\langle 0,1|   \nonumber \\ 
+\left[\begin{array}{cc}
\frac{1}{8}& \frac{-i}{8}\\
\frac{-1}{8}    & \frac{i}{8}
\end{array}\right]\otimes |0,1\rangle\langle 2,1|+
\left[\begin{array}{cc}
\frac{1}{8}& \frac{-1}{8}\\
\frac{-1}{8}    & \frac{1}{8}
\end{array}\right]\otimes|0,1\rangle\langle 0,1|\, \nonumber \\
+\left[\begin{array}{cc}
\frac{1}{8}& \frac{i}{8}\\
\frac{-i}{8}    & \frac{1}{8}
\end{array}\right]\otimes |0,-1\rangle\langle 0,-1|+
\left[\begin{array}{cc}
\frac{-1}{8}& \frac{-i}{8}\\
\frac{-1}{8}    & \frac{-i}{8}
\end{array}\right]\otimes|-2,-1\rangle\langle 0,-1|   \nonumber \\ 
+\left[\begin{array}{cc}
\frac{-1}{8}& \frac{-1}{8}\\
\frac{i}{8}    & \frac{i}{8}
\end{array}\right]\otimes |0,-1\rangle\langle -2,-1|+
\left[\begin{array}{cc}
\frac{1}{8}& \frac{1}{8}\\
\frac{1}{8}    & \frac{1}{8}
\end{array}\right]\otimes|-2,-1\rangle\langle -2,-1|\, \nonumber\\
+\Phi(\left[\begin{array}{cc}
\frac{-1}{4}& \frac{-i}{4}\\
\frac{-1}{4}    & \frac{-i}{4}
\end{array}\right]\otimes|-1, 0\rangle\langle 1,0|+
\left[\begin{array}{cc}
\frac{-1}{4}& \frac{-1}{4}\\
\frac{i}{4}    & \frac{i}{4}
\end{array}\right]\otimes |1,0\rangle\langle -1,0|).\label{}
\end{eqnarray}

\vskip 0.2in
The probability distributions of the walk at the first three steps are computed below:
\begin{itemize}
  \item When $t=0$, $P(0)=1$;
  \item When $t=1$, $P(-1)=P(1)=\frac{1}{2}$;
  \item When $t=2$, $P(-2)=P(2)=\frac{1}{4}$, $P(0)=\frac{1}{2}$.
\end{itemize} 


\section{Concluding remarks}

Discrete-time quantum walks have been formulated in terms of the state vectors in literature. An alternate formulation is introduced in this note. We describe quantum walks in the density operator picture. In the present framework, the action of the unitary channel on a density operator is described by the usual matrix multiplication. This approach offers, in the density operator picture, a mathematical model of unitary transformation of a quantum system in a directed graph.

%\section{Recovering Szegedy's quantum walks}It is easy to see that the quantum walks defined in this article becomes Szegedy's quantum walks when graph $G$ is a regular graph and the coin space $\mathcal{H}_C$ is one-dimensional, i.e, $\mathcal{H}_C=\mathbb{C}$.Let $\mathfrak{D}(\mathcal{H}_C)\subset \mathfrak{B}(\mathcal{H}_C)$ denote the set of positive operators $\rho: \mathbb{C}^{n}\rightarrow \mathbb{C}^{n}$ with $\mathrm{Tr}(\rho)=1$. The operators $\rho$ are the so-called �density operators.�  Thus, an overall state of the quantum walker can be described on the tensor product of the Hilbert spaces: $\mathfrak{B}(\mathcal{H}_C)\otimes \mathfrak{B}(\mathcal{H}_V).$


\begin{thebibliography}{0}


\bibitem{NC2000}

M. Nielsen and I. Chuang, {\it Quantum Computation and Quantum Information} (Cambridge University Press, Cambridge, 2000).


\bibitem{APS12}

S. Attal, F. Petruccione and I. Sinayskiy(2012),  {\it Open quantum walks on graphs},  Phys. Lett. A 376 1545.

\bibitem{APSS12}

S. Attal, F. Petruccione, C. Sabot and I. Sinayskiy(2012),  {\it Open quantum random walks}, J. Stat. Phys. 147 832.

\bibitem{G2008}

S. Gudder, {\it Quantum Markov chains}, J Math. Phys., 49, 072105(2008).

\bibitem{ABNVW01}

A. Ambainis, E. Bach, A. Nayak, A. Vishwanath and J. Watrous, {\it One-dimensional quantum walks},
in Proceedings of the thirty-third annual ACM symposium on Theory of computing, STOC '01 (ACM, New York, NY, USA,
2001) pp. 37-49.

\bibitem{W2001}
J. Watrous, {\it Quantum simulations of classical random walks
and undirected graph connectivity}, Journal of Computer and System
Sciences 62, pp. 376�391 (2001), eprint cs.CC/9812012.


\bibitem{AAKV01}

D. Aharanov, A. Ambainis, J. Kempe and U. Vazirani, {\it Quantum walks on graphs}, in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, (ACM, New York, 2001), pp.50-59.

%\bibitem{FG98}E. Farhi and S. Gutmann, {\it Quantum computation and decision trees}, Phys. Rev. A 58, 915�928 (1998).


\bibitem{K03}

J. Kempe (2003), {\it Quantum random walks - an introductory overview}, Contemp. Phys. {\bf 44}, 307.

%\bibitem{K08}

%N. Konno, in {\em Quantum Potential Theory}, Lecture Notes in Mathematics, edited by U. Franz and M. Schurmann (Springer-Verlag, Heidelberg, 2008), pp.309-452.

%\bibitem{VA08}

%S.E. Venegas-Andraca, {\em Quantum Walks for Computer Scientists}, Morgan and Claypool Publishers (Synthesis Lectures on Quantum Computing), 2008.

%\bibitem{CCDFGS03}A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann and
%D. A. Spielman, 2003, Exponential algorithmic speedup by quantum walk, Proceedings of the 35th ACM Symposium on Theory of Computing, pp. 59�68, eprint quant-ph/0209131.

\bibitem{Konno05}

N. Konno, {\it A new type of limit theorems for the one-dimensional quantum random walk},
Journal of the Mathematical Society of Japan, 57: 1179-1195 (2005).

\bibitem{K06}

V. Kendon, {\it Decoherence in quantum walks - a review}, Struct. in Comp. Sci 17(6) pp 1169-1220 (2006).



%\bibitem{AA2007}

%A. Ambainis, {\it Quantum walk algorithm for element distinctness}, SIAM Journal on Computing, 37:210-239, 2007. Also arXiv:quant-ph/0311001.

%\bibitem{AMC2009}A. M. Childs, {\it Universal computation by quantum walk}, Phys. Rev. Lett. 102, 180501 (2009).


\bibitem{VA12}

S. E. Venegas-Andraca, {\em Quantum walks: a comprehensive review}, Quantum Information Processing vol. 11(5), pp. 1015-1106 (2012).

\bibitem{S04}

M. Szegedy, {\it Quantum Speed-Up of Markov Chain Based Algorithms},  Foundations of Computer Science, 2004. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Pages 32-41.

\bibitem{PRR05}

A. Patel, K. S. Raghunathan and P. Rungta, {\it Quantum random walks do not need a coin toss}, Phys. Rev. A 71, 032347(2005).

\bibitem{W12}
J. D. Whitfield, {\it Reflections in Hilbert Space IV: Quantum walks via Szegedy�s scheme}, Selected Lectures from Whitfield's homepage, May, 2012.

%\bibitem{L2015}C. Liu, {\it From open quantum walks to unitary quantum walks}, arXiv:1502.01680.
















\end{thebibliography}


\end{document}













\newpage%

\addtolength{\topmargin}{13pt}
\setcounter{chapter}{2}


1506.02493.extracted_bib
{NC2000 M. Nielsen and I. Chuang, {Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, 2000).
1506.02493.extracted_bib
{APS12 S. Attal, F. Petruccione and I. Sinayskiy(2012), {Open quantum walks on graphs, Phys. Lett. A 376 1545.
1506.02493.extracted_bib
{APSS12 S. Attal, F. Petruccione, C. Sabot and I. Sinayskiy(2012), {Open quantum random walks, J. Stat. Phys. 147 832.
1506.02493.extracted_bib
{G2008 S. Gudder, {Quantum Markov chains, J Math. Phys., 49, 072105(2008).
1506.02493.extracted_bib
{ABNVW01 A. Ambainis, E. Bach, A. Nayak, A. Vishwanath and J. Watrous, {One-dimensional quantum walks, in Proceedings of the thirty-third annual ACM symposium on Theory of computing, STOC '01 (ACM, New York, NY, USA, 2001) pp. 37-49.
1506.02493.extracted_bib
{W2001 J. Watrous, {Quantum simulations of classical random walks and undirected graph connectivity, Journal of Computer and System Sciences 62, pp. 376�391 (2001), eprint cs.CC/9812012.
1506.02493.extracted_bib
{AAKV01 D. Aharanov, A. Ambainis, J. Kempe and U. Vazirani, {Quantum walks on graphs, in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, (ACM, New York, 2001), pp.50-59. %
1506.02493.extracted_bib
{FG98E. Farhi and S. Gutmann, {Quantum computation and decision trees, Phys. Rev. A 58, 915�928 (1998).
1506.02493.extracted_bib
{K03 J. Kempe (2003), {Quantum random walks - an introductory overview, Contemp. Phys. {44, 307. %
1506.02493.extracted_bib
{K08 %N. Konno, in {\em Quantum Potential Theory, Lecture Notes in Mathematics, edited by U. Franz and M. Schurmann (Springer-Verlag, Heidelberg, 2008), pp.309-452. %
1506.02493.extracted_bib
{VA08 %S.E. Venegas-Andraca, {\em Quantum Walks for Computer Scientists, Morgan and Claypool Publishers (Synthesis Lectures on Quantum Computing), 2008. %
1506.02493.extracted_bib
{CCDFGS03A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann and %D. A. Spielman, 2003, Exponential algorithmic speedup by quantum walk, Proceedings of the 35th ACM Symposium on Theory of Computing, pp. 59�68, eprint quant-ph/0209131.
1506.02493.extracted_bib
{Konno05 N. Konno, {A new type of limit theorems for the one-dimensional quantum random walk, Journal of the Mathematical Society of Japan, 57: 1179-1195 (2005).
1506.02493.extracted_bib
{K06 V. Kendon, {Decoherence in quantum walks - a review, Struct. in Comp. Sci 17(6) pp 1169-1220 (2006). %
1506.02493.extracted_bib
{AA2007 %A. Ambainis, {Quantum walk algorithm for element distinctness, SIAM Journal on Computing, 37:210-239, 2007. Also arXiv:quant-ph/0311001. %
1506.02493.extracted_bib
{AMC2009A. M. Childs, {Universal computation by quantum walk, Phys. Rev. Lett. 102, 180501 (2009).
1506.02493.extracted_bib
{VA12 S. E. Venegas-Andraca, {\em Quantum walks: a comprehensive review, Quantum Information Processing vol. 11(5), pp. 1015-1106 (2012).
1506.02493.extracted_bib
{S04 M. Szegedy, {Quantum Speed-Up of Markov Chain Based Algorithms, Foundations of Computer Science, 2004. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Pages 32-41.
1506.02493.extracted_bib
{PRR05 A. Patel, K. S. Raghunathan and P. Rungta, {Quantum random walks do not need a coin toss, Phys. Rev. A 71, 032347(2005).
1506.02493.extracted_bib
{W12 J. D. Whitfield, {Reflections in Hilbert Space IV: Quantum walks via Szegedy�s scheme, Selected Lectures from Whitfield's homepage, May, 2012. %
1506.02493.extracted_bib
{L2015C. Liu, {From open quantum walks to unitary quantum walks, arXiv:1502.01680.