6 Quantum Markov Chains

%%{ init: { 'flowchart': { 'curve': 'linear' } } }%%
flowchart TD
    A(Classical Walks)-- Quantize by coin -->B(Quantum Walk);
    A-- Stochastic Reset -->C(Stochastic Reset Classical Walk);
    B-- Stochastic Reset -->D(Stochastic Reset Quantum Walk);
    C-.-D;
    D-- Quantize by coin -->E(Quantum Reset Quantum walk);
    C-- ? -->F(Unitary quantum reset):::newwork;
    E-.-F;
    classDef newwork fill:#45f97b,color:#000;

Figure 6.1: Work until now: Our initial proposal to combat the transient nature of the quantum walk was by following a semi-quantum stochastic reset protocol. To further quantise the resetting mechanism, we propose a coined reset formalism. This proved to be too complex, prompting a unitary reset walk, which we shall introduce now.

As suggested in the earlier chapter, we would like to define a unitary quantum resetting protocol unitary for analytical and interpretational simplicity. For this, we reconsider our path until now (Figure 8.1). Instead of quantising the stochastic reset quantum walk via a coin, can we quantise the stochastic reset classical walk directly?

Generalized Coined walks

When we quantised walks in Chapter 2, we attached a 2 level coin whose states represented the selected edge, and by putting the coin into superposition, one can apply a superposition of jumps. We would like to quantise walks on arbitrary undirected graphs using the coined walk formalism.

Graphs can be partitioned into two classes, Class 1 and 2, based of the chromaticity of the graph.

Edge Chromaticity

The edge-chromaticity of a graph is the minimum number of colors that the edges can be colored with such that no two adjacent edges are similarly colored and is denoted by $\rho(G)$.

By Vizing’s theorem¹, $\Delta(G) \le \rho(G) \le \Delta(G)+1$, where $\Delta(G)$ is the max degree of the graph.

Graphs of Class 1 are those where $\Delta(G) = \rho(G)$ and graphs of Class 2 are the others. Walks on Class 1 graphs can be quantised by the coin - position formalism similar to the one introduced in Chapter 2, whereas walks on Class 2 graphs can be quantised by a walk on the edges rather than the nodes². However, we’re still restricted to undirected graphs.

Szegedy Walks

It is known that discrete time Markov chains do not naturally quantise via the coin formalism³. Szegedy³ came up with a formalism to quantise symmetric irreducible Markov chains by using the bipartite double cover of the underlying graph (Figure 6.2). This was then generalized to ergodic chains by Magniez et al.⁴. What follows is a brief introduction to the generalized Szegedy walks.

Figure 6.2: Duplication Process on a graph². The nodes are copied, and edges are drawn between the two sets if the pair of nodes had a connecting edge in the original graph.

Formalism

Let $P$ be the transition matrix of a reversible Markov chain. Let $P^*$ be the time reversed Markov chain of $P$.

For a state $|\psi\rangle \in \mathcal{H}$, let $\Pi_\psi = |\psi\rangle\langle \psi |$. For a subspace $\mathcal{K}$ of $\mathcal{H}$ spanned by a set of mutually orthogonal states $\{|\psi_i\rangle : i \in I\}$, let $\Pi_{\mathcal{K}} = \sum_{i\in I}\Pi_{\psi_i}$ be the projector onto $\mathcal{K}$ and $\mathcal{R}_{\mathcal{K}} = 2\Pi_{\mathcal{K}} - \text{Id}$ be a reflection through $\mathcal{K}$.

Let $\mathcal{A} = \text{Span}(|x\rangle|p_x\rangle: x\in X)$ and $\mathcal{B} = \text{Span}(|p_y^*\rangle|y\rangle: y\in Y)$ be subspaces of $\mathcal{H} = \mathbb{C}^{|X|\times |X|}$, where

\[|p_x\rangle = \sum_{y\in X}\sqrt{p_{xy}} |y\rangle; |p_y^*\rangle = \sum_{x\in X}\sqrt{p_{yx}^*} |x\rangle\]

where $p_{ij}, p_{ij}^* \text{ are elements of }P, P^*\text{ respectively}$, and $X$ is the set of nodes, $Y$ is the set of nodes after duplication.

Quantum Markov Chain

The quantised version of the Markov chain $P$ is defined to be the unitary operation $W(P) = \mathcal{R}_{\mathcal{B}}\mathcal{R}_{\mathcal{A}}$ and is called the Szegedy walk. Where defined, the Szegedy walk is equivalent to two steps of the Coined quantum walk⁵.

The Discriminant matrix

For an ergodic Markov chain $P$ with stable distribution $\pi$, we define

\[D(P) = \text{diag}(\pi)^{1/2} \cdot P \cdot \text{diag}(\pi)^{-1/2}\]

