Surface code implementation of block code state distillation Austin G. Fowler1, Simon J. Devitt2, Cody Jones3 1Centre for Quantum Computation and Communication Technology, School of Physics, The University of Melbourne, Victoria 3010, Australia, 2National Institute for Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan, 3Edward L. Ginzton Laboratory, Stanford University, Stanford, California 94305-4088, USA (Dated: January 31, 2013) State distillation is the process of taking a number of imperfect copies of a particular quantum state and producing fewer better copies. Until recently, the lowest overhead method of distilling √ states |A(cid:105)=(|0(cid:105)+eiπ/4|1(cid:105))/ 2 produced a single improved |A(cid:105) state given 15 input copies. New block code state distillation methods can produce k improved |A(cid:105) states given 3k+8 input copies, potentially significantly reducing the overhead associated with state distillation. We construct an explicit surface code implementation of block code state distillation and quantitatively compare 3 the overhead of this approach to the old. We find that, using the best available techniques, for 1 parametersofpracticalinterest,blockcodestatedistillationdoesnotalwaysleadtoloweroverhead, 0 and, when it does, the overhead reduction is typically less than a factor of three. 2 n Oneofthegrandchallengesof21st-centuryphysicsand I. BLOCK CODE STATE DISTILLATION a engineering is to construct a practical large-scale quan- J tum computer. One of the primary ways theoretical re- 9 The state we are interested in distilling is |A(cid:105) = √ search can reduce the magnitude of this challenge is to 2 (|0(cid:105)+eiπ/4|1(cid:105))/ 2. Anextendablequantumcircuittak- devise ways ofperforming agiven quantum computation ing 3k+8 copies of |A(cid:105), each with probability p of error, ] using fewer qubits and quantum gates while simultane- h and producing k copies, each with probability approxi- ously leaving all other engineering targets unchanged. p mately (3k+1)p2 of error [23], is shown in Figs. 1–2. T - gate application is delayed using the circuit of Fig. 2a. t n State distillation [1, 2] is a procedure required by This circuit has the additional advantage of eliminating a the majority of concatenated quantum error correction X errors from the T gate, leaving us only needing to de- u (QEC) schemes [3–7], with the exception of the Steane tect Z errors. Each T gate consumes one |A(cid:105) state as q code[8],andrequiredbythemajorityoftopologicalQEC shown in Fig. 2b. All output states are discarded if any [ schemes [9–19], with the exception of a 3-D color code errors are detected. Fig. 1 has been designed to detect 1 [20] and a non-Abelian code [21]. As such, the search for a Z error during any single T gate. All other quantum v lower overhead methods of implementing state distilla- gates are assumed to be perfect, or at least sufficiently 7 tion is of great importance. reliable that the probability of error from gate failure 0 is negligible compared to the probability of error from 1 7 multiple T gate errors. The first order probability that Two recent works [22, 23] are of particular note, both . the outputs will be rejected is therefore approximately 1 independently proposing block code based methods tak- (3k+8)p, with this expression approximate due to the 0 ing 3k+8 imperfect copies of a particular state and dis- ability of Fig. 2b to introduce S errors and the ability 3 tilling k improved copies. However, a detailed analysis 1 of Fig. 2a to filter out everything except Z errors. First of the overhead in terms of qubits and quantum gates : orderexpressionsareappropriateaswerestrictourselves v was not performed. In this work, we explicitly construct to (3k+8)p(cid:28)1. Xi a surface code [19] implementation of one of these block For k = 2+4j, the block code has the property that code state distillation methods [23]. The surface code is r transversalS†X implementslogicalSX oneachencoded a believed[24]tobethelowestoverheadcodethatwillever logical qubit. Each logical qubit is prepared in |A(cid:105), and exist for a quantum computer consisting of a 2-D array henceintheabsenceoferrorsthemultiple|A(cid:105)blockcode ofqubitswithnearestneighborinteractions[25–28]. Fur- willbeinthe+1eigenstateoftransversalS†X =T†XT. thermore, this code can be used to achieve time-optimal The top qubit of Fig. 1 should therefore report +1, with quantum computation [29]. The surface code therefore all output discarded if -1 is reported. This single mea- provides an excellent framework to gauge the cost of the surement is sufficient to detect a single Z error during new block code state distillation methods. the first two layers of T gates. The block code has four stabilizers, specif- The discussion shall be organized as follows. In Sec- ically X X X ...X , X X ...X X , 0 2 3 k+2 1 2 k+1 k+3 tion I, the quantum circuit used to perform block code Z Z Z ...Z , and Z Z ...Z Z . Detecting a 0 2 3 k+2 1 2 k+1 k+3 state distillation is presented. In Section II, we perform Z error in the final layer of T gates involves using the a detailed comparison of the overhead of concatenated stabilizers X X X ...X and X X ...X X . 0 2 3 k+2 1 2 k+1 k+3 15-1 and block code state distillation. In Section III, we For arbitrary encoded logical states, in the absence of summarize our results and discuss further work. errors, the block code will be in the +1 eigenstate of 2 + + M M X X + T T M 0 + T M 0 X X + T T M 1 0 T M X X 0 T T MX 2 + T MX 1 0 T T MX 3 0 T MX 0 T T T MX 4 0 T MX 2 0 T T T MX 5 0 T MX 0 T T T MX 6 0 T MX 3 0 T T T MX 7 0 T MX 0 T M 4 X + 0 0 T M X + 1 0 T M X + 2 + 0 + 3 0 T M 5 X 0 T M X FIG. 1: Extendable quantum circuit taking 3k+8 copies of 0 T M |A(cid:105),eachwithprobabilitypoferror,andproducingk copies, X eachwithapproximateprobability(3k+1)p2 oferror. Inthe + 1 figure, k = 4. The repeating unit cell is highlighted. Note that k must be even. A box encircles output numbers. Each 0 T MX 6 T gate consumes one |A(cid:105) state as shown in Fig. 2. 0 T M X 0 T M X a.) Y Z + 2 Y T 0 T M 7 0 T M X X 0 T M X 0 T M X b.) A X S + 3 Y T Y M Z FIG. 3: Constant depth extendable circuit implementing 3k+8tok statedistillationfork=4. Boxesencircleoutput numbers. Usingthesurfacecode,bentCNOTscanbeimple- FIG. 2: a.) Circuit useful for delaying the application of T mentedexactlyasshown(seeFig.5). Therepeatingunitcell and eliminating X errors. b.) Circuit implementing a T gate is highlighted. √ using an ancilla state |A(cid:105)=(|0(cid:105)+eiπ/4|1(cid:105))/ 2. these stabilizers. If the products of the individual X basis measurements comprising these stabilizers are not both +1, all output is discarded. convenient for physical implementation. A surface code Assumingtheabovethreechecksarepassed,alloutput CNOT is shown in Fig. 4 [12, 13, 19]. This topological isaccepted,withbyproductZ operatorsnotedasfollows. structure can be arbitrarily deformed without changing For each encoded logical qubit 0≤n<k, the associated the computation it implements. This permits direct im- logical X operator takes the form X X X . If plementation of the bent CNOTs (Fig. 5). This can be n+2 k+2 k+3 the product of these measurements is -1, a byproduct Z compressedtoFig.6. SeeAppendixAforastep-by-step is associated with output n. descriptionofthecompressionprocessandlargerversions Fig.3showsarearrangedversionofFig.1thatismore of these figures. 3 a.) b.) FIG. 4: a.) CNOT quantum circuit example. b.) Equivalent surfacecodeCNOT[12,13,19]. Timerunsfromlefttoright. The scale of the figure is set by the code distance d. Small cubesared/4aside. Longerblockshavelengthd. Eachunit of d in the temporal direction represents a round of error de- tection. Eachunitofdinthetwospatialdirectionsrepresents two qubits. The structures are called defects, and represent space-time regions in which error detection has been turned off. FIG. 5: Depth 31 canonical surface code implementation of Fig. 3. A larger version of this figure can be found in Ap- pendix A. FIG. 6: Depth 12 compressed surface code implementation of Fig. 3. A larger version of this figure can be found in Appendix A, along with step-by-step images explaining how II. OVERHEAD COMPARISON it was obtained. Suppose we desire logical |A(cid:105) states with error p out andcanpreparelogical|A(cid:105)stateswitherrorp . Wewill detection in a square patch of surface code as a function in consider values p = 10−2, 10−3, and 10−4, as this cov- of p and code distance d is shown in Fig. 7 [30]. in g ers the currently believable physically achievable range, Focusinginitiallyonthesimpler15-1concatenateddis- and values pout = 10−5, ..., 10−20, as this covers essen- tillation process, the topological structure required for a tially the entire range that could believably be useful in single level of distillation is shown in Fig. 8. Dark struc- a practical quantum algorithm. tures are called dual defects, light structures are called The process of preparing arbitrary logical states is primal defects. The geometric volume of the structure called state injection, and in the surface code approxi- can be defined as the number of primal cubes in a min- mately10gatesarerequiredtoworkbeforeerrorprotec- imum volume cuboid containing the structure. In this tionisavailable[19]. Itisthereforereasonabletoassume case, the structure is 6 cubes high, 16 cubes wide, and 2 the physical gate error rate p is an order of magnitude cubesdeep,foratotalV =192. Eachprimalcubehasdi- g less than p . The logical error rate per round of error mensions d/4, each longer prism has length d. Each unit in 4 10-1 10-2 )L p e ( 10-3 at X error r 10-4 ddd===357 al 10-5 d=9 gic d=11 Lo 10-6 d=15 d=25 10-7 d=35 d=45 110 -×8 10-5 1 × 10-4 1 × 10-3 1 × 10-d2=55 FIG. 9: A forest of d separated straight defects of circumfer- enced. Twosquaresurfacesofdimensiond×dhavebeenin- Depolarizing probability (p) cluded. Thelogicalerrorrateofthesesurfacesupperbounds the probability of a logical error connecting neighboring de- FIG.7: Probabilityp oflogicalX errorperroundofsurface fects and encircling a single defect. L codeerrorcorrectionforvariouscodedistancesdandphysical gateerrorratesp . Theasymptoticcurves(dashedlines)are g quadratic,cubic,quarticfordistancesd=3,5,7respectively. logical errors. The probability of each of these types of logical error per round of error detection can be upper bounded by the probability of logical error per round of error detection of a square surface. There are more potential logical errors per round connecting opposing boundaries in a square surface of distance d than there care connecting distinct defects or encircling a single de- fect. Given the per round probability of logical error p (d,p ) of a square surface, we can upper bound the L g logical error rate of a plumbing piece P (d,p ) by 2× L g 3×5d/4×p (d,p ), where the factor of 5d/4 is for the L g number of rounds of error detection in a plumbing piece, the factor of 3 is for the number of distinct classes of logical error, and the factor of 2 is due to the fact that FIG. 8: State distillation method taking 15 input |A(cid:105) states, a single plumbing piece can contain both a primal and a each with error p, and producing with probability 1−15p a dual defect. From Fig. 7, p (d,p ) ∼ 0.1(100p )(d+1)/2, single output |A(cid:105) state with error 35p3. Each unit of d in L g g the temporal direction (up in this figure) corresponds to a implying PL(d,pg)∼d(100pg)(d+1)/2. round of surface code error detection, each unit of d in the Given input error rate p , with 15-1 state distillation in two spatial directions corresponds to two qubits. the output error rate can be made arbitrarily close to p = 35p3 by using a sufficiently large d to eliminate dist logical errors during distillation. However, logical errors of d in the temporal direction (up in Fig. 8) corresponds do not need to be completely eliminated, and we define to a round of surface code error detection, each unit of d (cid:15)p to be the amount of logical error introduced. For dist in the two spatial directions corresponds to two qubits. (cid:15) = 1, the logical circuitry introduces as much error as It is therefore straightforward to convert the geometric distillation fails to eliminate, and p =(1+(cid:15))p . We out dist volume to an absolute volume in units of qubits-rounds. shall assume that logical failure anywhere during distil- Afragmentofthecompletestructureofedgelength5d/4 lation leads to the output being incorrect and accepted. withaprimalcubepotentiallycenteredwithinitiscalled Let us consider a specific example. Suppose p = in aplumbingpiece. Geometricvolumeisthereforeinunits 10−3, our desired p = 10−15, and our chosen (cid:15) = 1. out of plumbing pieces. In order to calculate the overhead of Our top level of state distillation must therefore have a state distillation, we will need to first reasonably upper probability of logical error no more than (cid:15)p /(1+(cid:15))= out boundtheprobabilityoflogicalerrorperplumbingpiece. 5×10−16. Given V =192 for 15-1 state distillation, this Consider a forest of straight, d separated parallel de- meansweneedVP (d,p )=192P (d,10−4)<5×10−16, L g L fects of circumference d, as shown in Fig. 9. Each defect implying d = 19. The states input to the top level can be assumed responsible for logical errors connecting of distillation must have an error rate no more than (cid:112) ittotwoofitsneighboringdefectsandalsoselfencircling p = 3 p /35(1+(cid:15)) = 2.4 × 10−6. Since this is less out 5 pin pin pout 10−2 10−3 10−4 pout 10−2 10−3 10−4 10−5 4.0×107 1.3 ×106 2.6×105 10−5 2.3 ×107 1.4×106 1.5 ×105 10−6 6.7×107 1.3 ×106 2.6 ×105 10−6 2.6 ×107 2.8×106 3.0×105 10−7 7.2×107 2.1 ×106 5.6 ×105 10−7 4.2 ×107 3.0×106 5.9×105 10−8 7.5 ×107 1.1×107 5.6 ×105 10−8 1.1×108 5.9 ×106 1.3×106 10−9 1.0×108 1.2×107 1.3 ×106 10−9 2.0×108 6.1 ×106 1.5×106 10−10 1.1 ×108 1.2×107 1.3 ×106 10−10 2.4×108 6.7 ×106 2.4×106 10−11 1.7×108 1.4×107 5.3×106 10−11 2.5×108 7.8 ×106 2.7×106 10−12 6.4×108 1.4×107 6.1×106 10−12 2.6×108 1.1 ×107 2.7 ×106 10−13 6.5×108 2.8×107 6.1×106 10−13 2.7×108 1.3 ×107 2.8 ×106 10−14 7.0×108 2.8×107 6.1×106 10−14 3.0 ×108 3.8×107 3.6 ×106 10−15 1.1×109 3.1×107 7.7×106 10−15 3.7 ×108 4.4×107 3.9 ×106 10−16 1.1×109 3.1×107 1.2×107 10−16 3.9 ×108 4.4×107 6.1 ×106 10−17 1.2×109 3.5×107 1.2×107 10−17 4.1 ×108 4.6×107 6.6 ×106 10−18 1.2×109 4.7×107 1.4×107 10−18 4.4 ×108 4.7×107 6.7 ×106 10−19 1.2×109 5.0×107 1.4×107 10−19 4.7 ×108 5.3×107 8.3 ×106 10−20 1.3×109 5.7×107 1.4×107 10−20 6.3 ×108 5.4×107 1.8×107 TABLE I: Minimum achieved volumes in qubits-rounds for TABLE II: Minimum achieved volumes in qubits-rounds for all combinations of pin and pout of interest when using con- all combinations of pin and pout of interest when using a top catenated 15-1 state distillation. The approximate two or- levelofblockcodestatedistillationfollowedbyconcatenated ders of magnitude volume ratio of pin = 10−2 and 10−4 for 15-1 state distillation. Bold numbers indicate a transition to pout =10−20 isduetotheformerrequiringthreelevelsofdis- more levels of distillation. For pin = 10−2, two levels, one tillation of distance 13, 21 and 45 respectively, whereas the block and one 15-1, are required even for p = 10−5, with out latterrequiresjusttwolevelsofdistance7and15respectively. a transition to two levels of 15-1 at p = 10−9. For lower out Thisis directlyrelatedtothe assumptionthatthe gateerror p , initially no 15-1 distillation is required. Italicized entries in ratepg ispin/10,meaningmuchsmallerdistances,andhence are smaller than their corresponding entries in Table I and volumes,arerequiredtoachieveagivenreliability. Boldnum- Table III. bers indicate a transition to more levels of distillation. For p =10−2,twolevelsarerequiredevenforp =10−5,with in out atransitiontothreelevelsatp =10−12. Forlowerp ,only out in metricvolumeofblockcodestatedistillationis96k+216. one or two levels are required. Italicized entries are smaller We must therefore choose a top level code distance than their corresponding entries in Table II and Table III. sufficiently large to satisfy (96k + 216)P (d,p /10) < L in (cid:15)p /(1+(cid:15)). Given the absolute volume V of the block out b than pin, more state distillation is required. Our sec- codeused,andtheabsolutevolumeV15 ofeach15-1con- ond level of state distillation must have a probability catenatedstructureusedtoproduceaninputtotheblock of logical error no more than (cid:15)p/(1+(cid:15)) = 1.2×10−6, code stage, the total absolute volume assigned to each implying d = 9. The states input to the second level output will be (Vb+(3k+8)V15)/k. of distillation must have an error rate no more than The minimum absolute volume found for arbitrary k (cid:112) 3 2.4×10−6/35(1+(cid:15))=3.3×10−3. Sincethisisgreater and (cid:15) is shown in Table II. Italicized volumes are lower thanp ,nofurtherdistillationisrequired. Theabsolute than the corresponding concatenated 15-1 volumes (and in volume of the d=19 top level and 15 d=9 second level two-level block code distilled volumes to be discussed distillation structures is 3.1×107 qubits-rounds. shortly). In all cases, the volume reduction is less than a Inpractice,thecomputationofthepreviousparagraph factor of three and was typically a factor of two for the is performed for a range of values of (cid:15), and the value casesinwhichareductionwasobservedatall. Notethat leadingtominimumvolumechosen. TableIcontainsthe a reduction is observed when concatenated 15-1 distilla- minimumvolumesinqubits-roundsfortherangeofinput tion needs an additional level (bold entries in Table I). andoutputerrorratesofinterest. Ourgoalistoimprove This makes sense, as when just a little more distillation these numbers using block code state distillation. Itali- is required, it is better to use the lower overhead block cized entries indicate input-output parameters for which code approach. blockcodestatedistillationfailedtoreducetheoverhead. Continuing similarly, we constructed Table III assum- Given values of p and p , we can choose an arbi- ing two top levels of block code state distillation. We in out trary value of k and (cid:15) for a top level of block code state found the minimum volume varying (cid:15), k and k , where 1 2 distillation, and calculate the required block input er- k and k are the k values of the first and second lay- 1 2 (cid:112) ror rate p = p /(3k+1)(1+(cid:15)). Concatenated 15-1 ers of block distillation, respectively. Where further im- k out distillationwillthenbeusedtoreducep top . Thegeo- provementwasobserved,thiswastypicallyquitemodest, in k 6 p code that implements the block code state distillation in p 10−2 10−3 10−4 procedure of [23]. Every effort was made to make this out 10−5 4.8×107 1.7×106 6.2×105 topological structure as compact as possible using avail- able techniques [24]. Despite this, we found only a mod- 10−6 6.4×107 2.4×106 7.1×105 est overhead reduction, on average a factor of two to 10−7 7.4×107 4.1×106 7.6×105 three, when using block code state distillation for favor- 10−8 8.9×107 6.4×106 9.6×105 able parameters. Parameter ranges were found in which 10−9 9.8 ×107 1.1×107 1.6×106 block code state distillation lead to higher overhead. 10−10 1.1×108 1.1×107 1.7×106 Two research directions will be explored to further re- 10−11 1.3 ×108 1.2×107 2.3 ×106 duce the overhead of state distillation. Firstly, block 10−12 1.7 ×108 1.5×107 3.0×106 codes of distance higher than two, secondly, more ad- 10−13 2.2 ×108 1.8×107 5.2×106 vancedmethodsofcompressingthecomplexandextend- 10−14 3.3×108 2.4 ×107 6.4×106 able encoding circuitry of block codes. 10−15 5.8×108 2.5 ×107 6.6×106 10−16 7.4×108 2.8 ×107 7.0×106 10−17 8.1×108 3.0 ×107 8.8×106 10−18 8.3×108 3.1 ×107 1.1×107 10−19 8.5×108 3.4 ×107 1.1×107 IV. ACKNOWLEDGEMENTS 10−20 8.8×108 4.1 ×107 1.2 ×107 TABLE III: Minimum achieved volumes in qubits-rounds for AGF acknowledges support from the Australian Re- allcombinationsofp andp ofinterestwhenusingtwotop in out search Council Centre of Excellence for Quantum Com- levelsofblockcodestatedistillationfollowedbyconcatenated putation and Communication Technology (project num- 15-1 state distillation. Bold numbers indicate a transition ber CE110001027), with support from the US National to more levels of distillation. For all values of p , the first in Security Agency and the US Army Research Office un- entry corresponds to no 15-1 distillation. Italicized entries are smaller than their corresponding entries in Table I and der contract number W911NF-08-1-0527. Supported by Table II. the Intelligence Advanced Research Projects Activity (IARPA) via Department of Interior National Business CentercontractnumberD11PC20166. TheU.S.Govern- usually less than a factor of two. ment is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copy- right annotation thereon. Disclaimer: The views and III. DISCUSSION conclusionscontainedhereinarethoseoftheauthorsand should not be interpreted as necessarily representing the We have presented an explicit extendable topological official policies or endorsements, either expressed or im- structure corresponding to computation in the surface plied, of IARPA, DoI/NBC, or the U.S. Government. [1] S.BravyiandA.Kitaev,Phys.Rev.A71,022316(2005), [12] R. Raussendorf and J. Harrington, Phys. Rev. Lett. 98, quant-ph/0403025. 190504 (2007), quant-ph/0610082. [2] B.W.Reichardt,Quant.Info.Proc.4,251(2005),quant- [13] R. Raussendorf, J. Harrington, and K. Goyal, New J. ph/0411036. Phys. 9, 199 (2007), quant-ph/0703143. [3] P. W. Shor, Phys. Rev. A 52, R2493 (1995). [14] M. Ohzeki, Phys. Rev. E 80, 011141 (2009), [4] R. Laflamme, C. Miquel, J. P. Paz, and W. H. Zurek, arXiv:0903.2102. Phys. Rev. Lett. 77, 198 (1996), quant-ph/9602019. [15] H. G. Katzgraber, H. Bombin, R. S. Andrist, and [5] D. Bacon, Phys. Rev. A 73, 012340 (2006), quant- M.A.Martin-Delgado,Phys.Rev.A81,012319(2010), ph/0506023. arXiv:0910.0573. [6] E. Knill, Nature 434, 39 (2005), quant-ph/0410199. [16] H. Bombin, New J. Phys. 13, 043005 (2011), [7] K.FujiiandK.Yamamoto,Phys.Rev.A82,060301(R) arXiv:1006.5260. (2010), arXiv:1008.2048. [17] H. Bombin, Phys. Rev. A 81, 032301 (2010), [8] A. M. Steane, Proc. R. Soc. Lond. A 452, 2551 (1996), arXiv:0908.4246. quant-ph/9601029. [18] A. G. Fowler, Phys. Rev. A 83, 042310 (2011), [9] S.B.BravyiandA.Y.Kitaev,quant-ph/9811052(1998). arXiv:0806.4827. [10] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, J. [19] A. G. Fowler, M. Mariantoni, J. M. Martinis, and Math. Phys. 43, 4452 (2002), quant-ph/0110143. A. N. Cleland, Phys. Rev. A 86, 032324 (2012), [11] H. Bombin and M. A. Martin-Delgado, Phys. Rev. Lett. arXiv:1208.0928. 97, 180501 (2006), quant-ph/0605138. [20] H. Bombin and M. A. Martin-Delgado, Phys. Rev. Lett. 7 98, 160502 (2007), quant-ph/0610024. [21] N.E.BonesteelandD.P.DiVincenzo,Phys.Rev.B86, 165113 (2012), arXiv:1206.6048. [22] S. Bravyi and J. Haah, arXiv:1209.2426 (2012). [23] N. C. Jones, arXiv:1210.3388 (2012). [24] A. G. Fowler and S. J. Devitt, arXiv:1209.0510 (2012). [25] S.J.Devitt,A.G.Fowler,A.M.Stephens,A.D.Green- tree,L.C.L.Hollenberg,W.J.Munro,andK.Nemoto, New. J. Phys. 11, 083032 (2009), arXiv:0808.1782. [26] J. M. Amini, H. Uys, J. H. Wesenberg, S. Seidelin, J. Britton, J. J. Bollinger, D. Leibfried, C. Ospelkaus, A. P. VanDevender, and D. J. Wineland, New J. Phys. 12, 033031 (2010), arXiv:0909.2464. [27] N.C.Jones,R.VanMeter,A.G.Fowler,P.L.McMahon, J.Kim,T.D.Ladd,andY.Yamamoto,Phys.Rev.X2, 031007 (2012), arXiv:1010.5022. [28] M. Kumph, M. Brownnutt, and R. Blatt, New J. Phys. 13, 073043 (2011), arXiv:1103.5428. [29] A. G. Fowler, arXiv:1210.4626 (2012). [30] A. G. Fowler, A. C. Whiteside, A. L. McInnes, and A. Rabbani, Phys. Rev. X 2, 041003 (2012), arXiv:1202.6111. 8 Appendix A: Step-by-step compression FIG. 10: Depth 31 canonical surface code implementation of Fig. 3. Dark structures are called dual defects, light structures are called primal defects. The depth is defined to be the maximum left to right number of small primal cubes. All figures in this Appendix make use of implicit bridge compression [24], meaning some of the dual defects overlap but this can be shown to implement the same computation. 9 FIG.11: TheinitialtwoCNOTgatescanbeinterchangedthroughdeformationwiththelongmulti-targetCNOT.Eachofthe primaldefectshasbeenpushedinasfaraspossibleonboththeinputandoutputsidesofthecircuit,reducingthedepthto25. 10 FIG.12: EachCNOTbetweentheredandblueprimaldefectscanbeconvertedintoaprimaljunctionencircledbyadualring using Eq. 12 of [13].