Transcription
Topological quantum computingfor beginnersJohn Preskill, CaltechKITP 7 June 2003http://www.iqi.caltech.edu/
http://www.theory.caltech.edu/ preskill/ph219/ph219 2004.html
KitaevFreedman
KitaevKitaev, Fault-tolerant quantumcomputation by anyons (1997).Preskill and Ogburn, Topologicalquantum computation (1997).Preskill, Fault-tolerant quantumcomputation (1997).Mochon, Anyons from non-solvablegroups are sufficient for universalquantum computation (2003).Mochon, Anyon computers withsmaller groups (2004).FreedmanFreedman, Larsen, and Wang, Amodular functor which is universal forquantum computation (2000).Freedman, Kitaev, and Wang,Simulation of topological field theoriesby quantum computers (2000).
Abstract for "Topological quantum computing forbeginners," by John PreskillI will describe the principles of fault-tolerant quantumcomputing, and explain why topological approaches to faulttolerance seem especially promising. A two-dimensionalmedium that supports abelian anyons has a topologicaldegeneracy that can exploited for robust storage of quantuminformation. A system of n nonabelian anyons in twodimensions has an exponentially large topologically protectedHilbert space, and quantum information can be processed bybraiding the anyons. I will discuss in detail two cases wherenonabelian anyons can simulate a quantum circuit efficiently:fluxons in a "nonabelian superconductor," and "Fibonaccianyons" with especially simple fusion rules.
QuantumComputationFeynman ‘81Deutsch ‘85Shor ‘94
A computer that operates on quantum states canperform tasks that are beyond the capability ofany conceivable classical computer.Feynman ‘81Deutsch ‘85Shor ‘94
Finding Prime 0812303371781887966563182013214880557 ? ?
Finding Prime 0812303371781887966563182013214880557 064832555157243 069600999044599Shor ‘94
Quantum computer: the model(1) Hilbert space of n qubits:spanned by( )H C2n x1 〉 x0 〉 , x {0,1}n x〉 xn 1 〉 xn 2 〉 Important: the Hilbert space is equipped with a natural tensorproduct decomposition into subsystems.2nC C C C 222 C2n timesPhysically, this decomposition arises from spatial locality.Elementary operations (“quantum gates”) that act on a smallnumber of qubits (independent of n) are “easy;” operations thatact on many qubits (increasing with n) are “hard.”(2) Initial state: 000 0〉 0〉 n
Quantum computer: the model(3) A finite set of fundamental quantum gates:{U ,U ,U , U }123nGEach gate is a unitary transformation acting on a boundednumber of qubits. The gates form a universal set: arbitraryunitary transformations can be constructed, to any specifiedaccuracy, as a quantum circuit constructed from the gates:U (Universal gates are generic.)Important: One universal set of gates can simulate anotherefficiently, so there is a notion of complexity that is independentof the details of the quantum hardware.
Quantum computer: the model(4) Classical control:The construction of a quantum circuit is directed by a classicalcomputer, i.e., a Turing machine. (We’re not interested in what aquantum circuit can do unless the circuit can be designedefficiently by a classical machine.)(5) Readout:At the end of the quantum computation, we read out the resultby measuring σ z , i.e., projecting onto the basis 0〉 , 1〉{(We don’t want to hide computational power in the ability toperform difficult measurements.)}
Quantum computer: the model(1)(2)(3)(4)(5)Clearly, the model can besimulated by a classicaln qubitscomputer with access to ainitial staterandom number generator.quantum gatesBut there is an exponentialclassical control slowdown, since the simulationreadoutinvolves matrices of exponentialsize.The quantum computer might solve efficiently someproblems that can’t be solved efficiently by a classicalcomputer. (“Efficiently” means that the number ofquantum gates polynomial of the number of bits ofinput to the problem.)
QuantumError CorrectionShor ‘95Steane ‘95
Quantum information can be protected,and processed fault-tolerantly.Shor ‘95Steane ‘95
QuantumComputerERROR!DecoherenceEnvironmentIf quantum information iscleverly encoded, it can beprotected from decoherenceand other potential sources oferror. Intricate quantumsystems can be accuratelycontrolled.
Two Physical SystemsWhat is the difference between:A: HumanImperfect hardware.Hierarchical architecture witherror correction at all scales.B: ChipReliable hardware.Information processing prevents information loss.
TopologyQuantumNoisyGateGate
Topological quantum computation(Kitaev ’97, FLW ‘00)annihilate pairs?braidKitaevbraidbraidFreedmantimecreate pairs
Topological quantum computation(Kitaev ’97, FLW ‘00)Physical faulttolerance withnonabelian anyons:uncontrolledexchange ofquantum numberswill be rare ifparticles are widelyseparated, andthermal anyons aresuppressed.time
Models of (nonabelian) anyonsA model of anyons is a theory of a two-dimensional medium with a massgap, where the particles carry locally conserved charges. We define themodel by specifying:1. A finite list of particle labels {a,b,c, }. These indicate the possiblevalues of the conserved charge that a particle can carry. If a particle iskept isolated from other particles, its label never changes. There is aspecial label “0” – indicating trivial charge, and a charge conjugationoperator C: a a (where 0 0). (Note: for “particle” you may read“puncture.”)2. Rules for fusing (and splitting). These specify the possible values of thecharge that can result when two charged particles are combined.3. Rules for braiding. These specify what happens when two neighboringparticles are exchanged (or when one is rotated by 2π).a1a2a3a4an
FusionFusion rules:a b N c b acabcV V VcabFusion vector space:acba0abcdim(V ) Ncabbca cbabµc(µ 1, 2, 3, , Nabc)a bµc
FusionFusion rules:a b N c b acabcFusion vector space:aaV V Vcabcba0abccabdim(V ) Ncbaa00 aa The charge 0 fuses trivially, and a isthe unique label that can fuse with ato yield charge 0.a0
FusionaabbµccAn anyon model is said to be nonabelian if for some a, and b,ccabbaccThen there is a “topological Hilbert space” that can encodenontrivial quantum information. This encoding is nonlocal; theinformation is a collective property of the two anyons, notlocalized on either particle. When the particles with labels aand b are far apart, different states in the topological Hilbertspace look identical to local observers. In particular, thequantum states are invulnerable to decoherence due to localinteractions with the environment. That is why we propose touse this encoding in a quantum computer.dim( V ) N 2.
FusionababµccWhen we hide the quantum state from the environment, wehide it from ourselves as well! But, when we are ready to readout the quantum state (for example, at the conclusion of aquantum computation), we can make the information locallyvisible again by bringing the two particles together, fusingthem into a single object. Then we ask, what is this object’slabel? In fact, it suffices (for universal quantum computation)to be able to distinguish the label c 0 from c 0. It isphysically reasonable to suppose that we can distinguishannihilation “into the vacuum” (c 0) from a lump that isunable to decay because of its conserved charge (c 0).
Abelian vs. nonabelianAbelian anyon models can also be used for robustquantum memory, e.g., a model of 2 fluxons andtheir dual 2 charges. A qubit is realized becausethe 2 flux in a hole can be either trivial or nontrivial(the information is carried by the labels themselves,not by the fusion states). This information is hiddenfrom the environment by making the holes large andkeeping them far apart (to prevent flux fromtunneling from one hole to another, or to the outsideedge, and to prevent the world lines of chargesfrom winding about holes). -- Kitaev (1996)However, this information may not be harder to read out. We’d need tocontract a hole to see if a particle appears, or perform a delicateinterference experiment to detect the flux, or Alternatively, by mixing the 2 with electromagnetic U(1), we might do thereadout via a Senthil-Fisher type experiment (i.e., one that would actuallywork)!-- Ioffe et al. (2002)Anyway, with nonabelian anyons we can exploit topology not just to storequantum information, but also to process it!
Associativity of fusion: the F-matrixaabbµeνd(a b) c a (b c)cc a(F ) µνe' ' ′d e ' µ 'ν 'abc eµνbcµ′ν′e’dThere are two natural ways to decompose the topologicaldHilbert space Vabc of three anyons in terms of the fusionspaces of pairs of particles. These two orthonormal bases arerelated by a unitary transformation, the F-matrix.
Braiding: the R-matrixabaacbR : V V :cbacabbµc (Rµ′)′c µba µcabµ′cWhen two neighboring anyons are exchanged counterclockwise,their total charge c is unaltered; since the particles swap positions,ccVVthe fusion space ba changes to the isomorphic space ab . Thisisomorphism is represented by a unitary matrix, the R-matrix.aThe R-matrix also determines thetopological spin of the label a, i.e., thephase acquired when the particle isa2π iJ a0rotated by 2π:e Raaa
Models of (nonabelian) anyonsA model of anyons is a theory of a two-dimensional mediumwith a mass gap, where the particles carry locally conservedcharges. We define the model by specifying:1. A finite label set {a,b,c, }.c2. The fusion rules a b c N ab c3. The F-matrix (expressing associativity of fusion).4. The R-matrix (braiding rules).These determine a representation of the mapping class group(braiding plus 2π rotations), and define a unitary topologicalmodular functor (UTMF), the two-dimensional part of a (2 1)dimensional topological quantum field theory (TQFT) --related to a (1 1)-dimensional rational conformal field theory(RCFT).a1a2a3a4an
Example: Yang-Lee(Fibonacci) Model110 or 1The charge takes two possible values: 0 (trivial)and 1 (nontrivial, and self-conjugate). Anyonshave charge 1.Two anyons can “fuse” in eitherof two ways: 1 1 0 1This is the simplest of all nonabelian anyon models. Yet itsdeceptively simple fusion rule has profound consequences.In particular, the fusion rule determines the F-matrix and Rmatrix uniquely; the resulting nontrivial braiding propertiesare adequate for universal quantum computation (pointed outby Kuperberg).
Nonabelian Anyons: Yang-Lee model1Suppose n anyons have a trivial total charge 0.What is the dimension of the Hilbert space?11111110 or 110,1 0,1 0,1 0,1 0,1 0,1110,11The distinguishable states of n anyons (a basis for the Hilbertspace) are labeled by binary strings of length n-3. 1 1 1But it is impossible to have two zeros in a row:1001
Nonabelian Anyons: Yang-Lee model1Suppose n anyons have a trivial total charge 0.What is the dimension of the Hilbert space?11111110 or 110,1 0,1 0,1 0,1 0,1 0,1110,11The distinguishable states of n anyons (a basis for the Hilbertspace) are labeled by binary strings of length n-3. 1 1 1But it is impossible to have two zeros in a row:1Therefore, the dimension is a Fibonacci number:001D 2, 3, 5, 8, 13, 21, 34, 55, 89, .Asymptotically, the number of qubits encoded by each anyon is:()log 2 φ log 2 1 5 / 2 log 2 (1.618) .694
Nonabelian Anyons: Yang-Lee model1Asymptotically, the number of qubitsencoded by each anyon is:(10 or 1)log 2 φ log 2 1 5 / 2 log 2 (1.618) .694 We say that d φ is the (quantum) dimension of theFibonacci anyon This counting vividly illustrates that the qubits are a nonlocal property ofthe anyons, and that the topological Hilbert space has no particularlynatural decomposition as a tensor product of small subsystems.Anyons have some “nonlocal” features, but they are not so nonlocal as toprofoundly alter the computational model (the braiding of anyons can beefficiently simulated by a quantum circuit) 11111
The quantum dimensionEvery anyon label a has a quantum dimension, which we maydefine as follows: Imagine creating two particle-antiparticle pairs,and then fusing the particle from one pair with the antiparticle ofthe other aaa 1,a1 daAnnihilation occurs with probability 1/da2. This is a naturalgeneralization of the case where the charge is an irreduciblerepresentation R of a group G, where the “quantum dimension” isjust the dimension R of the representation (which counts thenumber of “colors” going around the loop). But there is no logicalreason why a dimension defined this way must be can integer,and in general it isn’t an integer.
The quantum dimensionThere is a more convenient normalization convention for particleantiparticle pairs.aEach time we add anothertooth to the saw, it cost usanother factor of 1/da.aWe can compensate for thatfactor by weighting eachpair creation or annihilationaeven by a factor of d a .a dadadadaadadadaWith this convention, a closed loop has weightad a , as though we were counting colors Now we can deform the world line of a particle (e.g., addingand removing “teeth”) without altering the value of a diagram.
The quantum dimensiond a db c,µbµ aba Nµcab cc,µccabcµabµ N dccabcTherefore, the vector of quantum dimensions is the (PerronFrobenius) eigenvector of each fusion rule matrix, witheigenvalue da: (N ) dcca bc d a db N a d ( d a ) d
The quantum dimension, u〉 dN a u 〉 d a 〈u aaNbaaa aab1ab2ab3 dim(Vab4baaa aab5ab6) N N Nb1aa 〈b ( N a ) a〉 〈b u 〉 dn 1ab2ab1b3ab2N〈u a〉 Dbbn-2{bi }n 1ababn 2nad db2DThus the quantum dimension controls the rate of growth ofthe n-particle Hilbert space. The normalization factorD 2d aais called the total quantum dimension of the anyon model.
The quantum dimensioncWhat if we create pairs ofdifferent types, and then fuse?a( d a db ) p(ab c) µ µbµµac Ncab p (ab c) bcµµ N dccabccabN dcabd a db(generalizes what we found for the case b a )
The quantum dimensionp (ab c) cabN dccad a dbbSuppose we create a dense gas of anyons (by “quenching”), with anarbitrary initial distribution of particle types. Then we let the gas anneal,but not completely. The distribution of particle types converges to a steadystate distribution satisfying: papb p (ab c) pca ,bThe solution to this equation is:pa d2aD2 particle populations proportional to square of quantum dimension.
ddBraiding: the B-matrix B : Vacb Vabc :For the n-anyon Hilbert space, we may use the standard basis:a2a1a3b1a4b2a5b3a6b4b5a7an-1 anb6bbn-2The effect of braiding can be expressed in this basis:bace d(B ) µνe′ ' 'e ' µ ′ν 'dabc eµνabe’And the matrix B is determined by R and F:F R c 1F d
Topological quantum computation(Kitaev ’97, FLW ‘00)annihilate pairs?braidKitaevbraidbraidFreedmantimecreate pairs
Topological quantum computation1. Create pairs of particles of specified types.2. Execute a braid.3. Fuse neighboring particles, and observe whether they annihilate.Claim: This process can be simulated efficiently by a quantum circuit.Need to explain:1. Encoding of topological Hilbert space.2. Simulation of braiding (B-matrix as a two-qudit gate).3. Simulation of fusion (F-matrix plus a one-qudit projective measurement).a2a1b1a3b2a4b3an-2 an-1bn-3an( VAlthough the topological vector spaces are notthemselves tensor products of subsystems, they allfit into a tensor product of d-dimensional systems,where this qudit is the “total fusion space” of threeanyons a ,b , cHdd 0abc) ( n 2)0N abca ,b , c
Topological quantum computationa2a1b1a3an-2 an-1a4b2bn-3b3an ( Hd ) ( n 2)Therefore, the topological model is no more powerful than the quantumcircuit model. But is it as powerful? The answer depends on the model ofanyons, and in particular on the properties of the R-matrix and F-matrix.To simulate a quantum circuit, we encode qubits in the topological vectorspace, and use braiding to realize a set of universal quantum gates actingon the qubits.That is, the image of our representation of the braid group Bn on n strandsshould be dense in SU(2r), for some r linear in n.Example: in the Fibonacci model, we can encode a qubit in the two0dimensional Hilbert space V1111of four anyons with trivial total charge.111a1a {0,1}But what are R and Fin this model?
Consistency of braiding and fusingThe R-matrix (braiding), and the F-matrix (associativity of fusing) are highlyconstrained by algebraic consistency requirements (the Moore-Seiberg polynomialequations). In the case of the Fibonacci model, these equations allow us tocompletely determine R and F from the fusion rules.By a sequence of “F-moves” and “R-moves,” we obtain an isomorphism between twotopological Hilbert spaces, that is, a relation between two different canonical bases.This relation must not depend on the particular sequence of moves, only on thebasis we start with and the basis we end up with. For example, there are 5 differentways (without any exchanges) to fuse five particles, related by F-moves:1234F123412345aPentagon equation:cbd551235412354(F ) (F ) (F ) (F ) (F )ec5a 34 b5 d12 c ab e123 a5 d1e 4 bc5234 e
Consistency of braiding and fusing123F12R2b3Fb234aR4134cR21F13F21aR43c4Hexagon equation:4 (Fb)4 b123 a41bR(F)4 c231 b Ra12(F)4 c213 aR13cFurthermore, if the pentagon and hexagon equations are satisfied, then all sequencesof F- and R-moves from an initial basis to a final basis yield the same isomorphism!A systematic (in principle) procedure forconstructing anyon models:1. Assume a fusion rule.2. Solve pentagon and hexagonequations for R and F.-- If no solutions, the fusion rules areincompatible with local quantum physics.-- If multiple solutions, each is a validmodel.
Example: Fibonacci model11111 Σb Faba1 τF τ 1b11Ra:a1τ e 4π i / 5 , R τ 0 , τ 2π i / 5 e 0()5 1 / 2 φ 1This solution is unique (aside from freedom to redefine phasesand take the parity conjugate). Furthermore, products of the111111noncommuting matrices R and FRF-1(representing the generators of theabbraid group B3) are dense in SU(2).11
Example: Fibonacci model111111ab11We encode a qubit in four anyons. To simulate a quantum circuit, we needto do (universal) two-qubit gates.The two-qubits are embedded in the13-dimensional Hilbert space of eightanyons.The representation of B13 determined by our R and F matrices isuniversal – i.e., dense in SU(13), so in particular we can approximateany SU(4) gate arbitrarily well with some finite number of exchanges. Ifwe fix accuracy of the approximation to the gate, we can use quantumerror- correcting codes and fault-tolerant simulation to perform anefficient and reliable quantum computation.Here quantum-error correction might be needed to correct for the (small)flaws in the gates, but not to correct for storage errors.
“Leakage”111111ab11The computation takes place in the r-qubit subspace of a system of 4ranyons. As errors accumulate, the state of the computer might drift our ofthis subspace (the “leakage” problem).But we can include leakagecorrector gates in oursimulation. This gate is theidentity acting on data in thecomputational space, butreplaces a leaked qubit bythe standard state 0〉 in thecomputational d dataleakeddataLeakageCorrector 0〉For example, we can use a quantum teleportation protocol for leakagecorrection (in effect, this turns quantum leakage into classical leakage,which is easier to detect and correct).
Topological quantum computationTo summarize, we can simulate a universal quantum computer using (forexample) Fibonacci anyons, if we have these capabilities:1. We can create pairs of particles.2. We can guide the particles along a specified braid.3. We can fuse particles, and distinguish complete annihilation fromincomplete annihilation.-- The temperature must be small compared to the energy gap, so that strayanyons are unlikely to be excited thermally.-- The anyons must be kept far apart from one another compared to thecorrelation length, to suppress charge-exchanging virtual processes, exceptduring the initial pair creation and the final pair annihilation.
(Nonabelian) anyonsAn anyon model is characterized by its label set,fusion rules, F-matrix, and R-matrix.Classifying the models (finding all solutions tothe pentagon and hexagon equations) is animportant (hard) unsolved mathematical problem.We know how to find some examples (e.g.,Chern-Simons theories), but we don’t know howrich the possibilities are.Such a classification would be an important steptoward classifying topological order in twodimensions.abµcFRThere would still be more to do, though For example, this would be aclassification of gapped two-dimensional bulk theories, and one bulk theorycan correspond to more than one (1 1)-dimensional theory describing edgeexcitations. And of course, we would like to know, both for practical andtheoretical reasons, whether the model can be realized robustly with somelocal Hamiltonian (and how to realize it).
Topological quantum memoryKitaev ‘96Qubits can reside in holes in a planar array, where the holes carry Z2charge or flux. Then the quantum memory is topologically stable, butnontopological couplings between holes are needed to complete a set ofuniversal gates.This scheme might be realizable in suitably designed Josephson-junctionarrays, which have a phase that can be interpreted as a condensate ofobjects with charge 4e. A hole in the array can carry charge 2e or fluxIoffe et al. ‘02Φ0/2 2π/4e.
Quantum many-body physics:Exotic phases in optical latticesAtoms can be trapped inan optical lattice. Thelattice geometry andinteractions betweenneighbors can be chosenby the “material designer”(direction-dependent andspin dependent tunnelingbetween sites).In particular, Duan, Lukin, and Demler (cond-mat/0210564) havedescribed how Kitaev’s honeycomb lattice model, which supportsnonabelian anyons, can be simulated using an optical lattice.
Topological quantum computingfor beginnersJohn Preskill, CaltechKITP 7 June 2003http://www.iqi.caltech.edu/
c µ ab c ( ) µ′ c Rba µ µ µ ′ ′ ba c ab c When two neighboring anyons are exchanged counterclockwise, their total charge c is unaltered; since the particles swap positions, the fusion space changes to the isomorphic space . This isomorphism is represented by a unitary matrix, the R-matrix. c Vba c Vab The R-matrix also .