as the discriminant matrix.

Properties

On $\mathcal{A}+\mathcal{B}$, eigenvalues of $W(P)$ that have non-zero imaginary part are $e^{\pm 2i\theta_1}, \dots, e^{\pm 2i\theta_l}$, with same multiplicity.
On $\mathcal{A}\cap\mathcal{B}$, $W(P)$ acts as the identity. The left (and right) singular vectors of $D$ with singular value 1 span this space.
On $\mathcal{A}\cap\mathcal{B^\perp}$ and $\mathcal{A^\perp}\cap\mathcal{B}$, the operator acts as $-\text{Id}$. The $\mathcal{A}\cap\mathcal{B^\perp}$ (resp. $\mathcal{A^\perp}\cap\mathcal{B}$), is spanned by the set of left (resp. right) singular vectors of D
W(P) has no other eigenvalues on $\mathcal{A}+\mathcal{B}$; on $\mathcal{A}^\perp\cap\mathcal{B}^\perp$ it acts as $\text{Id}$

Szegedy Search or the Quantum Hitting Time

Of the many ways to define the search algorithm (refer to Chapter 3 for an introduction) for Szegedy walks, we shall look at two protocols, one which is easy to understand and the other easy to analyse. The original paper by Szegedy³ proposed the following protocol -

Modify the classical Markov chain to make all the marked vertices sinks (Figure 6.3).

\[ p^\prime_{xy} = \begin{cases} p_{xy}, &x \notin G\\ \delta_{xy}, &x \in G \end{cases} \]

Define $W^\prime(P)$ as the quantum Markov chain by the usual protocol.
Define the initial state

\[|\psi(0)\rangle = \frac{1}{\sqrt{n}}\sum_{\substack{x\in X\\ y \in Y}}\sqrt{p_{xy}}|x\rangle |y\rangle\]

Finally, define the quantum hitting time such that \[F(T) \ge 1 - \frac{g}{n}\] where \[F(T) = \frac{1}{T+1}\sum_{t=0}^{T}\Big\lVert |\psi(t)\rangle - |\psi(0)\rangle\Big\rVert^2; g = |G|\]

Figure 6.3: Duplication Process of a graph with marked vertex $3$². All edges going outwards from $x_3$ and $y_3$ are broken, making the graph directed

Defined by this protocol, the quantum hitting time is quadratically smaller than the classical hitting time³ for the 1D case.

A later modification⁴ defined the search operation via a Grover-like oracle. This was easier to analyse, and the connection between the spectral gap of the discriminant matrix (Section 6.2.1) and the quadratic speedup attained by the walk is clearer. We leave the exact protocol to reference⁴, but only outline the steps.

Prepare the initial state $|\pi\rangle|0^Tks\rangle$, where \[|\pi\rangle_d = \sum_{x\in X} \sqrt{\pi_x}|x\rangle |p_x\rangle = \sum_{y\in X} \sqrt{\pi_x}|x\rangle |p_x\rangle\]
First apply the Grover oracle \[\mathcal{G}(|x\rangle_d|y\rangle_d |z\rangle) = \begin{cases}-|x\rangle_d|y\rangle_d|z\rangle, & \text{if } x \in G\\+|x\rangle_d|y\rangle_d|z\rangle, & \text{otherwise}\end{cases}\]
Apply a phase estimation circuit to the quantum walk, repeated $k$ times.
Repeat steps 2 and 3 $T$ times.
Observe the first register, by a projective measurement in the computational basis. Denote by $\bar{x}$
With high probability, output $\bar{x}$ lies in $G$

If the eigenvalue gap of the Markov chain is $\delta$, and $\frac{|G|}{N} \ge \epsilon \ge 0$, the cost to perform this circuit is of order $\left(\frac{1}{\sqrt{\epsilon\delta}} \log \frac{1}{\sqrt \epsilon}\right)$ calls to the walk operation⁴. Contrast this with the classical search which requires $\frac{1}{\delta\epsilon}$ steps of the Markov walk, we see the quadratic speedup¹.

Therefore, one can find the spectral gap $\delta$ of $P$ and compare the search speed of two chains. This Szegedy formalism beautifully sets up the stage for a truly unitary quantum reset quantum walk protocol which can be analysed for any graph structure without having to resort to simulation techniques.

