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] Craig Gidney and Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", arXiv:1905.09749, Quantum 5, 433 (2021).

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

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

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

[9] Jérémie Guillaud and Mazyar Mirrahimi, "Error rates and resource overheads of repetition cat qubits", Physical Review A 103 4, 042413 (2021).

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

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

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

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

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

[15] Michael E. Beverland, Aleksander Kubica, and Krysta M. Svore, "Cost of Universality: A Comparative Study of the Overhead of State Distillation and Code Switching with Color Codes", PRX Quantum 2 2, 020341 (2021).

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

[17] Andrew N. Glaudell, Neil J. Ross, and Jacob M. Taylor, "Optimal two-qubit circuits for universal fault-tolerant quantum computation", npj Quantum Information 7 1, 103 (2021).

[18] J. Eli Bourassa, Rafael N. Alexander, Michael Vasmer, Ashlesha Patil, Ilan Tzitrin, Takaya Matsuura, Daiqin Su, Ben Q. Baragiola, Saikat Guha, Guillaume Dauphinais, Krishna K. Sabapathy, Nicolas C. Menicucci, and Ish Dhand, "Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer", Quantum 5, 392 (2021).

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

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

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

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

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

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

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

[26] Sepehr Nezami and Jeongwan Haah, "Classification of Small Triorthogonal Codes", arXiv:2107.09684.

[27] Howard J. Schnitzer, "Hypergraph States in SU(N)1, N odd prime, Chern-Simons Theory", arXiv:2102.02281.

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-19 22:38:29) and SAO/NASA ADS (last updated successfully 2021-10-19 22:38:30). The list may be incomplete as not all publishers provide suitable and complete citation data.