The DOI matches its DataCite record.
An algorithm for the T-count
Open accessAbstract
We consider quantum circuits composed of Clifford and T gates. In this context the T gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an n-qubit unitary U we are interested in computing a circuit that implements it using the minimum possible number of T gates (called the T-count of U). A related task is to decide if the T-count of U is less than or equal to m; we consider this problem as a function of N=2^n and m. We provide a classical algorithm which solves it using time and space both upper bounded as O(N^m poly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 T gates. This implies that the known 7 T gate circuits for these gates are T-optimal. We also provide a simple expression for the T-count of single-qubit unitaries.
Overview
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.
Integrity signals
Registry
Cites
Statistics
Verification
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.
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 Gosset et al., 2013
The introduction (p. 1) and COUNT-T discussion (p. 2) describe algorithms for finding the minimum T-count and note that Clifford-only circuits are classically simulable. But the paper motivates minimizing T gates by their cost in fault-tolerant computation; it does not say the algorithms do so to estimate the difficulty of classical simulation. (LLM, conf=0.86)
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.
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 10
- [1][1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A , 70(5):052328, 2004. -
- [2][2] M. Amy, D. Maslov, and M. Mosca. Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning. e-print arXiv: 1303.2042 , March 2013. - · arXiv
- [3][3] Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , 32:818-830, 2013. -
- [4][4] A. R. Calderbank, E. M Rains, P. W. Shor, and N. J. A. Sloane. Quantum Error Correction via Codes over GF(4). eprint arXiv:quant-ph/9608006 , August 1996. - · arXiv
- [5][5] Brett Giles and Peter Selinger. Exact synthesis of multiqubit clifford+ T circuits. Physical Review A , 87(3):032332, 2013. -
- [6][6] D. Gottesman. The Heisenberg Representation of Quantum Computers. eprint arXiv:quant-ph/9807006 , July 1998. - · arXiv
- [7][7] C. Jones. Low-overhead constructions for the fault-tolerant Toffoli gate. Physical Review A , 87(2):022328, February 2013. -
- [8][8] Vadym Kliuchnikov. Synthesis of unitaries with clifford+T circuits. eprint arXiv: 1306.3200 , 2013. - · arXiv
- [9][9] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Fast and efficient exact synthesis of single qubit unitaries generated by clifford and T gates. eprint arXiv: 1206.5236 , 2013. - · arXiv
- [10][10] V. Veitch, S. A. Hamed Mousavian, D. Gottesman, and J. Emerson. The Resource Theory of Stabilizer Computation. e-print arXiv: 1307.7171 , July 2013. · arXiv
Cited by
Sorted by citations
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
Metadata
- Authors
- Gosset, D., Kliuchnikov, V., Mosca, M., & Russo, V.
- Affiliations
- University of Waterloo (CA)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2013
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1308.4134
- OpenAlex
- W2950042952
- Cited by
- 32
- References
- 0
- Citations by year
- 2025: 1 · 2024: 6 · 2023: 3 · 2022: 3 · 2021: 3 · 2020: 1 · 2019: 5 · 2018: 3 · 2017: 1 · 2015: 1 · 2014: 2 · 2013: 3
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Canadian Institute for Advanced Research
- Government of Canada
- Mitacs
- Institut Périmètre de physique théorique
- Natural Sciences and Engineering Research Council of Canada
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- T-count, T-gate, Clifford+T circuits, quantum circuit synthesis, Toffoli gate, Fredkin gate, fault-tolerant quantum computing, classical algorithms
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
