CoChat
Sign Up
Cited by 49Quantum Computing Algorithms and ArchitectureCoding theory and cryptographyQuantum Information and Cryptography

T-Count Optimization and Reed–Muller Codes

Open access
Amy, Matthew, Mosca, Michele·2019·IEEE Transactions on Information Theory
DOI 10.1109/tit.2019.2906374
Open this paper in CoChat — free accountOpen PDF

Abstract

In this paper, we study the close relationship between Reed-Muller codes and single-qubit phase gates from the perspective of T-count optimization. We prove that minimizing the number of T gates in an n-qubit quantum circuit over CNOT and T, together with the Clifford group powers of T, corresponds to finding a minimum distance decoding of a length 2n- 1 binary vector in the order n - 4 punctured Reed-Muller code. Moreover, we show that the problems are polynomially equivalent in the length of the code. As a consequence, we derive an algorithm for the optimization of T-count in quantum circuits based on Reed-Muller decoders, along with a new upper bound of O(n2) on the number of T gates required to implement an n-qubit unitary over CNOT and T gates. We further generalize this result to show that minimizing small angle rotations corresponds to decoding lower order binary Reed-Muller codes. In particular, we show that minimizing the number of RZ(2π/m) gates for any integer m is equivalent to minimum distance decoding in RM(n - k - 1, n)*, where k is the highest power of 2 dividing m.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/tit.2019.2906374

Cites

