# Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates

Jeongwan Haah1 and Matthew B. Hastings2,1

1Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA 98052, USA
2Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA

### Abstract

We present several different codes and protocols to distill $T$, controlled-$S$, and Toffoli (or $CCZ$) gates. One construction is based on codes that generalize the triorthogonal codes, allowing any of these gates to be induced at the logical level by transversal $T$. We present a randomized construction of generalized triorthogonal codes obtaining an asymptotic distillation efficiency $\gamma\rightarrow 1$. We also present a Reed-Muller based construction of these codes which obtains a worse $\gamma$ but performs well at small sizes. Additionally, we present protocols based on checking the stabilizers of $CCZ$ magic states at the logical level by transversal gates applied to codes; these protocols generalize the protocols of
. Several examples, including a Reed-Muller code for $T$-to-Toffoli distillation, punctured Reed-Muller codes for $T$-gate distillation, and some of the check based protocols, require a lower ratio of input gates to output gates than other known protocols at the given order of error correction for the given code size. In particular, we find a $512$ T-gate to $10$ Toffoli gate code with distance $8$ as well as triorthogonal codes with parameters $[[887,137,5]],[[912,112,6]],[[937,87,7]]$ with very low prefactors in front of the leading order error terms in those codes.

### ► References

[1] S. Bravyi and J. Haah, Magic-state distillation with low overhead,'' Physical Review A 86, 052329 (2012), 1209.2426.
https:/​/​doi.org/​10.1103/​PhysRevA.86.052329
arXiv:1209.2426

[2] J. Haah, M. B. Hastings, D. Poulin, and D. Wecker, Magic state distillation with low space overhead and optimal asymptotic input count,'' Quantum 1, 31 (2017), 1703.07847v1.
https:/​/​doi.org/​10.22331/​q-2017-10-03-31
arXiv:1703.07847v1

[3] E. Knill, Fault-tolerant postselected quantum computation: Schemes,'' (2004a), quant-ph/​0402171v1.
arXiv:quant-ph/0402171v1

[4] E. Knill, Fault-tolerant postselected quantum computation: Threshold analysis,'' (2004b), quant-ph/​0404104v1.
arXiv:quant-ph/0404104v1

[5] S. Bravyi and A. Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas,'' Phys. Rev. A 71, 022316 (2005), quant-ph/​0403025.
https:/​/​doi.org/​10.1103/​PhysRevA.71.022316
arXiv:quant-ph/0403025

[6] D. Gottesman, A class of quantum error-correcting codes saturating the quantum hamming bound,'' Phys. Rev. A 54, 1862 (1996), quant-ph/​9604038.
https:/​/​doi.org/​10.1103/​PhysRevA.54.1862
arXiv:quant-ph/9604038

[7] A. R. Calderbank, E. M. Rains, P. W. Shor, and N. J. A. Sloane, Quantum error correction and orthogonal geometry,'' Phys. Rev. Lett. 78, 405–408 (1997), quant-ph/​9605005.
https:/​/​doi.org/​10.1103/​PhysRevLett.78.405
arXiv:quant-ph/9605005

[8] T. Karzig, C. Knapp, R. M. Lutchyn, P. Bonderson, M. B. Hastings, C. Nayak, J. Alicea, K. Flensberg, S. Plugge, Y. Oreg, et al., Scalable designs for quasiparticle-poisoning-protected topological quantum computation with majorana zero modes,'' Physical Review B 95, 235305 (2017), 1610.05289.
https:/​/​doi.org/​10.1103/​PhysRevB.95.235305
arXiv:1610.05289

[9] A. M. Meier, B. Eastin, and E. Knill, Magic-state distillation with the four-qubit code,'' Quant. Inf. Comp. 13, 195 (2013), 1204.4221.
arXiv:1204.4221
http:/​/​www.rintonpress.com/​xxqic13/​qic-13-34/​0195-0209.pdf

[10] C. Jones, Multilevel distillation of magic states for quantum computing,'' Phys. Rev. A 87, 042305 (2013a), 1210.3388v2.
https:/​/​doi.org/​10.1103/​PhysRevA.87.042305
arXiv:1210.3388v2

