# Quantum Computation and the Localization of Modular Functors ⁄

**View the full content.**View Full Document

0 0 20 views

**Unformatted text preview:**

Found Comput Math 2001 1 183 204 2001 SFoCM DOI 10 1007 s102080010006 FOUNDATIONS OF COMPUTATIONAL MATHEMATICS The Journal of the Society for the Foundations of Computational Mathematics Quantum Computation and the Localization of Modular Functors Michael H Freedman Microsoft Research One Microsoft Way Redmond WA 98052 6399 USA michaelf microsoft com Dedicated to my teachers and collaborators Alexei Kitaev Greg Kuperberg Kevin Walker and Zhenghan Wang Their work has been the inspiration for this lecture Abstract The mathematical problem of localizing modular functors to neighborhoods of points is shown to be closely related to the physical problem of engineering a local Hamiltonian for a computationally universal quantum medium For genus 0 surfaces such a local Hamiltonian is mathematically defined Braiding defects of this medium implements a representation associated to the Jones polynomial and this representation is known to be universal for quantum computation 1 The Picture Principle Reality has the habit of intruding on the prodigies of purest thought and encumbering them with unpleasant embellishments So it is astonishing when the chthonian hammer 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 computation The most compelling theoretical question localization is yielding an Based on lectures prepared for the joint Microsoft University of Washington celebration of mathematics April 2000 and the AMS Meeting on Mathematics in the New Millennium UCLA August 2000 Date received May 15 2000 Final version received November 15 2000 Online publication February 20 2001 Communicated by Steve Smale AMS classification Primary 57R56 Secondary 68Q05 81Q70 82B10 94B99 20F36 184 M H Freedman answer which points the way to a solution of Quantum Computing s QC most daunting engineering problem reaching the accuracy threshold for fault tolerant computation After Shor s discovery 21 of a polynomial time factoring algorithm in the quantum model QC skeptics properly questioned whether a unitary evolution could ever be induced to process information fault tolerantly The most obvious tricks such as making a backup copy useful in a dissipative system e g pencil and paper are unavailable in quantum mechanics To overcome these difficulties a remarkable 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 quantum computation the accuracy threshold which would allow this combinatorial behemoth 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 also to one part in a million This places a formidable task before the engineer and physicist But within the year the beginnings of a new idea on fault tolerance had been generated by Kitaev 13 While the term is not yet present in that paper the idea is to construct first mathematically a quantum medium and to store quantum states as topological structures within the medium and eventually manipulate these states that is apply gates to them by topological transformations of the medium For our purposes we define a quantum medium as a collection of many finite level systems coupled together by a Hamiltonian H obeying a strong locality condition The individual systems are located in a two dimensional lattice or a more irregular cellulation of a surface 6 We postulate a constant d 0 so that H 6 H k and each H k Hk id where the identity is on all tensor factors subsystem not located within some ball B of diameter d in the lattice For example the Heisenberg magnet with H J 6a b edge a b is a quantum medium of diameter 1 But engineer be warned localizing H within balls of diameter d implies n ary interaction for n d 2 Controlling effective n ary terms for n 2 will be tricky in the extreme and probably 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 quantum information in a degenerate ground state V 6 of a quantum medium The medium is on a disk with pointlike defects which we treat as punctures The dimension of V 6 6 the punctured disk grows exponentially with the number of punctures Transformations of 6 that is braidings up to isotopy of the punctures 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 6 threshold for software error correction is to be realized by the discreteness of algebraic topology two Z 2 homology cycles are never close two words in Quantum Computation and the Localization of Modular Functors 185 the braid group are equal or distinct More exactly it is geometry not topology which 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 before nonzero terms h P L i ground state H are encountered and so the splitting of the ground state is estimated to be proportional to e L The length scale 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 to each other during braiding The engineering goal is to construct a physical quantum medium on a material disk whose ground state admits many localized excitations anions whose braidings effect computationally universal unitary transformations of the ground state It is further hoped that actual errors the result of unwanted noisy excitations are to be removed automatically by some relaxation process in which the system is coupled to a cold bath by another much weaker Hamiltonian H 0 The mathematicians first cut at the engineering goal is to produce a mathematical quantum medium with these properties and this is accomplished by the theorem below This first cut is not yet interesting to experimentalists since the Hamiltonian contains summands which have as many as 30 nontrivial indices but it represents an exact existence theorem The question for