©2001 SFoCMDOI: 10.1007/s102080010006Found. Comput. Math. (2001) 1:183–204The Journal of the Society for the Foundations of Computational MathematicsFOUNDATIONSOFCOMPUTATIONALMATHEMATICSQuantum Computation and the Localization of ModularFunctors∗Michael H. FreedmanMicrosoft ResearchOne Microsoft WayRedmond, WA 98052-6399, [email protected] to my teachers and collaborators: Alexei Kitaev, Greg Kuperberg, KevinWalker, and Zhenghan Wang. Their work has been the inspiration for this lecture.Abstract. The mathematical problem of localizing modular functors to neighbor-hoods of points is shown to be closely related to the physical problem of engineeringa local Hamiltonian for a computationally universal quantum medium. For genus= 0 surfaces, such a local Hamiltonian is mathematically defined. Braiding defectsof this medium implements a representation associated to the Jones polynomial andthis representation is known to be universal for quantum computation.1. The Picture PrincipleReality has the habit of intruding on the prodigies of purest thought and encumber-ing them with unpleasant embellishments. So it is astonishing when the chthonianhammer of the engineer resonates precisely to the gossamer fluttering of theory.Such a moment may soon be at hand in the practice and theory of quantum com-putation. The most compelling theoretical question, “localization,” is yielding an∗Based on lectures prepared for the joint Microsoft/University of Washington celebration ofmathematics April 2000 and the AMS Meeting on Mathematics in the New Millennium, UCLA,August 2000.Date received: May 15, 2000. Final versionreceived: November 15, 2000. Online publication: February20, 2001. Communicated by Steve Smale.AMS classification: Primary 57R56; Secondary 68Q05, 81Q70, 82B10, 94B99, 20F36.184 M. H. Freedmananswer which points the way to a solution of Quantum Computing’s (QC) mostdaunting engineering problem: reaching the accuracy threshold for fault tolerantcomputation.After Shor’s discovery [21] of a polynomial time factoring algorithm in thequantum model QC, skeptics properly questioned whether a unitary evolutioncould ever be induced to process information fault tolerantly. The most obvioustricks, such as making a backup copy, useful in a dissipative system (e.g., penciland paper) are unavailable inquantum mechanics. To overcomethese difficulties, aremarkable theoretical framework based on “stabilizer codes,” “transversal gates,”“cat-state-ancilli,” and nested concatenations of these was erected [22], [23], [2],[12], and [16]. While the result is a consistent recipe for fault-tolerant quantumcomputation, the accuracy threshold which would allow this combinatorial behe-moth to overcome its own overhead has been estimated as about 10−6, one i.i.d.error per one million physical gate operations and requiring gates accurate alsoto one part in a million. This places a formidable task before the engineer andphysicist. But within the year the beginnings of a new idea on fault tolerance hadbeen generated by Kitaev [13].While the term is not yet present in that paper the idea is to construct (firstmathematically) a “quantum medium” and to store quantum states as topologicalstructureswithinthemediumand(eventually)manipulatethesestates,thatis,applygates to them, by topological transformations of the medium. For our purposes,we define a quantum medium as a collection of many finite level systems coupledtogether by a Hamiltonian H obeying a strong locality condition: The individualsystems are located in a two-dimensional lattice or a more irregular cellulation of asurface6.Wepostulateaconstantd > 0sothat H = 6Hkandeach Hk= Hk⊗id,where the identity is on all tensor factors (= subsystem) not located within someball B`of diameter d in the lattice. For example, the Heisenberg magnet withH =−J6a,b=∂ edge*σa⊗*σbis a quantum medium of diameter = 1. (But engineerbe warned; localizing H`within balls of diameter = d implies n-ary interaction forn ∼ d2.Controllingeffectiven-arytermsforn ≥ 2willbe trickyintheextremeandprobably will require enforcing symmetries to cancel lower-order terms.) Kitaev’s“toric code” [13] in which quantum states are stored as first homology of a torus,can be counted as having d = 2; they require 4-ary interactions.We study here a partial generalization of the toric code which also stores quan-tum information in a degenerate ground state V(6) of a quantum medium. Themedium is on a disk with pointlike defects which we treat as punctures. The di-mension of V(6), 6 the punctured disk, grows exponentially with the number ofpunctures. Transformations of 6, that is, braidings (up to isotopy) of the punc-tures in space–time, 6 ×R, operate unitarily on V(6). Other work ([13], [19], and[14]) also explores the realization of elements of computation by braiding anionic“quasi-particles” or “defects” of a quantum medium.The vision is that stability of computation, at least sufficient to reach the 10−6threshold for “software” error correction, is to be realized by the discretenessof algebraic topology: two Z2-homology cycles are never “close,” two words inQuantum Computation and the Localization of Modular Functors 185the braid group are equal or distinct. More exactly, it is geometry not topologywhich will confer stability. Working in a lattice model one may calculate [13]that the perturbation Hamiltonian P must be raised to the length scale L beforenonzero terms, hζ |PL|ηi,ζ,η ∈ ground state (H), are encountered and so thesplitting of the ground state is estimated to be proportional to e−Ä(L). The lengthscale in the previous two examples are: L = (length of shortest essential cycle);and in the anionic context, the closest that two defects are allowed to come toeach other during braiding. The “engineering goal” is to construct a physicalquantum medium on a material disk whose ground state admits many localizedexcitations (“anions”) whose braidings effect computationally universal unitarytransformations of the ground state. It is further hoped that actual “errors,” theresult of unwanted noisy excitations, are to be removed automatically by somerelaxation process in which the system is coupled to a cold bath by another muchweaker Hamiltonian H0. The mathematicians first cut at the engineering goalis to produce a mathematical quantum medium with these properties and thisis accomplished by the theorem