# Quantum Markov Chains {#sec-szegedy} ```{mermaid} %%| label: fig-work %%| fig-cap: "Work until now: Our initial proposal to combat the transient nature of the quantum walk was by following a semi-quantum stochastic reset protocol. To further quantise the resetting mechanism, we propose a coined reset formalism. This proved to be too complex, prompting a unitary reset walk, which we shall introduce now." %%{ init: { 'flowchart': { 'curve': 'linear' } } }%% flowchart TD A(Classical Walks)-- Quantize by coin -->B(Quantum Walk); A-- Stochastic Reset -->C(Stochastic Reset Classical Walk); B-- Stochastic Reset -->D(Stochastic Reset Quantum Walk); C-.-D; D-- Quantize by coin -->E(Quantum Reset Quantum walk); C-- ? -->F(Unitary quantum reset):::newwork; E-.-F; classDef newwork fill:#45f97b,color:#000; ``` As suggested in the earlier chapter, we would like to define a unitary quantum resetting protocol unitary for analytical and interpretational simplicity. For this, we reconsider our path until now (@fig-work). Instead of quantising the stochastic reset quantum walk via a coin, can we quantise the stochastic reset classical walk directly? ## Generalized Coined walks When we quantised walks in @sec-quantum, we attached a 2 level coin whose states represented the selected edge, and by putting the coin into superposition, one can apply a superposition of jumps. We would like to quantise walks on arbitrary undirected graphs using the coined walk formalism. Graphs can be partitioned into two classes, Class 1 and 2, based of the chromaticity of the graph. ::: {.callout-tip} ## Edge Chromaticity The edge-chromaticity of a graph is the minimum number of colors that the edges can be colored with such that no two adjacent edges are similarly colored and is denoted by $\rho(G)$. ::: By Vizing's theorem @noauthor_vizings_2023, $\Delta(G) \le \rho(G) \le \Delta(G)+1$, where $\Delta(G)$ is the max degree of the graph. Graphs of Class 1 are those where $\Delta(G) = \rho(G)$ and graphs of Class 2 are the others. Walks on Class 1 graphs can be quantised by the coin - position formalism similar to the one introduced in @sec-quantum, whereas walks on Class 2 graphs can be quantised by a walk on the edges rather than the nodes @portugal_quantum_2018. However, we're still restricted to undirected graphs. ## Szegedy Walks It is known that discrete time Markov chains do not naturally quantise via the coin formalism @szegedy_quantum_2004. Szegedy @szegedy_quantum_2004 came up with a formalism to quantise symmetric irreducible Markov chains by using the bipartite double cover of the underlying graph (@fig-dup). This was then generalized to ergodic chains by Magniez et al. @magniez_search_2011. What follows is a brief introduction to the generalized Szegedy walks. ![Duplication Process on a graph @portugal_quantum_2018. The nodes are copied, and edges are drawn between the two sets if the pair of nodes had a connecting edge in the original graph.](./images/03-19-22-24.png){#fig-dup width=75%} ### Formalism {#sec-szegedy-formalism} Let $P$ be the transition matrix of a reversible Markov chain. Let $P^*$ be the time reversed Markov chain of $P$. For a state $|\psi\rangle \in \mathcal{H}$, let $\Pi_\psi = |\psi\rangle\langle \psi |$. For a subspace $\mathcal{K}$ of $\mathcal{H}$ spanned by a set of mutually orthogonal states $\{|\psi_i\rangle : i \in I\}$, let $\Pi_{\mathcal{K}} = \sum_{i\in I}\Pi_{\psi_i}$ be the projector onto $\mathcal{K}$ and $\mathcal{R}_{\mathcal{K}} = 2\Pi_{\mathcal{K}} - \text{Id}$ be a reflection through $\mathcal{K}$. Let $\mathcal{A} = \text{Span}(|x\rangle|p_x\rangle: x\in X)$ and $\mathcal{B} = \text{Span}(|p_y^*\rangle|y\rangle: y\in Y)$ be subspaces of $\mathcal{H} = \mathbb{C}^{|X|\times |X|}$, where $$|p_x\rangle = \sum_{y\in X}\sqrt{p_{xy}} |y\rangle; |p_y^*\rangle = \sum_{x\in X}\sqrt{p_{yx}^*} |x\rangle$$ where $p_{ij}, p_{ij}^* \text{ are elements of }P, P^*\text{ respectively}$, and $X$ is the set of nodes, $Y$ is the set of nodes after duplication. ::: {.callout-tip} ## Quantum Markov Chain The quantised version of the Markov chain $P$ is defined to be the unitary operation $W(P) = \mathcal{R}_{\mathcal{B}}\mathcal{R}_{\mathcal{A}}$ and is called the Szegedy walk. Where defined, the Szegedy walk is equivalent to two steps of the Coined quantum walk @wong_equivalence_2017. ::: :::{#sec-desc .callout-tip} ## The Discriminant matrix For an ergodic Markov chain $P$ with stable distribution $\pi$, we define $$D(P) = \text{diag}(\pi)^{1/2} \cdot P \cdot \text{diag}(\pi)^{-1/2}$$ as the discriminant matrix. ::: ### Properties 1. On $\mathcal{A}+\mathcal{B}$, eigenvalues of $W(P)$ that have non-zero imaginary part are $e^{\pm 2i\theta_1}, \dots, e^{\pm 2i\theta_l}$, with same multiplicity. 2. On $\mathcal{A}\cap\mathcal{B}$, $W(P)$ acts as the identity. The left (and right) singular vectors of $D$ with singular value 1 span this space. 3. On $\mathcal{A}\cap\mathcal{B^\perp}$ and $\mathcal{A^\perp}\cap\mathcal{B}$, the operator acts as $-\text{Id}$. The $\mathcal{A}\cap\mathcal{B^\perp}$ (resp. $\mathcal{A^\perp}\cap\mathcal{B}$), is spanned by the set of left (resp. right) singular vectors of D 4. W(P) has no other eigenvalues on $\mathcal{A}+\mathcal{B}$; on $\mathcal{A}^\perp\cap\mathcal{B}^\perp$ it acts as $\text{Id}$ ## Szegedy Search or the Quantum Hitting Time {#sec-qht} Of the many ways to define the search algorithm (refer to @sec-search for an introduction) for Szegedy walks, we shall look at two protocols, one which is easy to understand and the other easy to analyse. The original paper by Szegedy @szegedy_quantum_2004 proposed the following protocol - 1. Modify the classical Markov chain to make all the marked vertices sinks (@fig-dup-marked). $$ p^\prime_{xy} = \begin{cases} p_{xy}, &x \notin G\\ \delta_{xy}, &x \in G \end{cases} $$ 2. Define $W^\prime(P)$ as the quantum Markov chain by the usual protocol. 3. Define the initial state $$|\psi(0)\rangle = \frac{1}{\sqrt{n}}\sum_{\substack{x\in X\\ y \in Y}}\sqrt{p_{xy}}|x\rangle |y\rangle$$ 4. Finally, define the quantum hitting time such that $$F(T) \ge 1 - \frac{g}{n}$$ where $$F(T) = \frac{1}{T+1}\sum_{t=0}^{T}\Big\lVert |\psi(t)\rangle - |\psi(0)\rangle\Big\rVert^2; g = |G|$$ ![Duplication Process of a graph with marked vertex $3$ @portugal_quantum_2018. All edges going outwards from $x_3$ and $y_3$ are broken, making the graph directed](./images/03-19-22-30.png){#fig-dup-marked width=75%} Defined by this protocol, the quantum hitting time is quadratically smaller than the classical hitting time @szegedy_quantum_2004 for the 1D case. A later modification @magniez_search_2011 defined the search operation via a Grover-like oracle. This was easier to analyse, and the connection between the spectral gap of the discriminant matrix (@sec-szegedy-formalism) and the quadratic speedup attained by the walk is clearer. We leave the exact protocol to reference @magniez_search_2011, but only outline the steps. 1. Prepare the initial state $|\pi\rangle|0^Tks\rangle$, where $$|\pi\rangle_d = \sum_{x\in X} \sqrt{\pi_x}|x\rangle |p_x\rangle = \sum_{y\in X} \sqrt{\pi_x}|x\rangle |p_x\rangle$$ 2. First apply the Grover oracle $$\mathcal{G}(|x\rangle_d|y\rangle_d |z\rangle) = \begin{cases}-|x\rangle_d|y\rangle_d|z\rangle, & \text{if } x \in G\\+|x\rangle_d|y\rangle_d|z\rangle, & \text{otherwise}\end{cases}$$ 3. Apply a phase estimation circuit to the quantum walk, repeated $k$ times. 4. Repeat steps 2 and 3 $T$ times. 5. Observe the first register, by a projective measurement in the computational basis. Denote by $\bar{x}$ 6. With high probability, output $\bar{x}$ lies in $G$ If the eigenvalue gap of the Markov chain is $\delta$, and $\frac{|G|}{N} \ge \epsilon \ge 0$, the cost to perform this circuit is of order $\left(\frac{1}{\sqrt{\epsilon\delta}} \log \frac{1}{\sqrt \epsilon}\right)$ calls to the walk operation @magniez_search_2011. Contrast this with the classical search which requires $\frac{1}{\delta\epsilon}$ steps of the Markov walk, we see the quadratic speedup^[Technically, this is not a quadratic speedup due to the extra $\log\frac{1}{\epsilon}$ term, and it was only later shown @krovi_quantum_2016 using a protocol of eigenvalue estimation to hold true for all ergodic chains with any number of marked vertices]. Therefore, one can find the spectral gap $\delta$ of $P$ and compare the search speed of two chains. This Szegedy formalism beautifully sets up the stage for a truly unitary quantum reset quantum walk protocol which can be analysed for any graph structure without having to resort to simulation techniques.