[11] B. Eastin, Distilling one-qubit magic states into toffoli states,'' Physical Review A 87, 032321 (2013), 1212.4872.
https:/​/​doi.org/​10.1103/​PhysRevA.87.032321
arXiv:1212.4872

[12] C. Jones, Low-overhead constructions for the fault-tolerant toffoli gate,'' Physical Review A 87, 022328 (2013b), 1212.5069.
https:/​/​doi.org/​10.1103/​PhysRevA.87.022328
arXiv:1212.5069

[13] C. Jones, Composite toffoli gate with two-round error detection,'' Physical Review A 87, 052334 (2013c), 1303.6971.
https:/​/​doi.org/​10.1103/​PhysRevA.87.052334
arXiv:1303.6971

[14] E. T. Campbell and M. Howard, Unifying gate-synthesis and magic state distillation,'' Phys. Rev. Lett. 118, 060501 (2017a), 1606.01906v2.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.060501
arXiv:1606.01906v2

[15] E. T. Campbell and M. Howard, Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost,'' Physical Review A 95, 022316 (2017b), 1606.01904v3.
https:/​/​doi.org/​10.1103/​PhysRevA.95.022316
arXiv:1606.01904v3

[16] C. Jones, Distillation protocols for fourier states in quantum computing,'' Quantum Information & Computation 14, 560–576 (2014), 1303.3066.
arXiv:1303.3066

[17] A. Paetznick and B. W. Reichardt, Universal fault-tolerant quantum computation with only transversal gates and error correction,'' Phys. Rev. Lett. 111, 090505 (2013), 1304.3709v2.
https:/​/​doi.org/​10.1103/​PhysRevLett.111.090505
arXiv:1304.3709v2

[18] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation,'' Phys. Rev. A 86, 032324 (2012), 1208.0928.
https:/​/​doi.org/​10.1103/​PhysRevA.86.032324
arXiv:1208.0928

[19] R. A. Moser and G. Tardos, A constructive proof of the general lovász local lemma,'' Journal of the ACM (JACM) 57, 11 (2010), 0903.0544.
https:/​/​doi.org/​10.1145/​1667053.1667060
arXiv:0903.0544

[20] N. Alon and J. H. Spencer, The probabilistic method (John Wiley & Sons, 2004).

[21] N. Sloane and E. Berlekamp, Weight enumerator for second-order reed-muller codes,'' IEEE Transactions on Information Theory 16, 745–751 (1970).
https:/​/​doi.org/​10.1109/​TIT.1970.1054553

[22] E. R. Berlekamp and N. J. A. Sloane, Restrictions on weight distribution of reed-muller codes,'' Information and Control 14, 442–456 (1969).
https:/​/​doi.org/​10.1016/​S0019-9958(69)90150-8

[23] G. Song and A. Klappenecker, Optimal realizations of simplified toffoli gates,'' Quantum Information & Computation 4, 361–372 (2004).

[24] E. Arikan, Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,'' IEEE Transactions on Information Theory 55, 3051–3073 (2009), 0807.3917.
https:/​/​doi.org/​10.1109/​TIT.2009.2021379
arXiv:0807.3917

[25] J. M. Renes, F. Dupuis, and R. Renner, Efficient polar coding of quantum information,'' Physical Review Letters 109, 050504 (2012), 1109.3195.
https:/​/​doi.org/​10.1103/​PhysRevLett.109.050504
arXiv:1109.3195

[26] H. N. Ward, Weight polarization and divisibility,'' Discrete Mathematics 83, 315–326 (1990).
https:/​/​doi.org/​10.1016/​0012-365x(90)90015-a

[27] S. Bravyi, B. Leemhuis, and B. M. Terhal, Majorana fermion codes,'' New J.Phys. 12, 083039 (2010), 1004.3791.
https:/​/​doi.org/​10.1088/​1367-2630/​12/​8/​083039
arXiv:1004.3791

[28] M. B. Hastings, Small majorana fermion codes,'' Quantum Information & Computation 17, 1191–1205 (2017), 1703.00612.
https:/​/​doi.org/​10.26421/​QIC17.13-14
arXiv:1703.00612

