# 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

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] Anirudh Krishna and Jean-Pierre Tillich, "Magic state distillation with punctured polar codes", arXiv:1811.03112 (2018).

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

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

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

The above citations are from SAO/NASA ADS (last updated 2019-02-20 15:08:24). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2019-02-20 15:08:22).