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

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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.

► BibTeX data

► References

[1] S. Bravyi and J. Haah, ``Magic-state distillation with low overhead,'' Physical Review A 86, 052329 (2012), 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.

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

[4] E. Knill, ``Fault-tolerant postselected quantum computation: Threshold analysis,'' (2004b), 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.

[6] D. Gottesman, ``A class of quantum error-correcting codes saturating the quantum hamming bound,'' Phys. Rev. A 54, 1862 (1996), 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.

[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.

[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.

[10] C. Jones, ``Multilevel distillation of magic states for quantum computing,'' Phys. Rev. A 87, 042305 (2013a), 1210.3388v2.

[11] B. Eastin, ``Distilling one-qubit magic states into toffoli states,'' Physical Review A 87, 032321 (2013), 1212.4872.

[12] C. Jones, ``Low-overhead constructions for the fault-tolerant toffoli gate,'' Physical Review A 87, 022328 (2013b), 1212.5069.

[13] C. Jones, ``Composite toffoli gate with two-round error detection,'' Physical Review A 87, 052334 (2013c), 1303.6971.

[14] E. T. Campbell and M. Howard, ``Unifying gate-synthesis and magic state distillation,'' Phys. Rev. Lett. 118, 060501 (2017a), 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.

[16] C. Jones, ``Distillation protocols for fourier states in quantum computing,'' Quantum Information & Computation 14, 560–576 (2014), 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.

[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.

[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.

[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).

[22] E. R. Berlekamp and N. J. A. Sloane, ``Restrictions on weight distribution of reed-muller codes,'' Information and Control 14, 442–456 (1969).

[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.

[25] J. M. Renes, F. Dupuis, and R. Renner, ``Efficient polar coding of quantum information,'' Physical Review Letters 109, 050504 (2012), 1109.3195.

[26] H. N. Ward, ``Weight polarization and divisibility,'' Discrete Mathematics 83, 315–326 (1990).

[27] S. Bravyi, B. Leemhuis, and B. M. Terhal, ``Majorana fermion codes,'' New J.Phys. 12, 083039 (2010), 1004.3791.

[28] M. B. Hastings, ``Small majorana fermion codes,'' Quantum Information & Computation 17, 1191–1205 (2017), 1703.00612.

[29] S. Vijay and L. Fu, ``Quantum error correction for complex and majorana fermion qubits,'' 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.

[31] A. R. Calderbank and P. W. Shor, ``Good quantum error-correcting codes exist,'' Phys. Rev. A 54, 1098–1105 (1996), 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] Anirudh Krishna and Jean-Pierre Tillich, "Towards Low Overhead Magic State Distillation", Physical Review Letters 123 7, 070507 (2019).

[5] 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).

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

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

[8] Christopher Chamberland and Kyungjoo Noh, "Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits", npj Quantum Information 6 1, 91 (2020).

[9] Jeongwan Haah and Matthew B. Hastings, "Measurement sequences for magic state distillation", arXiv:2007.07929, Quantum 5, 383 (2021).

[10] 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).

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

[12] 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.

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

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

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

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

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

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2021-01-22 21:03:45) and SAO/NASA ADS (last updated successfully 2021-01-22 21:03:46). The list may be incomplete as not all publishers provide suitable and complete citation data.