[29] S. Vijay and L. Fu, Quantum error correction for complex and majorana fermion qubits,'' 1703.00459.
arXiv:1703.00459

[30] M. Grassl and T. Beth, Quantum bch codes,'' in Proceedings X. International Symposium on Theoretical Electrical Engineering, Magdeburg (1999) pp. 207–212, quant-ph/​9910060.
arXiv:quant-ph/9910060

[31] A. R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist,'' Phys. Rev. A 54, 1098–1105 (1996), quant-ph/​9512032.
https:/​/​doi.org/​10.1103/​PhysRevA.54.1098
arXiv:quant-ph/9512032

### Cited by

[1] Diego Ristè, Luke C. G. Govia, Brian Donovan, Spencer D. Fallek, William D. Kalfus, Markus Brink, Nicholas T. Bronn, and Thomas A. Ohki, "Real-time processing of stabilizer measurements in a bit-flip code", npj Quantum Information 6 1, 71 (2020).

[2] Daniel Litinski, "Magic State Distillation: Not as Costly as You Think", Quantum 3, 205 (2019).

[3] Christopher Chamberland and Andrew W. Cross, "Fault-tolerant magic state preparation with flag qubits", Quantum 3, 143 (2019).

[4] Narayanan Rengaswamy, Robert Calderbank, Michael Newman, and Henry D. Pfister, "On Optimality of CSS Codes for Transversal T ", IEEE Journal on Selected Areas in Information Theory 1 2, 499 (2020).

[5] Anirudh Krishna and Jean-Pierre Tillich, "Towards Low Overhead Magic State Distillation", Physical Review Letters 123 7, 070507 (2019).

[6] Kun Fang and Zi-Wen Liu, "No-Go Theorems for Quantum Resource Purification", Physical Review Letters 125 6, 060405 (2020).

[7] Narayanan Rengaswamy, Robert Calderbank, Michael Newman, and Henry D. Pfister, 2020 IEEE International Symposium on Information Theory (ISIT) 1891 (2020) ISBN:978-1-7281-6432-8.

[8] Ryuji Takagi and Hiroyasu Tajima, "Universal limitations on implementing resourceful unitary evolutions", Physical Review A 101 2, 022315 (2020).

[9] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Fault-tolerant quantum speedup from constant depth quantum circuits", Physical Review Research 2 3, 033444 (2020).

[10] Daniel Litinski, "A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery", Quantum 3, 128 (2019).

[11] Ilkwon Sohn, Jeongho Bang, and Jun Heo, "Dynamic Concatenation of Quantum Error Correction in Integrated Quantum Computing Architecture", Scientific Reports 9 1, 3302 (2019).

[12] Matthew B. Hastings and Jeongwan Haah, "Distillation with Sublogarithmic Overhead", Physical Review Letters 120 5, 050504 (2018).

[13] Anirudh Krishna and Jean-Pierre Tillich, "Magic state distillation with punctured polar codes", arXiv:1811.03112.

[14] Narayanan Rengaswamy, Robert Calderbank, Michael Newman, and Henry D. Pfister, "On Optimality of CSS Codes for Transversal $T$", arXiv:1910.09333.

[15] Earl T. Campbell and Mark Howard, "Magic state parity-checker with pre-distilled components", arXiv:1709.02214.

[16] Narayanan Rengaswamy, Robert Calderbank, Michael Newman, and Henry D. Pfister, "Classical Coding Problem from Transversal $T$ Gates", arXiv:2001.04887.

[17] Jeongwan Haah, "Towers of generalized divisible quantum codes", Physical Review A 97 4, 042327 (2018).

[18] Narayanan Rengaswamy, Robert Calderbank, Swanand Kadhe, and Henry D. Pfister, "Logical Clifford Synthesis for Stabilizer Codes", arXiv:1907.00310.

[19] Jeongwan Haah and Matthew B. Hastings, "Measurement sequences for magic state distillation", arXiv:2007.07929.

The above citations are from Crossref's cited-by service (last updated successfully 2020-10-23 01:56:16) and SAO/NASA ADS (last updated successfully 2020-10-23 01:56:17). The list may be incomplete as not all publishers provide suitable and complete citation data.