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.

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.

► BibTeX data

► 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] Shraddha Singh, Andrew S. Darmawan, Benjamin J. Brown, and Shruti Puri, "High-fidelity magic-state preparation with a biased-noise architecture", Physical Review A 105 5, 052410 (2022).

[3] Daniel Litinski, "Magic State Distillation: Not as Costly as You Think", Quantum 3, 205 (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", Quantum 5, 433 (2021).

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

[7] Christopher Chamberland, Kyungjoo Noh, Patricio Arrangoiz-Arriola, Earl T. Campbell, Connor T. Hann, Joseph Iverson, Harald Putterman, Thomas C. Bohdanowicz, Steven T. Flammia, Andrew Keller, Gil Refael, John Preskill, Liang Jiang, Amir H. Safavi-Naeini, Oskar Painter, and Fernando G.S.L. Brandão, "Building a Fault-Tolerant Quantum Computer Using Concatenated Cat Codes", PRX Quantum 3 1, 010329 (2022).

[8] Nick S. Blunt, Joan Camps, Ophelia Crawford, Róbert Izsák, Sebastian Leontica, Arjun Mirani, Alexandra E. Moylett, Sam A. Scivier, Christoph Sünderhauf, Patrick Schopf, Jacob M. Taylor, and Nicole Holzmann, "Perspective on the Current State-of-the-Art of Quantum Computing for Drug Discovery Applications", Journal of Chemical Theory and Computation 18 12, 7001 (2022).

[9] Christopher Chamberland and Earl T. Campbell, "Universal Quantum Computing with Twist-Free and Temporally Encoded Lattice Surgery", PRX Quantum 3 1, 010331 (2022).

[10] Xiaoning Bian and Peter Selinger, "Generators and Relations for 3-Qubit Clifford+CS Operators", Electronic Proceedings in Theoretical Computer Science 384, 114 (2023).

[11] William J. Huggins, Sam McArdle, Thomas E. O’Brien, Joonho Lee, Nicholas C. Rubin, Sergio Boixo, K. Birgitta Whaley, Ryan Babbush, and Jarrod R. McClean, "Virtual Distillation for Quantum Error Mitigation", Physical Review X 11 4, 041036 (2021).

[12] Sepehr Nezami and Jeongwan Haah, "Classification of small triorthogonal codes", Physical Review A 106 1, 012437 (2022).

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

[14] Zhenyu Cai, Adam Siegel, and Simon Benjamin, "Looped Pipelines Enabling Effective 3D Qubit Lattices in a Strictly 2D Device", PRX Quantum 4 2, 020345 (2023).

[15] Jingzhen Hu, Qingzhong Liang, and Robert Calderbank, "Designing the Quantum Channels Induced by Diagonal Gates", Quantum 6, 802 (2022).

[16] Narayanan Rengaswamy, Robert Calderbank, Swanand Kadhe, and Henry D. Pfister, "Logical Clifford Synthesis for Stabilizer Codes", IEEE Transactions on Quantum Engineering 1, 1 (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] Eesa Nikahd, Morteza Saheb Zamani, and Mehdi Sedighi, "Low-overhead code concatenation approaches for universal quantum computation", Quantum Information Processing 22 1, 73 (2023).

[20] Jingzhen Hu, Qingzhong Liang, Narayanan Rengaswamy, and Robert Calderbank, "Mitigating Coherent Noise by Balancing Weight-2 Z-Stabilizers", IEEE Transactions on Information Theory 68 3, 1795 (2022).

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

[22] Nick S. Blunt, György P. Gehér, and Alexandra E. Moylett, "Compilation of a simple chemistry application to quantum error correction primitives", Physical Review Research 6 1, 013325 (2024).

[23] Isaac H. Kim, Ye-Hua Liu, Sam Pallister, William Pol, Sam Roberts, and Eunseok Lee, "Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules", Physical Review Research 4 2, 023019 (2022).

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

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

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

[27] Akel Hashim, Rich Rines, Victory Omole, Ravi K. Naik, John Mark Kreikebaum, David I. Santiago, Frederic T. Chong, Irfan Siddiqi, and Pranav Gokhale, "Optimized SWAP networks with equivalent circuit averaging for QAOA", Physical Review Research 4 3, 033028 (2022).

[28] Jingzhen Hu, Qingzhong Liang, and Robert Calderbank, 2022 IEEE International Symposium on Information Theory (ISIT) 1229 (2022) ISBN:978-1-6654-2159-1.

[29] Michael Vasmer and Aleksander Kubica, "Morphing Quantum Codes", PRX Quantum 3 3, 030319 (2022).

[30] Héctor Bombín, Mihir Pant, Sam Roberts, and Karthik I. Seetharam, "Fault-Tolerant Postselection for Low-Overhead Magic State Preparation", PRX Quantum 5 1, 010302 (2024).

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

[32] Yiting Liu, Zhi Ma, Lan Luo, Chao Du, Yangyang Fei, Hong Wang, Qianheng Duan, and Jing Yang, "Magic state distillation and cost analysis in fault-tolerant universal quantum computation", Quantum Science and Technology 8 4, 043001 (2023).

[33] Christophe Vuillot and Nikolas P. Breuckmann, "Quantum Pin Codes", IEEE Transactions on Information Theory 68 9, 5955 (2022).

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

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

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

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

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

[39] Filipa C R Peres, Rafael Wagner, and Ernesto F Galvão, "Non-stabilizerness and entanglement from cat-state injection", New Journal of Physics 26 1, 013051 (2024).

[40] Craig Gidney and Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", arXiv:1905.09749, (2019).

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

[42] Zi-Wen Liu and Sisi Zhou, "Quantum error correction meets continuous symmetries: fundamental trade-offs and case studies", arXiv:2111.06360, (2021).

[43] Earl T. Campbell and Mark Howard, "Magic state parity-checker with pre-distilled components", Quantum 2, 56 (2018).

[44] Stergios Koutsioumpas, Darren Banfield, and Alastair Kay, "The Smallest Code with Transversal T", arXiv:2210.14066, (2022).

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

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

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

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

[49] Jingzhen Hu, Qingzhong Liang, Narayanan Rengaswamy, and Robert Calderbank, "Mitigating Coherent Noise by Balancing Weight-2 $Z$-Stabilizers", arXiv:2011.00197, (2020).

[50] Prithviraj Prabhu and Christopher Chamberland, "New magic state distillation factories optimized by temporally encoded lattice surgery", arXiv:2210.15814, (2022).

[51] Jingzhen Hu, Qingzhong Liang, and Robert Calderbank, "Divisible Codes for Quantum Computation", arXiv:2204.13176, (2022).

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

[53] Xiaoning Bian and Peter Selinger, "Generators and Relations for 3-Qubit Clifford+CS Operators", arXiv:2306.08530, (2023).

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-03-28 08:52:27) and SAO/NASA ADS (last updated successfully 2024-03-28 08:52:28). The list may be incomplete as not all publishers provide suitable and complete citation data.