- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Faculty Research and Publications /
- Measurement-based quantum computation
Open Collections
UBC Faculty Research and Publications
Measurement-based quantum computation Browne, Dan 2010
Page Metadata
Item Metadata
Title | Measurement-based quantum computation |
Creator |
Browne, Dan Raussendorf, Robert |
Date Created | 2010-12-01 |
Date Issued | 2010-07-29 |
Description | There are two fundamentally different ways of evolving a quantum state: unitary evolution and projective measurement. Unitary evolution is deterministic and reversible, whereas measurement is probabilistic and irreversible. Despite these differences, it turns out that universal quantum computation can be built on either. In this lecture we are concerned with quantum computation by measurement. We give an introduction to the subject, and discuss various aspects of this field, ranging from physical realization to fault-tolerance and foundations of quantum mechanics. |
Subject |
Quantum Computation Computational Models Measurement-based Quantum Computation |
Type |
Sound Moving Image |
Language | Eng |
Collection |
10th Canadian Summer School on Quantum Information |
Date Available | 2010-12-01 |
DOI | 10.14288/1.0040944 |
Affiliation |
Science, Faculty of Physics and Astronomy, Department of |
Peer Review Status | Unreviewed |
Scholarly Level | Faculty |
URI | http://hdl.handle.net/2429/30257 |
Digital Resource Original Record | https://open.library.ubc.ca/collections/29055/items/1.0040944/source |
Download
- Media
- MBQC Browne 1.mp4
- MBQC Browne 1.mp4 [ 198.31MB ]
- MBQC Browne 1.mp4
- MBQC Browne 2.mp4 [ 236.36MB ]
- MBQC Browne 3.mp4
- MBQC Browne 3.mp4 [ 226.03MB ]
- MBQC Raussendorf 4.mp4 [ 200.59MB ]
- MBQC Raussendorf 4.mp4
- MBQC Raussendorf 4.mp4
- MB_quantum_computation.pdf [ 1.01MB ]
- FTQC_QI10.pdf [ 2.63MB ]
- FTQC_QI10.pdf
- Metadata
- JSON: 1.0040944.json
- JSON-LD: 1.0040944+ld.json
- RDF/XML (Pretty): 1.0040944.xml
- RDF/JSON: 1.0040944+rdf.json
- Turtle: 1.0040944+rdf-turtle.txt
- N-Triples: 1.0040944+rdf-ntriples.txt
- Citation
- 1.0040944.ris
Full Text
Measurement-based quantum computation 10th Canadian Summer School on QI Dan Browne Dept. of Physics and Astronomy University College London Thursday, 29 July 2010 What is a quantum computer? Thursday, 29 July 2010 The one-way quantum computer A multi-qubit entangled “resource state” E.g. cluster state Single-qubit measurements Choice of bases specify computation Adaptive (some bases depend upon previous outcomes) + = A universal quantum computer Thursday, 29 July 2010 Overview of Lectures ★ 1. Cluster states and graph states I ★ What are they? Basic properties. ★ 2. The one-way quantum computer ★ What is the model? How does it work? ★ 3. Cluster states and graph states II ★ Stabilizer formalism and graphical representation ★ 4. Cluster states and graph states III ★ How do we build them? ★ 5. Beyond cluster states (If time permits) ★ (other models of MBQC) ★ 6. (Robert Raussendorf) Fault tolerant MBQC Thursday, 29 July 2010 Pauli group and Clifford Group • Pauli group: • Set of all n-fold tensor products of X, Y, Z and I, with pre-factors +1, -1. +i, -i for group closure. • Clifford group: • “Normalizer” of Set of unitaries C such that Equiv,: “Maps Pauli group onto Pauli group” n n CσkC † = σj∀σk ∈ n σj ∈ n Cσk = σjC = (CσkC†)C Thursday, 29 July 2010 2-qubit gates and universal q.c. J J J J J J J J J J J J J J J Thursday, 29 July 2010 2-qubit gates and universal q.c. J J J J J J J J J J J J J J J Thursday, 29 July 2010 2-qubit gates and universal q.c. J J J J J J J J J J J J J J J Thursday, 29 July 2010 Etching with z measurements VOLUME 86, NUMBER 22 P H Y S I C A L R E V I E W L E T T E R S 28 MAY 2001 A One-Way Quantum Computer Robert Raussendorf and Hans J. Briegel Theoretische Physik, Ludwig-Maximilians-Universität München, Germany (Received 25 October 2000) We present a scheme of quantum computation that consists entirely of one-qubit measurements on a particular class of entangled states, the cluster states. The measurements are used to imprint a quantum logic circuit on the state, thereby destroying its entanglement at the same time. Cluster states are thus one-way quantum computers and the measurements form the program. DOI: 10.1103/PhysRevLett.86.5188 PACS numbers: 03.67.Lx, 03.65.Ud A quantum computer promises efficient processing of certain computational tasks that are intractable with clas- sical computer technology [1]. While basic principles of a quantum computer have been demonstrated in the labora- tory [2], scalability of these systems to a large number of qubits [3], essential for practical applications such as the Shor algorithm, represents a formidable challenge. Most of the current experiments are designed to implement se- quences of highly controlled interactions between selected particles (qubits), thereby following models of a quan- tum computer as a (sequential) network of quantum logic gates [4,5]. Here we propose a different model of a scalable quan- tum computer. In our model, the entire resource for the quantum computation is provided initially in the form of a specific entangled state (a so-called cluster state [6]) of a large number of qubits. Information is then written onto the cluster, processed, and read out from the cluster by one-particle measurements only. The entangled state of the cluster thereby serves as a universal “substrate” for any quantum computation. Cluster states can be created effi- ciently in any system with a quantum Ising-type interaction (at very low temperatures) between two-state particles in a lattice configuration. We consider two- and three-dimensional arrays of qubits that interact via an Ising-type next-neighbor in- teraction [6] described by a Hamiltonian Hint ! g!t" 3P #a,a0$ 11s!a"z 2 12s!a 0" z 2 % 2 1 4g!t" P #a,a0$s !a" z s !a0" z [7] whose strength g!t" can be controlled externally. A possible realization of such a system is discussed below. A qubit at site a can be in two states j0$a & j0$z,a or j1$a & j1$z,a, the eigenstates of the Pauli phase flip operator s!a"z 's!a"z ji$a ! !21"iji$a(. These two states form the compu- tational basis. Each qubit can equally be in an arbitrary superposition state aj0$ 1 bj1$, jaj2 1 jbj2 ! 1. For our purpose, we initially prepare all qubits in the su- perposition j1$ ! !j0$ 1 j1$")p2, an eigenstate of the Pauli spin flip operator sx 'sxj6$ ! 6j6$(. Hint is then switched on for an appropriately chosen finite time interval T , where RT 0 dt g!t" ! p, by which a unitary transformation S is realized. Since Hint acts uniformly on the lattice, entire clusters of neighboring particles become entangled in one single step. The quantum state jF$C , the state of a cluster !C " of neighboring qubits, which is thereby created provides in advance all entanglement that is involved in the subsequent quantum computation. It has been shown [6] that the cluster state jF$C is characterized by a set of eigenvalue equations s!a"x O a0[ngbh!a" s!a 0" z jF$C ! 6jF$C , (1) where ngbh!a" specifies the sites of all qubits that inter- act with the qubit at site a [ C . The eigenvalues are de- termined by the distribution of the qubits on the lattice. The equations (1) are central for the proposed computation scheme. As an example, a measurement on an individual qubit of a cluster has a random outcome. On the other hand, Eqs. (1) imply that any two qubits at sites a, a0 [ C can be projected into a Bell state by measuring a subset of the other qubits in the cluster. This property will be used to define quantum channels that allow us to propagate quan- tum information through a cluster. We show that a cluster state jF$C can be used as a sub- strate on which any quantum circuit can be imprinted by one-qubit measurements. In Fig. 1 this scheme is illus- trated. For simplicity, we assume that in a certain region of the lattice each site is occupied by a qubit. This re- quirement is not essential as will be explained below [see (d)]. In the first step of the computation, a subset of qubits is measured in the basis of sz which effectively removes them. In Fig. 1 these qubits are denoted by “ Ø.” quantum gate information flow FIG. 1. Quantum computation by measuring two-state parti- cles on a lattice. Before the measurements the qubits are in the cluster state jF$C of (1). Circles Ø symbolize measurements of sz , vertical arrows are measurements of sx , while tilted arrows refer to measurements in the x-y plane. 5188 0031-9007)01)86(22))5188(4)$15.00 © 2001 The American Physical Society• Figure 1in H. J. Briegel and R. Raussendorf, Phys. Rev. Lett. 86, 5188 (2001) z-measurements “quantum wire” for logical single qubi Thursday, 29 July 2010 Measurement-patterns for gates in the one-way model 5 B. A universal set of quantum gates To provide something definite to discuss right from the beginning, we now give the procedures of how to realize a CNOT-gate and a general one-qubit rotation via one- qubit measurements on a cluster state. The explanation of why and how these gates work will be given in Sec- tion IIG. (a) 1 2 3 4 5 6 7 9 10 11 12 13 14 15 8 control target Y Y Y Y Y Y Y XXX X X X CNOT-gate (b) 1 2 3 4 5 _X !_+ "+#+_ (c) 1 2 3 4 5 X X X+#_ general rotation z-rotation (d) 1 2 3 4 5 X YY Y (e) 1 2 3 4 5 X X XY Hadamard-gate pi/2-phase gate FIG. 2: Realization of elementary quantum gates on the QCC. Each square represents a lattice qubit. The squares in the extreme left column marked with white circles denote the in- put qubits, those in the right-most column denote the output qubits. A CNOT-gate can be realized on a cluster state of 15 qubits, as shown in Fig. 2. All measurements can be performed simultaneously. The procedure to realize a CNOT-gate on a cluster with 15 qubits as displayed in Fig. 2 is Procedure 1 Realization of a CNOT-gate acting on a two-qubit state |ψin〉. 1. Prepare the state |Ψin〉C15 = |ψin〉1,9 ⊗ (⊗ i∈C15\{1,9} |+〉i ) . 2. Entangle the 15 qubits of the cluster C15 via the unitary operation S(C15). 3. Measure all qubits of C15 except for the output qubits 7, 15 (following the labeling in Fig. 2). The measurements can be performed simultaneously. Qubits 1, 9, 10, 11, 13, 14 are measured in the σx- eigenbasis and qubits 2-6, 8, 12 in the σy-eigenbasis. Dependent on the measurement results, the following gate is thereby realized: U ′CNOT = UΣ,CNOT CNOT (c, t). (23) Therein the byproduct operator UΣ,CNOT has the form UΣ,CNOT = σ (c) x γ(c)x σ(t)x γ(t)x σ(c)z γ(c)z σ(t)z γ(t)z , with γ(c)x = s2 + s3 + s5 + s6 γ(t)x = s2 + s3 + s8 + s10 + s12 + s14 γ(c)z = s1 + s3 + s4 + s5 + s8 + s9 + s11 + 1 γ(t)z = s9 + s11 + s13. (24) Therein, the si represent the measurement outcomes si on the qubits i. The expression (24) is modified if re- dundant cluster qubits are present and/or if the cluster state on which the CNOT gate is realized is specified by a set {κa} different from (12), see Section II C. This con- cludes the presentation of the CNOT gate, the proof of its functioning is given in Section IIG. An arbitrary rotation URot ∈ SU(2) can be realized on a chain of 5 qubits. Consider a rotation in its Euler representation URot[ξ, η, ζ] = Ux[ζ]Uz[η]Ux[ξ], (25) where the rotations about the x- and z-axis are Ux[α] = exp ( −iασx 2 ) Uz[α] = exp ( −iασz 2 ) . (26) Initially, the first qubit is prepared in some state |ψin〉, which is to be rotated, and the other qubits are prepared in |+〉. After the 5 qubits are entangled by the unitary transformation S, the state |ψin〉 can be rotated by mea- suring qubits 1 to 4. At the same time, the state is also swapped to site 5. The qubits 1 .. 4 are measured in ap- propriately chosen bases Bj(ϕj) = { |0〉j + eiϕj |1〉j√ 2 , |0〉j − eiϕj |1〉j√ 2 } , (27) whereby the measurement outcomes sj ∈ {0, 1} for j = 1 .. 4 are obtained. Here, sj = 0 means that qubit j is projected into the first state of Bj(ϕj). In (27) the ba- sis states of all possible measurement bases lie on the equator of the Bloch sphere, i.e. on the intersection of the Bloch sphere with the x-y-plane. Therefore, the mea- surement basis for qubit j can be specified by a single pa- rameter, the measurement angle ϕj . The measurement direction of qubit j is the vector on the Bloch sphere which corresponds to the first state in the measurement basis Bj(ϕj). Thus, the measurement angle ϕj is the an- gle between the measurement direction at qubit j and the positive x-axis. In summary, the procedure to realize an arbitrary rotation URot[ξ, η, ζ], specified by its Euler angles ξ, η, ζ, is this: R. Raussendorf, D. E. Browne and H.J. Briegel, Phys. Rev. A 68: 022312 (2003) Thursday, 29 July 2010 LC-orbit of local Clifford equivalent states ENTANGLEMENT IN GRAPH STATES AND ITS APPLICATIONS 21 the graph unchanged: (41) τa : G !→ τa(G) := G+Na . With this notation the following result can be stated [39, 60]: Proposition 5 (LC-rule). By local complementation of a graph G at some vertex a ∈ V one obtains an LC-equivalent graph state |τa(G)〉: (42) |τa(G)〉 = U τa (G) |G〉 , where (43) U τa (G) = e−i pi 4 σ a xei pi 4 σ Na z ∝ √ Ka is a local Clifford unitary. Furthermore, two graph states |G〉 and |G′〉 are LC-equivalent iff the corresponding graphs are related by a sequence of local complementations, i.e. G′ = τa1 ◦ . . . ◦ τan(G) for some a1, . . . , an ∈ V . 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 No. 1 No. 2 No. 3 No. 4 No. 5 No. 6 No. 7 No. 8 No. 9 No. 10 No. 11 Apply LC!Rule Fig. 4. – An example for a successive applica- tion of the LC-rule, which exhibits the whole equivalence class associated with graph No. 1. The rule is successively applied to the vertex, which is colored red in the figure. Fig. 4 depicts an example for such a successive application of the LC-rule. Starting with the first graph the complete orbit can be obtained by ap- plying the LC-rule to the vertices in the preceding graph that appear above the arrow of the following diagram: No. 1 3−−−−→ No. 2 2−−−−→ No. 3 3−−−−→ No. 4 1−−−−→ No. 5 3−−−−→ No. 6 1−−−−→ No. 7 3−−−−→ No. 8 4−−−−→ No. 9 1−−−−→ No. 10 2−−−−→ No. 11 Proof of Proposition 5: Let G be a graph with correlation operators Kb and G′ = τa(G) the corresponding graph under local complementation at vertex a with correlation operators K ′b. For c ∈ V \ Na we find (44) U τaKc(U τa )† = Kc = K ′c . For b ∈ Na, we compute U τa Kb (U τ a ) † = (−iσax) ( iσbz ) σbx σ a zσ Nb\a z = σax σ Na z · σbx σNb+Naz = K ′a · K ′b . ENTANGLEMENT IN GRAPH STATES AND ITS APPLICATIONS 21 the graph unchanged: (41) τa : G !→ τa(G) := G+Na . With this notation the following result can be stated [39, 60]: Proposition 5 (LC-rule). By local complementation of a graph G at some vertex a ∈ V one obtains an LC-equivalent graph state |τa(G)〉: (42) |τa(G)〉 = U τa (G) |G〉 , where (43) U τa (G) = e−i pi 4 σ a xei pi 4 σ Na z ∝ √ Ka is a local Clifford unitary. Furthermore, two graph states |G〉 and |G′〉 are LC-equivalent iff the corresponding graphs are related by a sequence of local complementations, i.e. G′ = τa1 ◦ . . . ◦ τan(G) for some a1, . . . , an ∈ V . 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 No. 1 No. 2 No. 3 No. 4 No. 5 No. 6 No. 7 No. 8 No. 9 No. 10 No. 11 Apply LC!Rule Fig. 4. – An example for a successive applica- tion of the LC-rule, which exhibits the whole equivalence class associated with graph No. 1. The rule is successively applied to the vertex, which is colored red in the figure. Fig. 4 depicts an example for such a successive application of the LC-rule. Starting with the first graph the complete orbit can be obtained by ap- plying the LC-rule to the vertices in the preceding graph that appear above the arrow of the following diagram: No. 1 3−−−−→ No. 2 2−−−−→ No. 3 3−−−−→ No. 4 1−−−−→ No. 5 3−−−−→ No. 6 1−−−−→ No. 7 3−−−−→ No. 8 4−−−−→ No. 9 1−−−−→ No. 10 2−−−−→ No. 11 Proof of Proposition 5: Let G be a graph with correlation operators Kb and G′ = τa(G) the corresponding graph under local complementation at vertex a with correlation operators K ′b. For c ∈ V \ Na we find (44) U τaKc(U τa )† = Kc = K ′c . For b ∈ Na, we compute U τa Kb (U τ a ) † = (−iσax) ( iσbz ) σbx σ a zσ Nb\a z = σax σ Na z · σbx σNb+Naz = K ′a · K ′b . • Figure 4 in M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, H.-J. Briegel, quant-ph/0602096 (Varena lectures) Thursday, 29 July 2010 Counter-example to LU-LC conjecture 11 equivalent but not LC equivalent graph states can differ only in on edge. Note that the simplifi- cation of Q(x) discussed above does not simplify or change the form of the four stabilizer states in Fig. 2. FIG. 3: Corresponding Graph States V. CONCLUSION In summary, we have shown that the LU-LC conjecture is false by giving explicit counterex- amples of it. It is also clear that in order to disprove the conjecture, we have to consider stabilizer states with the rank of the support no less than 6. This result leads us to rethink about the local equivalence problem of stabilizers as most of the previous work focus on proving the conjecture to be true. The random procedure generates counterexamples of size 27 and 35. Though not proved, we believe that 27 is the smallest possible size of counterexamples of LU-LC. Although the LU-LC conjecture is now disproved, we still know little about the relation of LU and LC equivalence and do not have an explicit understanding of why or when LU equivalence differs from LC equiva- lence. When d = 6, the random generation procedure can find a counterexample in seconds, but it is in fact not an efficient algorithm when d is large or even when d = 7. That fact is we have never obtained a valid counterexample of d = 7 using the random procedure. Fortunately, larger scale counterexamples, including those of d = 7, have been found [7] motivated by the randomly generated counterexamples. As LU and LC equivalences are nowknown to be different. It is also challenging to askwhether there is an efficient algorithm deciding LU equivalence for stabilizers or whether there is a graph theoretical interpretation of LU equivalent graph states. This seems to be difficult as local unitary operations are much less linked up with the stabilizer formalism. The two graphs (with / without the red edge) represent locally equivalent states, but are not related by the LC rule. Zhengfeng Ji et al, Quantum Inf. Comput., Vol. 10, No. 1&2, 97-108, 2010 Thursday, 29 July 2010 Universal resources derived via graphical rules These regular graphs can all be mapped into square lattices via Pauli measurements - using the graphical rules. Hence all are resources for universal MBQC. M. Van den Nest, et al, New J. Phys. 9 204 (2007). CONTENTS 32 Fig. 2. Accordingly, we finally obtain a square lattice, i.e., a 2D cluster state. The total spatial overhead is eight in that a unit square on (d) is obtained from eight hexagons in (a). Since the overhead is constant, all resource states are efficient universal. ! Note that, since these other resource states can be transformed into the 2D cluster state always by adaptive local projective measurements assisted with classical communication, and local (Clifford) operations, they are also universal in the sense of a conventional one-way quantum computation. It is interesting to observe that the square lattice, together with the hexagonal and triangular lattices are the only possibilities to obtain a regular tiling of the 2D plane. Furthermore, the Kagome lattice is an example of a uniform semiregular 2D tiling with 2 basic tiles (the triangle and the hexagon). The hexagonal lattice has vertex degree 3, which leads to an increased robustness against local noise as compared to the 2D cluster state [53]. Since the 1D cluster state (with uniform vertex degree 2) has been proved not to be universal [27], the vertex degree 3 is minimal for universal resource on uniform lattice structures. We remark that other universal resource states have been presented [54] based on non-uniform lattice structures (see also [55]), where each gate in a universal set of unitary gates can be implemented by local measurements on an elementary unit and these units are combined (bottom-up approach). Here we took, in contrast, a (a) (b) (c) 3 21 (d) Figure 2. Examples of efficient universal resource for MQC. These are graph states corresponding to (a) hexagonal, (b) triangular and (c) Kagome lattices. Deterministic LOCC transformation from (a) to (d) (2D cluster state) via (b) and (c) is indicated, where simple graph rules can be used sequentially (σy and σz measurements are displayed by ! and ♦, respectively). The spatial overhead for the transformation is constant. Hexagonal Triangular Kagome Square Thursday, 29 July 2010 Universal resources derived via graphical rules These regular graphs can all be mapped into square lattices via Pauli measurements - using the graphical rules. Hence all are resources for universal MBQC. M. Van den Nest, et al, New J. Phys. 9 204 (2007). CONTENTS 32 Fig. 2. Accordingly, we finally obtain a square lattice, i.e., a 2D cluster state. The total spatial overhead is eight in that a unit square on (d) is obtained from eight hexagons in (a). Since the overhead is constant, all resource states are efficient universal. ! Note that, since these other resource states can be transformed into the 2D cluster state always by adaptive local projective measurements assisted with classical communication, and local (Clifford) operations, they are also universal in the sense of a conventional one-way quantum computation. It is interesting to observe that the square lattice, together with the hexagonal and triangular lattices are the only possibilities to obtain a regular tiling of the 2D plane. Furthermore, the Kagome lattice is an example of a uniform semiregular 2D tiling with 2 basic tiles (the triangle and the hexagon). The hexagonal lattice has vertex degree 3, which leads to an increased robustness against local noise as compared to the 2D cluster state [53]. Since the 1D cluster state (with uniform vertex degree 2) has been proved not to be universal [27], the vertex degree 3 is minimal for universal resource on uniform lattice structures. We remark that other universal resource states have been presented [54] based on non-uniform lattice structures (see also [55]), where each gate in a universal set of unitary gates can be implemented by local measurements on an elementary unit and these units are combined (bottom-up approach). Here we took, in contrast, a (a) (b) (c) 3 21 (d) Figure 2. Examples of efficient universal resource for MQC. These are graph states corresponding to (a) hexagonal, (b) triangular and (c) Kagome lattices. Deterministic LOCC transformation from (a) to (d) (2D cluster state) via (b) and (c) is indicated, where simple graph rules can be used sequentially (σy and σz measurements are displayed by ! and ♦, respectively). The spatial overhead for the transformation is constant. Hexagonal Triangular Kagome Square Thursday, 29 July 2010 Measurement-patterns for gates in the one-way model 5 B. A universal set of quantum gates To provide something definite to discuss right from the beginning, we now give the procedures of how to realize a CNOT-gate and a general one-qubit rotation via one- qubit measurements on a cluster state. The explanation of why and how these gates work will be given in Sec- tion IIG. (a) 1 2 3 4 5 6 7 9 10 11 12 13 14 15 8 control target Y Y Y Y Y Y Y XXX X X X CNOT-gate (b) 1 2 3 4 5 _X !_+ "+#+_ (c) 1 2 3 4 5 X X X+#_ general rotation z-rotation (d) 1 2 3 4 5 X YY Y (e) 1 2 3 4 5 X X XY Hadamard-gate pi/2-phase gate FIG. 2: Realization of elementary quantum gates on the QCC. Each square represents a lattice qubit. The squares in the extreme left column marked with white circles denote the in- put qubits, those in the right-most column denote the output qubits. A CNOT-gate can be realized on a cluster state of 15 qubits, as shown in Fig. 2. All measurements can be performed simultaneously. The procedure to realize a CNOT-gate on a cluster with 15 qubits as displayed in Fig. 2 is Procedure 1 Realization of a CNOT-gate acting on a two-qubit state |ψin〉. 1. Prepare the state |Ψin〉C15 = |ψin〉1,9 ⊗ (⊗ i∈C15\{1,9} |+〉i ) . 2. Entangle the 15 qubits of the cluster C15 via the unitary operation S(C15). 3. Measure all qubits of C15 except for the output qubits 7, 15 (following the labeling in Fig. 2). The measurements can be performed simultaneously. Qubits 1, 9, 10, 11, 13, 14 are measured in the σx- eigenbasis and qubits 2-6, 8, 12 in the σy-eigenbasis. Dependent on the measurement results, the following gate is thereby realized: U ′CNOT = UΣ,CNOT CNOT (c, t). (23) Therein the byproduct operator UΣ,CNOT has the form UΣ,CNOT = σ (c) x γ(c)x σ(t)x γ(t)x σ(c)z γ(c)z σ(t)z γ(t)z , with γ(c)x = s2 + s3 + s5 + s6 γ(t)x = s2 + s3 + s8 + s10 + s12 + s14 γ(c)z = s1 + s3 + s4 + s5 + s8 + s9 + s11 + 1 γ(t)z = s9 + s11 + s13. (24) Therein, the si represent the measurement outcomes si on the qubits i. The expression (24) is modified if re- dundant cluster qubits are present and/or if the cluster state on which the CNOT gate is realized is specified by a set {κa} different from (12), see Section II C. This con- cludes the presentation of the CNOT gate, the proof of its functioning is given in Section IIG. An arbitrary rotation URot ∈ SU(2) can be realized on a chain of 5 qubits. Consider a rotation in its Euler representation URot[ξ, η, ζ] = Ux[ζ]Uz[η]Ux[ξ], (25) where the rotations about the x- and z-axis are Ux[α] = exp ( −iασx 2 ) Uz[α] = exp ( −iασz 2 ) . (26) Initially, the first qubit is prepared in some state |ψin〉, which is to be rotated, and the other qubits are prepared in |+〉. After the 5 qubits are entangled by the unitary transformation S, the state |ψin〉 can be rotated by mea- suring qubits 1 to 4. At the same time, the state is also swapped to site 5. The qubits 1 .. 4 are measured in ap- propriately chosen bases Bj(ϕj) = { |0〉j + eiϕj |1〉j√ 2 , |0〉j − eiϕj |1〉j√ 2 } , (27) whereby the measurement outcomes sj ∈ {0, 1} for j = 1 .. 4 are obtained. Here, sj = 0 means that qubit j is projected into the first state of Bj(ϕj). In (27) the ba- sis states of all possible measurement bases lie on the equator of the Bloch sphere, i.e. on the intersection of the Bloch sphere with the x-y-plane. Therefore, the mea- surement basis for qubit j can be specified by a single pa- rameter, the measurement angle ϕj . The measurement direction of qubit j is the vector on the Bloch sphere which corresponds to the first state in the measurement basis Bj(ϕj). Thus, the measurement angle ϕj is the an- gle between the measurement direction at qubit j and the positive x-axis. In summary, the procedure to realize an arbitrary rotation URot[ξ, η, ζ], specified by its Euler angles ξ, η, ζ, is this: R. Raussendorf, D. E. Browne and H.J. Briegel, Phys. Rev. A 68: 022312 (2003) Generate the full Clifford group Thursday, 29 July 2010 Graphical “Gottesman-Knill Theorem” 20 21 22 23 24 25 26 27 28 29 30 31 32 33 17 18 19 20 10 11 12 13 14 15 6 7 54321 No. 1 8 9 21 25 33 17 19 12 14 6 531 8 16 16 10 29 No. 2 FIG. 16: The graph associated with the QFT on 3 qubits in the one-way quantum computer is represented in graph No. 1, where the boxes denote the input (left) and output (right) vertices. Graph No. 2 is obtained from the first after performing all Pauli measurements according to the protocol in Ref. [3], except from the σx-measurements at the input vertices. More precisely, it is obtained from graph No. 1 after σy-measurements on the vertices 22, 23, 24, 26, 27, 28, 30, 31, 32 and σx-measurements on the vertices 2, 4, 7, 9, 11, 13, 15, 18, 20 have been performed. ror correction, quantum communication, and quantum com- putation in the context of the one-way quantum computer. The Schmidt measure is tailored for a comparably detailed account on the quantum correlations grasping genuine multi-particle entanglement, yet it turns out to be computable for many graph states. We have presented a number of general rules that can be applied when approaching the problem of evalu- ating the Schmidt measure for general graph states, which are stated mostly in graph theoretical terms. These rules have then been applied to a number of graph states that appear in quan- tum computation and error correction. Also, all connected graphs with up to seven vertices have been discussed in detail. The formalism that we present here abstracts from the actual physical realisation, but as has been pointed out in several in- stances, a number of well-controllable physical systems such as neutral atoms in optical lattices serve as potential candi- dates to realize such graph states [45, 46]. In this paper, the Schmidt measure has been employed to quantify the degree of entanglement, as a generalization of the Schmidt rank in the bipartite setting. This measure is sufficiently coarse to be accessible for systems consisting of many constituents and to allow for an appropriate discussion of multi-particle entanglement in graph states. The approach of quantifying entanglement in terms of rates of asymptotic reversible state transformations, as an alternative, appears un- feasible in the many-partite setting. The question of the min- imal reversible entangling generating set (MREGS) in multi- partite systems remains unresolved to date, even for quantum systems consisting of three qubits, and despite considerable research effort [47, 48]. These MREGS are the (not necessar- Standard-form measurement pattern Quantum Fourier Transform Graph state after all Pauli measurements performed 20 21 22 23 24 25 26 27 28 29 30 31 32 33 17 18 19 20 10 11 12 13 14 15 6 7 54321 No. 1 8 9 21 25 33 17 19 12 14 6 531 8 16 16 10 29 No. 2 FIG. 16: The graph associated with the QFT on 3 qubits in the one-way quantum computer is represented in graph No. 1, where the boxes denote the input (left) and output (right) vertices. Graph No. 2 is obtained from the first after performing all Pauli measurements according to the protocol in Ref. [3], except from the σx-measurements at the input vertices. More precisely, it is obtained from graph No. 1 after σy-measurements on the vertices 22, 23, 24, 26, 27, 28, 30, 31, 32 and σx-measurements on the vertices 2, 4, 7, 9, 11, 13, 15, 18, 20 have been performed. ror correction, quantum communication, and quantum com- putation in the context of the one-way quantum computer. The Schmidt measure is tailored for a comparably detailed account on the quantum correlations grasping genuine multi-particle entanglement, yet it turns out to be computable for many graph states. We have presented a number of general rules that can be applied when approaching the problem of evalu- ating the Schmidt measure for general graph states, which are stated mostly in graph theoretical terms. These rules have then been applied to a number of graph states that appear in quan- tum computation and error correction. Also, all connected graphs with up to seven vertices have been discussed in detail. The formalism that we present here abstracts from the actual physic l realisation, but as has b en pointed out in several in- stances, a number of well-controllable p ysical systems such as neutral atoms in optical lattices serve as potential candi- dates to realize such graph states [45, 46]. In this paper, the Schmidt measure has been employed to quantify the degree of entanglement, as a generalization of the Schmidt rank in the bipartite setting. This measure is sufficiently coarse to be accessible for systems consisting of many constituents and to allow for an appropriate discussion of multi-particle entanglement in graph states. The approach of quantifying entanglement in terms of rates of asymptotic reversible state transformations, as an alternative, appears un- feasible in the many-partite setting. The question of the min- imal reversible entangling generating set (MREGS) in multi- partite systems remains unresolved to date, even for quantum systems consisting of three qubits, and despite considerable research effort [47, 48]. These MREGS are the (not necessar- M. Hein, J. Eisert and H.J. Bri gel, Phys. Rev. A 69, 062311 (2004) Thursday, 29 July 2010 Valence bond PEPS to MPS “Virtual Qudit pairs” d n=1 |n|n PEPS “projector” Constructs a Matrix Product State MPS M(j)m,n = Ajp,q |ψ = s1,...sn Tr[M(s1)M(s2) . . .M(sn)] |s1|s2 · · · |sn D j=1 d p,q=1 Ajp,q|jp|q| Thursday, 29 July 2010 References • Progress Review • H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, M. Van den Nest, Nature Physics 5 1, 19-26 (2009) • Tutorials • M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, H.-J. Briegel, quant-ph/0602096 (Varena lectures on graph states) • D. E. Browne and H. J. Briegel, quant-ph/0603226 • M.A. Nielsen, quant-ph/0504097 • And many more... • Search arxiv for One-way, MBQC, Cluster States, Graph States, .... Thursday, 29 July 2010 Fault-tolerant quantum computation with cluster states Robert Raussendorf, UBC QI10 @ UBC, July 29, 2010 Our setting qubit elementary cell • 2D/3D: Nearest-neighbor translation-invariant interaction. • High fault-tolerance threshold Our setting Fault-tolerant quantum computation Task: • Maintain the quantum speedup in the presence of deco- herence. Solution: Fault-tolerance theorem∗: If for a universal quantum computer the noise per elementary operation is below a constant non- zero error threshold then arbitrarily long quantum computa- tions can be performed efficiently with arbitrary accuracy. *: Aharonov & Ben-Or (1996), Kitaev (1997), Knill & Laflamme & Zurek (1998), Aliferis & Gottesman & Preskill (2005) Talk outline 1. Universal cluster state computation. • The scheme: computation by local measurements • Cluster states: creation, definition, experiment 2. General introduction to quantum error-correction 3. Making cluster state computation fault-tolerant Part I: Cluster state quantum computation 1.1 Cluster state quantum computation measurement of Z (), X (↑), cosαX + sinαY (↗) • Universal computational resource: cluster state. • Information written onto the cluster, processed and read out by one-qubit measurements only. R. Raussendorf and H.J Briegel, PRL 86, 5188 (2001). 1.2 Cluster states - creation 1. Prepare product state ⊗ a∈C |0〉a + |1〉a√ 2 on d-dimensional qubit lattice C. 2. Apply the Ising interaction for a fixed time T : UIsing = e −igTh̄ ∑ 〈i,j〉 σ (i) z σ (j) z , with gT h̄ = pi 4 . • Interaction time T independent of cluster size. 1.2 Cluster states - simple examples |ψ〉2 = |0〉1|+〉2 + |1〉1|−〉2 Bell state |ψ〉3 = |+〉1|0〉2|+〉3 + |−〉1|1〉2|−〉3 GHZ-state |ψ〉4 = |0〉1|+〉2|0〉3|+〉4 + |0〉1|−〉2|1〉3|−〉4 + + |1〉1|−〉2|0〉3|+〉4 + |1〉1|+〉2|1〉3|−〉4 Number of terms exponential in number of qubits! 1.2 Cluster states - definition Z Z ZZ X A cluster state |φ〉C on a cluster C is the single common eigenstate of the stabilizer operators {Ka}, Ka|φ〉C = |φ〉C, ∀a ∈ C, with Ka = Xa ⊗ b∈N(a) Zb, ∀a ∈ C. (1) Therein, b ∈ N(a) if a,b are spatial next neighbors in C. 1.2 Cluster states - experiment Cold atoms in optical lattices [1,2] The QCC with photons [3]. 1: Greiner, Mandel, Esslinger, Hänsch, and Bloch, Nature 415, 39-44 (2002), 2: Greiner, Mandel, Hänsch and Bloch, Nature, 419, 51-54 (2002). 3: P. Walther et al., Nature 434, 169 (2005). Part II: Introduction to quantum error correction ... take a break from cluster states 2.1 Quantum vs. classical bits z x y Ψ Ψ = α +β0 1 E 0 1 s = 1,0 V 0 1 quantum bit classical bit −Measurement affects state −Mmnt does not affect state − Set of states continuous − Set of states discrete Despite the differences: • Quantum error-correction (QEC) is possible. • QEC is based on classical error correction. 2.2 Starting point: Classical EC An example: the repitition code. encoded state 0 erroneous states encoded state 1 0 0 0 0 1 0 0 1 1 1 1 1 bit 1 2 3 Individually read out all bits Perform majority vote & • Procedure on n-bit code corrects bn−12 c errors. • Error-correction procedure learns encoded state. If state measurement does not help in classical EC why bother that it can’t be done in QEC? 2.2 Starting point: Classical EC Same effect without state measurement: Read out parities only. encoded state 0 erroneous states encoded state 1 0 0 0 0 1 0 0 1 1 1 1 1 bit 1 2 3 0 1( )11( ) 1 1 00 1 1( )= 0 Syndrome Parity check matrix code word w. errors • Syndrome only reveals error, not encoded state: Sy(c) = 0, ∀ codewords c. Sy(E ⊕ c) ≡ Sy(E). (2) Learning the state is not crucial for classical error-correction. 2.3 How Quantum Error Correction works Classical-to-quantum dictionary: c ∈ {000,111} −→ |Ψ〉 = α|000〉+ β|111〉 Errors: bit flip −→ spin & phase flips σx, σy, σz Parity check matrix︷ ︸︸ ︷( 1 1 0 0 1 1 ) −→ stabilizer operators Z1 ⊗ Z2, Z2 ⊗ Z3 Syndrome −→ Measured eigenvalues of stabilizer operators. 2.3 How Quantum Error Correction works • Repeated measurement of the stabilizer operators, and con- ditional correction. • Correctable errors anti-commute with at least one stabilizer operator → error-syndrome. • Syndrome informs about an error, not the encoded state. Emergence of the error threshold R es id u al e rr o r a ft er c o rr ec ti o n error probability p small code large codeinfinite-size code error threshold Fault-tolerance theorem: For a universal quantum computer, an error per gate < is effectively as good as zero error. So far... • Have explained the basics of quantum error-correction. • Have ignored: – Errors introduced by error-correction itself. – Computation. ... but that can be fixed Part III: Fault-tolerant quantum computation with 3D cluster states Part III outline 3.1 Topological quantum error-correction with 3D cluster states 3.2 Topologocal quantum gates 3.3 Fault-tolerance threshold, overhead scaling, mapping to 2D Known threshold values geometric constraintno constraint [1] [2] [3] [4] 0.03, est. 10 10 10 -3 -4 -5 , est. , bd. , est. 1D2D [7] 10 -8 , bd. [6] 2 10 -5 , bd.. [5] 7 10 -3, est.. • Error sources: |+〉-Preparation, Λ(Z)-gates, Hadamard gates, measurement. [1] Knill, (2005); [2] Zalka (1999); [3] Dawson & Nielsen (2005); [4] Aliferis & Gottesman & Preskill (2005), [5] Raussendorf & Harrington, quant-ph/0610062; [6] Svore & DiVincenzo & Terhal, quant-ph/0604090, [7] Aharonov & Ben-Or (1999) Main idea 3D cluster state = fault- tolerant substrate Gates from non-trivial cluster topology Macroscopic view Three cluster regions: V (Vacuum), D (Defect) and S (Singular qubits). Qubits q ∈ V : local X-measurements, Qubits q ∈ D: local Z-measurements, Qubits q ∈ S: local measurements of X ± Y . R. Raussendorf, J. Harrington and K. Goyal, Ann. Phys. 321, 2242 (2006). Microscopic view 0 1 2 0 1 2 z x cluster edges elementary cell of L qubit location: (even, odd, odd) - face of L, qubit location: (odd, odd, even) - edge of L, syndrome location: (odd, odd, odd) - cube of L, syndrome location: (even, even, even) - site of L. Lattice duality L ←→ L Translation by vector (1,1,1)T : • Cluster C invariant, • L (primal) −→ L (dual). face of L − edge of L, edge of L − face of L, site of L − cube of L, cube of L − site of L, (3) • Many objects in this scheme exist as ‘primal’ and ‘dual’. Part III.1: Quantum Error-correction in 3D cluster states 3.1 Measuring the cluster state stabilizer X Z Z Z Z X-measurement Z-measurement 1 2 3 4 5 K1 = X1Z2Z3Z4Z5 But ... 3.1 Measuring the cluster state stabilizer X Z Z Z Z X-measurement Z-measurement 1 2 3 4 5 K1 = X1Z2Z3Z4Z5 λX,1 λZ,2 λZ,3 λZ,4 λZ,5 = +1. ±1 ±1 ±1 ±1 ±1 Measure eigenvalue of K1 by local measurements on qubits 1 - 5. But ... 3.1 Measuring the cluster state stabilizer X Z Z Z Z X-measurement Z-measurement 1 2 3 4 5 But ... all measurements in cluster region V are in the X-basis. Are there stabilizer elements that we can measure by local X- measurements only? Criterion: KJ = ⊗ a∈J Xa. 3.1 Measuring the cluster state stabilizer Criterion: KJ = ⊗ a∈J Xa. Such stabilizer elements exist! Example: X X X-measurement X X X X 1 2 3 4 5 6 X1X2X3X4X5X6 = K1K2K3K4K5K6 Correlation of measured eigenvalues: λX,1 λX,2 λX,3 λX,4 λX,5 λX,6 = +1, if no error. ±1 ±1 ±1 ±1 ±1 ±1 3.1 Measuring the cluster state stabilizer X X X-measurement X X X X 1 2 3 4 5 6 λX,1λX,2λX,3λX,4λX,5λX,6︸ ︷︷ ︸ Error syndrome = -1 indicates an error. • One bit of error syndrome per lattice cell. 3.1 Measuring the cluster state stabilizer Error non-trivial error syndrome -1 non-trivial error syndrome -1 Z-error on face qubit yields non-trivial syndrome on ad- jacent cells. • Each error leaves characteristic signature in the syndrome. • Identify error by that syndrome. 3.1 Geometry and topology Error Error syndrome supported on closed surface located on dual edge multiple edges = chain 3.1 Geometry and topology f f 2 e 1 error chain Error syndrome 1 Error syndrome 2 1 • An error chain Z(e) is detected by a syndrome Sy(f) if e and f interesect an even number of times. • Intersection number is a topological invariant. 3.1 Geometry and topology f f 2 e 1 e 2 f error chain equivalent error chain Error syndrome 1 Error syndrome 2 1 • Homologically equivalent error chains have same effect on the computation: e2 = e1 + ∂f −→ Z(e2) ≡ Z(e1). • Only need to identify the homology class of the error. 3.1 Topological error-correction • Topological error-correction in 3D cluster states described by Random plaquette Z2-gauge model (RPGM) [1]. • FT quantum memory with toric code described by RPGM as well [1]. [1] Dennis et al., quant-ph/0110143 (2001). 3.1 Phase diagram of the RPGM Map error correction to statistical mechanics: EC no EC Nishimori line p T optimal Error correction [1] Minimum weight chain matching [2] 3% • Have an error budget of 3%. [1] T. Ohno et al., quant-ph/0401101 (2004). [2] E. Dennis et al., quant-ph/0110143 (2001); J. Edmonds, Canadian J. Math. 17, 449 (1965). Part III.2: Topological quantum gates 3.2 Encoded quantum gates Z-measurement removes qubit from the cluster • Local Z-measurements remove the qubits in region D from the cluster. • Remaining cluster has non-trivial topology. 3.2 Encoded quantum gates Surface perpendicular to “time” supports a quantum code 3.2 Surface codes • Storage capacity of the code depends upon the topology of the code surface. 3.2 The surface code harmless error syndrome at endpoint harmful error Z ZZ X X X X Z ZZZ ZZ ZZ Z X X X X X X X X X Z = = plaquette stabilizer site stabilizer One qubit located on every edge Z X As Bp |ψ〉 = As|ψ〉 = Bp|ψ〉, ∀|ψ〉 ∈ HC, ∀s, p. (4) • Surface codes are stabilizer codes associated with 2D lattices. • Only the homology class of an error chain matters. A. Kitaev,quant-ph/9707021 (1997). 3.2 The surface code syndrome at endpoint harmful error Non-correctable error: small weight-distance away from non-trivial cycle. 3.2 Surface code on plane with holes site stabilizer not enforced X X X X plaquette stabilizer not enforced Z Z Z Z dual hole primal hole • There are two types of holes: primal and dual. • A pair of same-type holes constitutes a qubit. 3.2 Surface code on plane with holes Surface code with boundary: dual hole dual hole rough boundary Zd Xd primal hole primal hole smooth boundary Xp Zp primal qubit dual qubit • X-chain cannot end in primal hole, can end in dual hole. • Z-chain can end in primal hole, cannot end in dual hole. 3.2 Encoded quantum gates Defect D = worldline of hole. 3.2 Encoded quantum gates Topological quantum gates are encoded in the way worldlines of primal and dual holes are braided. 3.2 A CNOT-gate Xt X X c c dual hole dual hole rough boundary Zd Xd primal hole primal hole smooth boundary Xp Zp primal qubit dual qubit • Propagation relation: Xc −→ Xc ⊗Xt. • Remaining prop rel Zc → Zc, Xt → Xt, Zt → Zc ⊗ Zt for CNOT derived analogously. 3.2 Topological quantum gates 3.2 Universal gate set • Need one non-Clifford element: fault-tolerant preparation of |A〉 := X+Y√ 2 |A〉. Encoding of |A〉. • FT prep. of |A〉 provided through realization of magic state distillation∗. *: S. Bravyi and A. Kitaev, Phys. Rev. A 71, 022316 (2005). Part III.3: Threshold and Overhead Scaling 3.3 Sequential cluster state creation measurement conveyor belt for sequential cluster state creation depth d How large or small can the depth d be? 3.3 Sequential cluster state creation How large? measurement conveyor belt for sequential cluster state creation depth d Limitation: • Temporal order of measurements −→ accumulating memory error. 3.3 Sequential cluster state creation How small? measurement conveyor belt for sequential cluster state creation depth d • d ≥ 1. - d = 1: mapping to circuit model, d ≥ 2: cluster state. 3.3 Error model • Locality: Errors are assocoated with the elementary gates of a quantum computer. Errors act where the gates act. • Independence: Errors associated with different gates are stochastically independent. • Probabilistic error-model: The elementary errors are prob- abilistic Pauli-flips σx, σy, σz on all qubits. All these assumptions can be relaxed. Example: “Fault-tolerance with long-range correlated noise” (Dorit Aharonov, Alexei Kitaev, John Preskill, Phys. Rev. Lett. 96 (2006) 050504) 3.3 Error Model • Error sources: 2D (d = 1) 3D (d ≥ 2) 1. |+〉-preparation 2. cPhase-gates 3. Hadamard-gates 4. Local measurement 1. |+〉-preparation 2. cPhase-gates 3. Memory error 4. Local measurement • Every quantum operation has same error p. • Instant classical processing. 3.3 Fault-tolerance threshold Topological threshold in cluster region V : pc = 7.5× 10−3 (2D), pc = 6.8× 10−3 (3D). (5) Purification threshold for fault-tolerant |A〉-preparation: pc = 3.7× 10−2. (6) Topological EC sets the overall threshold. 3.3 Fault-tolerance threshold 0.76 0.78 0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.007 0.0072 0.0074 0.0076 0.0078 0.008 f i d e l i t y o f e r r o r c o r r e c t i o n error probability p l = 3 l = 5 l = 7 l = 9 l = 11 l = 13 Numerical estimate of the fault-tolerance threshold in 2D. 3.3 Overhead and Robustness • Denote by S (S′) the bare (encoded) size of a quantum cir- cuit. Then, for the described method: S′ ∼ S log3 S. (7) • The threshold is robust against variations in the error model such as higher weight elemetary errors, long-distance errors. 3.3 Overhead in absolute terms Operational cost of a fault-tolerant gate, at 1/3 threshold. Summary • The 3D cluster state has error-correction built-in • Encoded gates by topology • High error threshold of 0.7% Reading: Raussendorf and Harrington, Phys. Rev. Lett. 98, 190504 (2007). Raussendorf, Harrington and Goyal, New J. Phys. 9, 199 (2007).
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
China | 5 | 0 |
India | 5 | 20 |
United States | 4 | 5 |
France | 3 | 0 |
Japan | 2 | 0 |
Spain | 1 | 0 |
Canada | 1 | 0 |
City | Views | Downloads |
---|---|---|
Unknown | 10 | 22 |
Beijing | 5 | 0 |
Tokyo | 2 | 0 |
Madrid | 1 | 0 |
Waterloo | 1 | 0 |
Mountain View | 1 | 3 |
Ashburn | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Share to: