$\newcommand{\I}{\mathrm{i}} \newcommand{\E}{\mathrm{e}} \newcommand{\D}{\mathop{}\!\mathrm{d}} \DeclareMathOperator{\Tr}{Tr} \newcommand{\bra}[1]{\langle{#1}|} \newcommand{\ket}[1]{|{#1}\rangle} \newcommand{\braket}[1]{\langle{#1}\rangle} \newcommand{\bbraket}[1]{\langle\!\langle{#1}\rangle\!\rangle} \newcommand{\bm}{\boldsymbol}$

Lectures on advanced quantum mechanics

Cluster state and quantum computation

The most basic model of quantum computation is the circuit, in which an initial state, usually a product state $\ket{0}^N$ of $N$ qubits, is acted upon by a sequence of universal one and two qubits gates; for instance the pauli $\bm \sigma = (X,Y,Z)$, hadamard $\mathsf{H}$, the phase $\mathsf{S}$, and $\pi/4$ phase $\mathsf{T}$ one qubit gates, complemented with the two qubits $\mathsf{CNOT}$ gate. Because of its universality the circuit model is also useful as a representation of other quantum computation models. Another important class is the topological model, whose first formulation is based on the toric code of Kitaev. In this case the computational resource is an entangled quantum state, the ground state of a many-body hamiltonian. Excitations of the toric code ground state are anyons, topological “particles” that take a phase when exchanged (not necessarily 0, as for bosons, or $\pi$, as for fermions). Braiding these quasiparticles is thus used to implement logical gates. A third important quantum computational model is the cellular automaton. The idea is to apply a local unitary to a set of qubits (arranged in a line or a lattice) to an initial state, in order to, by discrete time iteration, update the state of the systems to eventually get a useful entangled state. The unitary generally implements a simple rule, in analogy with the classical cellular automata, and is applied in parallel; its homogeneity ensures translational invariance. The three models of quantum computation, circuit, topological, and automaton, are equivalently universal, in the sense that they can implement any $N$-body unitary operator.

A variant of the topological quantum model of computation is the one based on teleportation; it is called measurement based quantum computation. Let us start with an example:

The initial state is the product $\ket{t_0} = \ket{\psi}\otimes\ket{0} = a\ket{00} + b \ket{10}$, after the $\mathsf{CNOT}$ we get the entangled state

$$\ket{t_1} = a \ket{00} + b \ket{11},$$

which is our computational resource. To exploit this resource we measure the first qubit in the base $\ket{\pm}$ of the $X$ operator. Note that $\ket{t_1}$ writes EX,

$$\ket{t_1} = P_+ \ket{t_1} + P_- \ket{t_1} = \frac{\ket{+}}{\sqrt{2}}\big(a\ket{0} + b \ket{1}\big) + \frac{\ket{+}}{\sqrt{2}}\big(a\ket{0} - b \ket{1}\big)$$

where we used the projectors $P_\pm = \ket{\pm}\bra{\pm}$, the pre-measurement state:

$$\frac{\ket{+}}{\sqrt{2}}\ket{\psi} + \frac{\ket{-}}{\sqrt{2}} Z\ket{\psi}.$$

The final state of the second qubit, after the measurement, is then

$$\ket{\mathrm{out}} = Z^b \ket{\psi}$$

according to the result $b$ of the first qubit measurement. As a result the circuit teleports the $\ket{\psi}$ state, possibly modified by the gate $Z$. Had we measured the first qubit in other basis, we could obtain other one qubit gate applied to the teleported state. Indeed, the slightly modified circuit

in which we measure the first qubit in the base of the operator $O = \bm{n} \cdot \bm \sigma$, and $\bm n = (\cos\theta, \sin\theta,0)$, leads to the output state EX:

$$\ket{\mathrm{out}} = \E^{-\I \theta Z/2} Z^b \ket{\mathrm{in}}.$$

Hint. Use the eigenvectors

$$\ket{\theta_\pm} = \frac{1}{\sqrt{2}} \begin{pmatrix} \E^{-\I\theta/2} \\ \pm\E^{\I\theta/2} \end{pmatrix}$$

of the $O$ and the corresponding projectors to write the state just before the measure, as in the previous calculation.

We observe that an appropriated measurement of on a single qubit on a previously prepared entangled state, is a computational resource that can be used to effectively apply a logical gate to an initial state; in the case of the last circuit we transformed the initial arbitrary state $\ket{\mathrm{in}}$, into a rotated output one. As a result of the measurement, the entanglement in the system decreases, which is consistent with the notion of entanglement as a resource. In addition, too much entanglement, as for instance a thermal state (maximally entangled), would not be useful because the sequence of measurements cannot be distinguished from a random processes, which in fact can be efficiently implemented by a classical computer. Therefore, we need a useful entangled state: the cluster state satisfies these requirements, one qubits measurements can implement in it one qubit gates and the $\mathsf{CNOT}$ gate, leading to universal computing.

Cluster state on a graph

A graph $G=(V,E)$ is a set of $|V|$ vertices $x \in V$ linked by edges $E = \{(x,y) \mid x, y \in V\}$:

(left) A graph $G=(V,E)$ of $|V| = 5$ qubits, initially in the state $\ket{+}$; (right) a cluster state obtained by application of the gate $\mathsf{CZ}$ to each edge in $E$.

The graph $G$ of the figure corresponds to the set of vertices $V=\{0,1,2,3,4\}$ and the set of edges $E = \{(0,1),(0,4),(1,2),(2,3),(2,4),(3,4)\}$. To construct the cluster state we associate to each node $x \in V$ a quantum state $\ket{+}$ (the 1 eigenvalue eigenvector of $X$), then we apply the controlled phase gate

$$\mathsf{CZ}(x,y) = \frac{1+Z_x}{2} \otimes 1_y + \frac{1-Z_x}{2} \otimes Z_y = \mathrm{diag}(1,1,1,-1),$$

which change the sign of the $\ket{11}$ amplitude, to each edge $(x,y) \in E$; therefore,

\begin{equation} \label{e:C} \ket{C} = \prod_{(x,y)\in E} \mathsf{CZ}(x,y) \ket{+}^N \end{equation}

where $N = |V|$ is the number of qubits, and to simplify the notation we write the kronecker product as a product of kets.

The hilbert space of the graph $\mathcal{H}(G)$ is spanned by the vectors

$$\ket{s} = \ket{s_0} \otimes \cdots \otimes \ket{s_{N-1}} = \ket{s_0\ldots s_{N-1}} \in \mathcal{H}(G), \; s_x=\{0,1\}, \; x = 0,\ldots,N-1.$$

In this basis the action of the controlled phase gate is

$$\mathsf{CZ}(x,y) \ket{\ldots s_x \ldots s_y \ldots} = (-1)^{s_x s_y}\ket{\ldots s_x \ldots s_y \ldots}.$$

The string $\{s_0\ldots s_{N-!}\}$ is the binary representation of the integer $s \in [0, 2^N -1]$ (the equivalent of the classical configuration of a set of $N$ ising spins).

Example: two and three qubits

The simplest cluster state is the one formed by two qubits:

$$\ket{C_2} = \mathsf{CZ}(0,1) \ket{++} = \frac{1}{2} \big( \ket{00} + \ket{01} + \ket{10} - \ket{11}\big) = \mathsf{H} \otimes 1_2 \ket{\Phi_+}$$

where the last equality shows that the $\ket{C_2}$ state is equivalent to a bell state up to one qubit operations (here the hadamard gate $\mathsf{H}$). It is straightforward to show that the schmidt decomposition of $\ket{C_2}$ leads to two $p_n = 1/2$ ($n=1,2$) eigenvalues of the reduced density matrix, which implies that the von Neumann entropy is maximal:

$$S_1[C_2] = -\sum_{n=\{1,2\}} p_n \log p_n = 1.$$

The case of three qubits can be represented by the circuit

which gives EX

$$\ket{C_3} = \frac{1}{2^{3/2}} \sum_{s_0, s_1, s_2} (-1)^{s_0 s_1 + s_0 s_2 + s_1 s_2} \ket{s_0 s_1 s_2},$$

or explicitly

$$\ket{C_3} = \frac{1}{2^{3/2}} \big( \ket{000} + \ket{001} + \ket{010} - \ket{011} + \ket{100} - \ket{101} - \ket{110} - \ket{111} \big).$$

Note that in the sum, the exponent is computed using operations in the finite field $\mathrm{GF}(2)$, addition and multiplication modulo 2.

Hamiltonian and stabilizers

The stabilizer of a state $\ket{\psi}$ is a subgroup $\mathcal{S}$ of the pauli group $\mathcal{P}$ generated by a set of mutually commuting operators $\{g_0, g_1, \ldots\}$ (essentially products of pauli matrices) satisfying $g_n \ket{\psi} = \ket{\psi}$; the particular states $\ket{i_L}$ satisfying this equation for all $n$ are logical states. Whence, the quantum state $\ket{i_L}$ is a common eigenvector of the stabilizers with eigenvalue 1 (the subgroup $\mathcal{S}$ do not contain the matrix $-1$). We show now that the stabilizer formalism reveals the rich structure of the cluster state $\eqref{e:C}$.

We reconsider the construction of the cluster state to identify step by step the relevant operators with eigenvalue 1. A graph of only one qubit in state $\ket{+}$ is easily related with the operator $X$, which is its stabilizer. Adding a second qubit (also in the state $\ket{+}$) and applying $\mathsf{CZ}$ we obtain the cluster state $\ket{C_2}$, and we want to know how this state is modified by the (previous) stabilizer $X$:

$$X_0 \mathsf{CZ}(0,1) \ket{++} = \mathsf{CZ}(0,1) X_0 Z_1 \ket{++}$$

where $0$ and $1$ refer to the respective qubits number (vertices of the graph). Multiplying this expression by $Z_1$ (note that it commutes with everything), we get

$$X_0 Z_1 \mathsf{CZ}(0,1) \ket{++} = \mathsf{CZ}(0,1) \ket{++}$$

which is just a stabilizer of $\ket{C_2}$. Adding other neighbors, say $y$, to $0$ will add to the stabilizer the corresponding $Z_y$, therefore giving (by recurrence EX) the form

$$K_x = X_x \prod_{(x,y) \in N_x} Z_y$$

of the stabilizer operator associated to vertex $x$, where $N_x$ is the set of neighbors of $x$ ($|N_x|$ is the degree of node $x$). Note that the set of $K_x$ is commuting, and its cardinality coincides with the number of nodes, therefore the general cluster state of a graph $\ket{C}$ satisfying

$$K_x \ket{C} = \ket{C}, \; \forall x,$$

is unique. We can then write the stabilizer set explicitly

$$\mathcal{S} = \{K \mid [K,K_x] = 0, \forall x \in V\}, \; |\mathcal{S}| = N.$$

We observe that when a stabilizer is applied to the “up” state

$$K_x \ket{0}^N = X_x \ket{0}^N = \ket{0\ldots 1 \ldots 0} \; \Rightarrow \; \braket{0|X|0}=0$$

the new state is orthogonal to it. This leads us to the formula

\begin{equation} \label{e:CK} \ket{C} = \frac{1}{2^{N/2}} \prod_{x \in V} \big(1 + K_x \big) \ket{0}^N \end{equation}

that express the cluster state as a superposition of $2^N$ (orthogonal) terms, spanning $\mathcal{H}(G)$. Note that $K_x(1 + K_x) = 1 + K_x$, from which one deduce that $\ket{C}$ is effectively eigenvector of $K_x$ with eigenvalue 1.

Because $\mathcal{S} = N$ the dimension of the logical subspace is 0, and the cluster state do not code any logical qubit. We show below that a modification of the set of stabilizers may lead to a “degeneracy” of the cluster state which results in a nontrivial logical subspace: we can associate a hamiltonian to the graph $G$ and the corresponding cluster state $\ket{C}$.

As a matter of fact, we find that $\ket{C}$ is the unique ground state of the hamiltonian

\begin{equation} \label{e:H} H_C = -J \sum_{x \in V} K_x = -J \sum_x \prod_{y \in N_x} X_x Z_y \end{equation}

formed by a sum over the stabilizers of $\ket{C}$:

$$H_C \ket{C} = -NJ \ket{C},$$

where $-NJ$ is the lowest possible energy. We remark that each term of $H_C$ is a local multibody interaction of neighboring qubits; $J=1$ is the energy scale, which can be taken as the energy unit. We may then, think the cluster state as a genuine phase of matter, since it is a ground state of a local hamiltonian. It is worth noting that, although the cluster state is unique, in the framework of a system defined by a hamiltonian, degeneracy is possible, depending on the boundary conditions: for instance on a regular lattice, where the boundary stabilizers are set to zero.

In summary, given a graph $G=(V,E)$ we define a hilbert space $\mathcal{H}(G)$ of dimension $2^N$, where $N=|V|$, and a hamiltonian $H_C$ which is a superposition of “cluster” operators $K_x, x\in V$; these operators are the stabilizers of the cluster state $\ket{C}$, the ground state of $H_C$.

The one dimensional cluster hamiltonian

In the special case of the one dimensional lattice with open boundary conditions

$$H_C^{(1)} = - \sum_{x=1}^{N-2} Z_{x-1} X_x Z_{x+1}$$

the cluster state $\ket{C^{(1)}}$ is 4-fold degenerate, as can be seen by the fact that it is stabilized by $N-2$ operators $K_x$ ($x=1,\ldots,N-2$), thus leaving free two qubits. Of course each $K_x$ is an integral of motion of $H_C^{(1)}$. The spin $1/2$ chain with the cluster interaction, with open or periodic boundary conditions, is completely integrable, in the sense that it can be transformed into a system of free particles.

We also find two global symmetries

$$P_e = \prod_{x \in e} X_x, \; P_o = \prod_{x \in o} X_x, \quad e = \{0,2,4, \ldots\}, \; o = \{1,3,5, \ldots\}$$

It is easy to verify that reversing the direction of every two spins leaves invariant the system, the two (parity symmetry) operators $P_{e,o}$ commute with the hamiltonian $H_C^{(1)}$. The parity symmetry is associated with the $\mathbb{Z}_2 \times \mathbb{Z}_2$ group whose generators are precisely $P_{e,o}$ (for example, the quantum ising model has a $\mathbb{Z}_2$ symmetry).

In addition we observe that the operators $P_{e,o}$ commute with $K_x$, however $\ket{C^{(1)}}$ is not in their eigenstate space, we can therefore view these symmetries as the logical operators of the “cluster” code, spanned by the 4-fold degenerated ground state. Indeed,

$$[P_{e,o}, \mathsf{CZ}] = 0, \quad \mathsf{CZ} = \prod_{(x,y) \in E} \mathsf{CZ}(x,y)$$

which implies that EX

$$\braket{C^{(1)} | P_n | C^{(1)}} = 0, \; P_n \in \{P_e, P_o, P_eP_o\}$$

which shows that the four states $\{\ket{C^{(1)}}, P_n \ket{C^{(1)}}\}$ are orthogonal and therefore span the ground state subspace of $H^{(1)}_C$.

Entanglement entropy

To measure the entanglement of the cluster state $\eqref{e:C}$, which is a pure state that can be associated to the time independent hamiltonian $\eqref{e:H}$, we may use the von Neumann entropy: we partition the system into two sets of nodes $x \in A$ and $x \in B$, such that $A \cup B = V$, and compute

$$S_A = -\Tr \rho_A \log \rho_A, \; \rho_A = \Tr_B \ket{C} \bra{C}$$

where $\Tr_B$ is the partial trace over the set $B$ ($\log 2 = 1$). For an isolated system in thermodynamic equilibrium $\rho_A$ is the microcanonical density matrix, and the entropy is extensive, its value is proportional to the system’s size ($|A| = N_A$, the number of sites in the partition $A$). We do not expect for our system, which is in the ground state of $H_C$, to satisfy this law. In fact, invoking the third law of thermodynamics (Nernst theorem), we would expect that the entropy of a unique state should be zero: the zero temperature state is dominated by the energy of the system, and the minimum energy configuration is unique. However, it is known that the ground state of some quantum systems can be disordered and therefore have a finite entropy. One example is the Heisenberg antiferromagnet. We show now that the cluster state satisfy an area law for the entanglement entropy: it is proportional to the size of the boundary $\partial A$ between the two regions.

The product $\eqref{e:CK}$ can be transformed into a sum over the whole stabilizer group

$$\ket{C} = \frac{1}{2^{|V|/2}} \prod_{x \in V} \big(1 + K_x\big) \ket{0}^{|V|} = \frac{1}{2^{|V|/2}} \sum_{K \in \mathcal{S}} K \ket{0}^{|V|},$$

where $|\mathcal{S}| = 2^{|V|}$. Each $K$ is a product of pauli matrices:

$$K = \sigma_0^{b_0} \sigma_1^{b_1} \ldots \sigma_{|V|-1}^{b_{|V|-1|}} = \sigma^b$$

where we introduced the notation $\sigma_x = 1_2, X, Y, Z$ is one of the pauli matrices (including the identity) of vertex $x$, $\sigma = (\sigma_0, \ldots, \sigma_{|V|-1})$ and $b = (b_0, \ldots, b_{|V|-1})$ are vectors of pauli and binary numbers, and the notation $\sigma^b$ stands for the kronecker product of paulis each of which to the power $0$ or $1$. Using this notation it is easy to write $\ket{C}$ as a superposition of terms belonging to different subsets of $V$. We also introduce the notion of support of an operator:

$$\mathrm{supp} K = \{x \in V \mid \sigma_x^{b_x} \ne 1_2\}$$

it is then the set of nodes over which $K$ acts on nontrivially.

We partition the graph $G$ into two domains $A$ and $B$. The boundary between $A$ and $B$ cut the edges $(x,y)$ with $x \in A$ and $y \in B$. We distinguish among the stabilizers $K$ those $K_{A_\circ}$ whose support is entirely within $A$, this set of nodes is called $A_\circ$ (the interior of $A$), those $K_{B_\circ}$, equivalently, with support in $B_\circ$, and finally $K_{AB}$ whose support belong to the interface between $A$ and $B$. We can split the domain $V$ into three nonoverlapping sets of nodes $V = A_\circ \cup AB \cup B_\circ$ according to the support of $K$. The product $\eqref{e:CK}$ can then be written as a product of three nonoverlapping sets of nodes $A_\circ, AB, B_\circ$:

$$\ket{C} = \frac{1}{2^{|V|/2}} \prod_{x \in AB} \big(1 + K_x\big) \prod_{x \in A_\circ} (1 + K_x\big) \prod_{x \in B_\circ} (1 + K_x\big) \ket{0}^{|A|} \ket{0}^{|B|}.$$

Noting that the last two products give

$$\ket{C_{A_\circ}} = \frac{1}{2^{|A_\circ|/2}} \prod_{x \in A} (1 + K_x\big) \ket{0}^{|A|},\quad \ket{C_{B_\circ}} = \frac{1}{2^{|B_\circ|/2}} \prod_{x \in B_\circ} (1 + K_x\big) \ket{0}^{|B|} $$

the cluster states of the subgraphs $A_\circ$ and $B_\circ$ we get

$$\ket{C} = \frac{1}{2^{|AB|/2}} \prod_{x \in \partial A} (1 + K_x\big) \ket{C_A} \ket{C_B},$$

note the change in the normalization factor: this last product has $|AB|$ terms, corresponding to the set of $K_x$ operators with support over nodes adjacent to the interface of $A$ and $B$: the number of edges cut by the interface. Note also that $\ket{C}$ belongs to $\mathcal{H}(G)= \mathcal{H}_A \otimes \mathcal{H}_B$ and $\ket{C_{A_\circ}} \in \mathcal{H}_A$ and $\ket{C_{B_\circ}} \in \mathcal{H}_B$ are cluster states of open boundary graphs. This last expression is in fact the schmidt decomposition of the cluster state EX:

\begin{equation} \label{e:sch} \ket{C} = \frac{1}{2^{|AB|/2}} \sum_{K \in \mathcal{S}_{AB}} K \ket{C_A} \ket{C_B} = \frac{1}{2^{|AB|/2}} \sum_{b_A,b_B} \ket{b_A} \ket{b_B}, \end{equation}

where $\ket{b_A}$ and $\ket{b_B}$ are basis vectors of $\mathcal{H}_A$ and $\mathcal{H}_B$, respectively. Their are constructed from the $K$ operators by separating them into a product of pauli matrices in $A$ and in $B$: $K = \sigma_A^{b_A} \sigma_B^{b_B}$. If $|A|<|B|$ and the rank of the schmidt decomposition is $|AB| = L$ where $L$ is the number of nodes in $A$ with links on $B$, namely the boundary $L = |\partial A|$ of $A$.

As an immediate consequence of $\eqref{e:sch}$ we obtain the reduced density matrix of $A$

$$\rho_A = \frac{1}{2^{L}} 1_L, \; |AB| = |\partial A| = L,$$

and thus, the entanglement entropy

$$S_A = L.$$

This is precisely what the entanglement area law states for the cluster ground state $\ket{C}$ of the graph hamiltonian system $H_C(G)$.

Problem

Demonstrate that the density matrix associated to the cluster state can be written as a superposition of the stabilizers $K = \sigma^b$ (in the notation we introduced above)

$$\rho = \ket{C}\bra{C} = \frac{1}{|\mathcal{S}|} \sum_{K \in \mathcal{S}} K, \quad |\mathcal{S}| = 2^{|V|}$$

Using this expression show that the reduced density matrix of the subgraph $A$ is

$$\rho_A = \frac{1}{2^{|A|}} \sum_{K \in \mathcal{S}_A} K, \quad \mathcal{S}_A = \{K \in \mathcal{S} \mid \mathrm{supp}(K) \subseteq A \}.$$

Explain why $2^{|A|} \ne |\mathcal{S}_A|$ in general, and compute the square of $\rho_A$:

$$\rho_A^2 = \frac{|\mathcal{S}_A|}{2^{|A|}} \rho_A.$$

Deduce from this result the entanglement entropy:

$$S_A = -\log\frac{|\mathcal{S}_A|}{2^{|A|}},$$

compare with the result in the main text.

Notes

The paper Entanglement in graph states and its applications by Hein et al. (2006) reviews the cluster states properties and may be useful for some of the exercices.
Raussendorf and Wei (2012) discuss the role of cluster states in the measurement based quantum computation, with some emphasis in entanglement as a resource.