Two-dimensional Affleck-Kennedy-Lieb-Tasaki state on the honeycomb lattice is a universal resource for quantum computation

Universal quantum computation can be achieved by simply performing single-qubit measurements on a highly entangled resource state. Resource states can arise from ground states of carefully designed two-body interacting Hamiltonians. This opens up an appealing possibility of creating them by cooling. The family of Affleck-Kennedy-Lieb-Tasaki (AKLT) states are the ground states of particularly simple Hamiltonians with high symmetry, and their potential use in quantum computation gives rise to a new research direction. Expanding on our prior work [T.-C. Wei, I. Affleck, and R. Raussendorf, Phys. Rev. Lett. 106, 070501 (2011)], we give a detailed analysis to explain why the spin-3/2 AKLT state on a two-dimensional honeycomb lattice is a universal resource for measurement-based quantum computation. Along the way, we also provide an alternative proof that the 1D spin-1 AKLT state can be used to simulate arbitrary one-qubit unitary gates. Moreover, we connect the quantum computational universality of 2D random graph states to their percolation property and show that these states whose graphs are in the supercritical (i.e., percolated) phase are also universal resources for measurement-based quantum computation.

Figure 1

The 1D AKLT state (a) and the 1D cluster state (b).

Figure 2

Illustration of (a) encoding and (b) and (c) stabilizer operator.

Figure 3

Illustrations of the AKLT state on the honeycomb lattice, a graph state, and the 2D cluster state on a square lattice. (a) AKLT state. Spin singlets of two virtual spins-1/2 are located on the edges of the honeycomb lattice. A projection $P_{S,v}$ at each lattice site $v$ onto the symmetric subspace of three virtual spins creates the AKLT state. (b) A graph state. One qubit (i.e., spin-1/2) resides at vertex of the graph. One stabilizer generator of the form $X_v{⨂}_{u\in \mathrm{nb}\left(v\right)}{Z}_u$ is shown. (c) 2D Cluster state is a special case of graph states, where the graph is a two-dimensional square lattice.

Figure 4

Graphical rules for transformation of the lattice $\mathcal{L}$ into the graph $G\left(\mathcal{A}\right)$, depending on the POVM outcomes $\mathcal{A}$. (a) Graph Rule 1: A single edge between neighboring sites with the same POVM outcome $i\in \{x,y,z\}$ is contracted. (b) Rule 2: Pairs of edges between the same vertices are deleted. (b) An example for the application of rules 1 and 2 to a small honeycomb lattice. The alphabets ($j\ne k$) inside the circle indicate the POVM outcomes. (c) An example to illustrate the applications of the graph rules.

Figure 5

Illustrations of the encoding and the cluster graph stabilizer. (a) If two neighboring sites $u$ and $v$ share the same POVM outcome, e.g., $a_u=a_v=z$, then collectively these two sites form a logical qubit. More generally, if a set of connected sites share the same POVM outcome, then these sites effective encode a logical qubit. (b) An example of four sites $u$, $v$, $w$, and $c$ with POVM outcomes $a_c=z$, and $a_u=a_v=a_w=x$ is used to illustrate the stabilizer generator $K_c=\pm {\overline{X}}_c{\overline{Z}}_u{\overline{Z}}_v{\overline{Z}}_w$.

Figure 6

(a) Constructing a rectangle with a traversing path of aspect ratio 1:5, from such rectangles with aspect ratio 1:2, 2:1. (b) Overlapping rectangles of size $L\times 5L$, $5L\times L$. The union of their traversing paths yields the net $\mathcal{P}$. (c) Pair of nonseparated junctions.

Figure 7

Transforming $\left|G\right(\mathcal{A})\rangle$ into a 2D cluster state. (a) Macroscopic view: Regions $\alpha$, $\beta$, $A$, etc., imposed on the graph $G\left(\mathcal{A}\right)$. (b) Graph with three-valent junctions. (c) Decorated 2D grid. (d) 2D grid for the cluster state.

Figure 8

Average vertex (or domain) number, average edge number, and average Betti number in the typical random graphs original lattice site vs. $L$. The total number of sites is $N=L^2$. This shows the number of domains, the number of interdomain Ising interaction, and the number of independent loops in the resultant graph all scale with the system size of the original honeycomb lattice.

Figure 9

Average domain size (i.e., number of original sites in a domain), average width of domain size distribution, and average degree of a vertex in the typical random graphs vs. $L$, where $L^2$ is the total number of sites in the honeycomb lattice. For better discernibility of the two lower sets of data, we suppress the error bars for one of them. This set of data was first shown in Ref. [34], and we have reproduced it here for the sake of completeness.

Figure 10

Percolation study of the graph formed by the domains: probability of a spanning cluster $p_{\mathrm{cluster}}$ vs. the probability to delete a vertex (a) or an edge (b) $p_{\mathrm{delete}}$. The threshold for destroying the spanning cluster is around $p_{\mathrm{delete}}\approx 0.33$ in deleting vertices and $p_{\mathrm{delete}}\approx 0.43$ in deleting edges. This shows that the graph without deleting any vertex or edge is deep in the percolated (i.e., connected) phase. We note that the result of site percolation is reproduced from Ref. [34], and the additional bond percolation result presented here is consistent with the picture that the typical random graphs lie somewhat between the honeycomb and the square lattice.

Figure 11

The largest domain size in the typical graphs vs. $L$, with $N=L^2$ being the total number of sites. The fitted curve to the largest domain size is $3.337\ln \left(N\right)-5.566$. The result is reproduced from Ref. [34].

Figure 12

Illustration of loops. (a) A domain consisting of eight vertices, eight edges, and one face. The numbers indicate one possible order in which the domain could be grown. When the first vertex is added, $V=1$, $E=F=0$. As vertices 2 to 7 are added both $V$ and $E$ increase by 1. When the eight vertex is added, $V$ and $F$ increase by 1 and $E$ increases by 2. (b) In this domain, which contains $F=3$ faces, two of them are selected, as indicated by shading. The corresponding set of loops is a single loop surrounding the two adjacent faces as indicated by heavy lines. This domain contains $V=16$ vertices and $E=18$ edges, obeying $F=E-V+1$. (c) This is the same domain as in the previous figure (b) but a different subset of faces is selected. Now the set of loops consists of two loops as indicated by heavy lines.

Figure 13

Illustration of loops in the case of the periodic boundary condition. A honeycomb lattice with periodic boundary conditions, drawn as a “brick wall” lattice for convenience. (a) A topological loop is shown. The arrows indicate an edge in the domain between vertices at the left- and right-hand sides of the lattice. (b) The set of loops (one loop in this case) is shown for a domain containing one topological loop and one face sharing on edge with the topological loop, corresponding to the case in which the face and the topological loop are chosen. (c) A domain containing two topological loops, with $W=2$. It can be seen that there are three possible loops, corresponding to four sets of loops, and zero faces.