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

full text pdf

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 (beta)

Crossref's cited-by service has no data on citing works. Unfortunately not all publishers provide suitable citation data.