8 of 8 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Many algorithms try to reduce quantum circuits to the minimal number of T gates to estimate the difficulty of classically simulating a circuit.

    “For this reason, many algorithms try to reduce quantum circuits to the minimal number of T gates to give an estimation of the difficulty of classically simulating a circuit (Amy et al. , 2013; Amy and Mosca, 2019; Gosset et al. , 2013; Heyfron and Campbell, 2018; Kissinger and van de Wetering, 2019).”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Amy and Mosca, 2019

    The Related Work section (p. 2) describes substantial work on reducing T-count, and the paper presents its own T-count optimization algorithm (p. 1). But the cited passages do not say that these algorithms are used to estimate the difficulty of classically simulating a circuit; searches for classical simulation did not establish that purpose. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 30

  1. [4]M. Amy, D. Maslov, and M. Mosca, 'Polynomial-time t-depth optimization of Clifford+T circuits via matroid partitioning,' Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , vol. 33, no. 10, pp. 1476-1489, Oct 2014.
  2. [6]S. Forest, D. Gosset, V. Kliuchnikov, and D. McKinnon, 'Exact synthesis of single-qubit unitaries over clifford-cyclotomic gate sets,' Journal of Mathematical Physics , vol. 56, no. 8, pp. -, 2015. [Online]. Available: http://scitation.aip.org/content/aip/journal/jmp/56/8/10.1063/1.4927100 · DOI
  3. [8]D. Gosset, V. Kliuchnikov, M. Mosca, and V. Russo, 'An algorithm for the t-count,' Quantum Info. Comput. , vol. 14, no. 15-16, pp. 1261-1276, Nov. 2014. [Online]. Available: http://dl.acm.org/citation.cfm?id=2685179.2685180
  4. [9]P. Selinger, 'Quantum circuits of T -depth one,' Phys. Rev. A , vol. 87, p. 042302, Apr 2013. [Online]. Available: http://link.aps.org/doi/10.1103/PhysRevA.87.042302 · DOI
  5. [10]N. Abdessaied, M. Soeken, and R. Drechsler, 'Quantum circuit optimization by hadamard gate reduction,' in Reversible Computation , ser. Lecture Notes in Computer Science, S. Yamashita and S.-i. Minato, Eds. Springer International Publishing, 2014, vol. 8507, pp. 149-162. [Online]. Available: http://dx.doi.org/10.1007/978-3-319-08494-7 12 · DOI
  6. [12]V. Kliuchnikov, D. Maslov, and M. Mosca, 'Fast and efficient exact synthesis of single-qubit unitaries generated by clifford and t gates,' Quantum Info. Comput. , vol. 13, no. 7-8, pp. 607-630, Jul. 2013. [Online]. Available: http://dl.acm.org/citation.cfm?id=2535649.2535653
  7. [14]P. Selinger, 'Efficient clifford+t approximation of single-qubit operators,' Quantum Info. Comput. , vol. 15, no. 1-2, pp. 159-180, Jan. 2015. [Online]. Available: http://dl.acm.org/citation.cfm?id=2685188.2685198
  8. [15]N. J. Ross and P. Selinger, 'Optimal ancilla-free clifford+ t approximation of z-rotations,' arXiv preprint , 2014.
  9. [16]A. Paetznick and K. M. Svore, 'Repeat-until-success: Non-deterministic decomposition of single-qubit unitaries,' Quantum Info. Comput. , vol. 14, no. 15-16, pp. 1277-1301, Nov. 2014. [Online]. Available: http://dl.acm.org/citation.cfm?id=2685179.2685181
  10. [18]E. Knill, R. Laflamme, and W. Zurek, 'Threshold Accuracy for Quantum Computation,' arXiv preprint , Oct. 1996.
  11. [19]B. Zeng, A. Cross, and I. L. Chuang, 'Transversality versus universality for additive quantum codes,' IEEE Transactions on Information Theory , vol. 57, no. 9, pp. 6272-6284, Sept 2011.
  12. [20]J. T. Anderson and T. Jochym-O'Connor, 'Classification of transversal gates in qubit stabilizer codes,' arXiv preprint , 2014.
  13. [21]S. Bravyi and J. Haah, 'Magic-state distillation with low overhead,' Phys. Rev. A , vol. 86, p. 052329, Nov 2012. [Online]. Available: http://link.aps.org/doi/10.1103/PhysRevA.86.052329 · DOI
  14. [22]E. T. Campbell, H. Anwar, and D. E. Browne, 'Magic-state distillation in all prime dimensions using quantum reed-muller codes,' Phys. Rev. X , vol. 2, p. 041021, Dec 2012. [Online]. Available: http://link.aps.org/doi/10.1103/PhysRevX.2.041021 · DOI
  15. [23]A. J. Landahl and C. Cesare, 'Complex instruction set computing architecture for performing accurate quantum z rotations with less magic,' arXiv preprint , 2013.
  16. [24]M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information , ser. Cambridge Series on Information and the Natural Sciences. Cambridge University Press, 2000. [Online]. Available: http://books.google.ca/books?id=65FqEKQOfP8C
  17. [26]D. E. Muller, 'Application of boolean algebra to switching circuit design and to error detection,' Electronic Computers, Transactions of the I.R.E. Professional Group on , vol. EC-3, no. 3, pp. 6-12, Sept 1954.
  18. [27]I. Reed, 'A class of multiple-error-correcting codes and the decoding scheme,' Information Theory, Transactions of the IRE Professional Group on , vol. 4, no. 4, pp. 38-49, September 1954.
  19. [28]G. D. Cohen and S. N. Litsyn, 'On the covering radius of reed-muller codes,' Discrete Mathematics , vol. 106, pp. 147 155, 1992. [Online]. Available: http://www.sciencedirect.com/science/article/pii/0012365X9290542N
  20. [29]G. Seroussi and A. Lempel, 'Maximum likelihood decoding of certain reed - muller codes,' Information Theory, IEEE Transactions on , vol. 29, no. 3, pp. 448-450, May 1983.
  21. [31]G. Duclos-Cianci and D. Poulin, 'Reducing the quantum-computing overhead with complex gate distillation,' Phys. Rev. A , vol. 91, p. 042315, Apr 2015. [Online]. Available: http://link.aps.org/doi/10.1103/PhysRevA.91.042315 · DOI
  22. [32]I. Dumer, 'Recursive decoding and its performance for low-rate reed-muller codes,' Information Theory, IEEE Transactions on , vol. 50, no. 5, pp. 811-823, May 2004.
  23. [35]V. Vedral, A. Barenco, and A. Ekert, 'Quantum networks for elementary arithmetic operations,' Phys. Rev. A , vol. 54, pp. 147-153, Jul 1996. [Online]. Available: http://link.aps.org/doi/10.1103/PhysRevA.54.147 · DOI
  24. [36]R. Van Meter and K. M. Itoh, 'Fast quantum modular exponentiation,' Phys. Rev. A , vol. 71, p. 052320, May 2005. [Online]. Available: http://link.aps.org/doi/10.1103/PhysRevA.71.052320 · DOI · Paper page
  25. [37]T. G. Draper, S. A. Kutin, E. M. Rains, and K. M. Svore, 'A logarithmic-depth quantum carrylookahead adder,' Quantum Info. Comput. , vol. 6, no. 4, pp. 351-369, Jul. 2006. [Online]. Available: http://dl.acm.org/citation.cfm?id=2012086.2012090
  26. [38]Y. Takahashi, S. Tani, and N. Kunihiro, 'Quantum addition circuits and unbounded fan-out,' Quantum Info. Comput. , vol. 10, no. 9, pp. 872-890, Sep. 2010. [Online]. Available: http://dl.acm.org/citation.cfm?id=2011464.2011476
  27. [39]S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. Petrie Moulton, 'A new quantum ripple-carry addition circuit,' ArXiv e-prints , Oct. 2004.
  28. [40]I. L. Markov and M. Saeedi, 'Constant-optimized quantum circuits for modular multiplication and exponentiation,' Quantum Info. Comput. , vol. 12, no. 5-6, pp. 361-394, May 2012. [Online]. Available: http://dl.acm.org/citation.cfm?id=2230996.2230997
  29. [41]A. G. Fowler, S. J. Devitt, and C. Jones, 'Surface code implementation of block code state distillation,' Scientific reports , vol. 3, 2013.
  30. [42]D. Maslov, J. Mathew, D. Cheung, and D. K. Pradhan, 'An O ( m 2 )-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF(2 m ),' Quantum Info. Comput. , vol. 9, no. 7, pp. 610-621, Jul. 2009. [Online]. Available: http://dl.acm.org/citation.cfm?id=2011814.2011818

Cited by

Sorted by citations

Authors
Amy, M., & Mosca, M.
Affiliations
  • University of Waterloo (CA)
  • Perimeter Institute (CA)
ORCID
Amy, Matthew
Venue
IEEE Transactions on Information Theory
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Published
2019-08
Volume
65
Issue
8
Pages
4771-4784
ISSN
  • 0018-9448 (ISSN-L)
  • 1557-9654
DOI
10.1109/tit.2019.2906374
OpenAlex
W2308615846
Cited by
49
References
8
Citations by year
2026: 3 · 2025: 13 · 2024: 10 · 2023: 3 · 2022: 5 · 2021: 5 · 2020: 9 · 2019: 1
FWCI
2.28
Type
journal article
Language
en
Open access
Licence
Locations
  • IEEE Transactions on Information Theory (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Natural Sciences and Engineering Research Council of Canada
  • Canada’s NSERC, CIFAR, and CFI
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
Reed-Muller codes, quantum circuit synthesis, minimum distance decoding, Clifford group, polynomial equivalence, quantum error correction

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review