The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning
Open accessAbstract
Most work in quantum circuit optimization has been performed in isolation from the results of quantum fault-tolerance. Here we present a polynomial-time algorithm for optimizing quantum circuits that takes the actual implementation of fault-tolerant logical gates into consideration. Our algorithm resynthesizes quantum circuits composed of Clifford group and T gates, the latter being typically the most costly gate in fault-tolerant models, e.g., those based on the Steane or surface codes, with the purpose of minimizing both T-count and T-depth. A major feature of the algorithm is the ability to resynthesize circuits with ancillae at effectively no additional cost, allowing space-time trade-offs to be easily explored. The tested benchmarks show up to 65.7% reduction in T-count and up to 87.6% reduction in T-depth without ancillae, or 99.7% reduction in T-depth using ancillae.
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.
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
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 18,842
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Elementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311
Lloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088 · cited 1×
“Quantum computers have the potential to efficiently solve important computational problems, including integer factorization [29] and quantum simulation [18], for which there are no known efficient classical algorithms.”
BackgroundGottesman, D., & Chuang, I. L. (1999) · Nature · doi:10.1038/46503 · Cited by 1,860
Universal quantum computation with ideal Clifford gates and noisy ancillas
Bravyi, S., & Kitaev, A. (2005) · Physical Review A · doi:10.1103/physreva.71.022316 · Cited by 1,525 · cited 1×
“Some recent work has been done concerning minimization of T -depth [2, 28], though these previous results focus on finding small optimal two- and three-qubit circuits [2], and on classes of circuits that can be parallelized to T -depth 1 by adding ancillae [2, 28].”
ResultTwo-bit gates are universal for quantum computation
DiVincenzo, D. P. (1995) · Physical Review A · doi:10.1103/physreva.51.1015 · Cited by 1,069
Theory of fault-tolerant quantum computation
Gottesman, D. (1998) · Physical Review A · doi:10.1103/physreva.57.127 · Cited by 947
Britton, J. W., Sawyer, B. C., Keith, A. C., Wang, C.-C. J., Freericks, J. K., Uys, H., Biercuk, M. J., & Bollinger, J. J. (2012) · Nature · doi:10.1038/nature10981 · Cited by 941
Cited by
t|ket⟩: a retargetable compiler for NISQ devices
Sivarajah, S., Dilkes, S., Cowtan, A., Simmons, W., Edgington, A., & Duncan, R. (2021) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8e92 · Cited by 475
A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
Litinski, D. (2019) · Quantum · doi:10.22331/q-2019-03-05-128 · Cited by 408
Applying Grover’s Algorithm to AES: Quantum Resource Estimates
Grassl, M., Langenberg, B., Roetteler, M., & Steinwandt, R. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-29360-8_3 · Cited by 299
Challenges and Opportunities of Near-Term Quantum Computing Systems
Corcoles, A. D., Kandala, A., Javadi-Abhari, A., McClure, D. T., Cross, A. W., Temme, K., Nation, P. D., Steffen, M., & Gambetta, J. M. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2019.2954005 · Cited by 203
Maslov, D. (2016) · Physical Review A · doi:10.1103/physreva.93.022311 · Cited by 193
“We can furthermore explain how to obtain the solution with 12k − 20 T gates to implement a kcontrolled Toffoli gate using k−2 unrestricted ancilla featured in [1] without resorting to a computer optimization.”
BackgroundMethodInfluentialSelf-citation
Metadata
- Authors
- Amy, M., Maslov, D., & Mosca, M.
- Venue
- IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Published
- 2014-10
- Volume
- 33
- Issue
- 10
- Pages
- 1476-1489
- ISSN
- 0278-0070 (ISSN-L)
- 1937-4151
- OpenAlex
- W2046826122
- Cited by
- 274
- References
- 42
- FWCI
- 10.56
- Type
- journal article
- Language
- en
- Open access
- green
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning. https://app.cochat.ai/papers/10.1109/tcad.2014.2341953
- The paper
- Amy, M., Maslov, D., & Mosca, M. (2014). Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. https://doi.org/10.1109/tcad.2014.2341953
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.