The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Low-overhead constructions for the fault-tolerant Toffoli gate
Open accessAbstract
We present two constructions for the Toffoli gate which substantially reduce resource costs in fault-tolerant quantum computing. The first contribution is a Toffoli gate requiring Clifford operations plus only four $T=\mathrm{exp}(i\ensuremath{\pi}{\ensuremath{\sigma}}^{z}/8)$ gates, whereas conventional circuits require seven $T$ gates. An extension of this result is that adding $n$ control inputs to a controlled gate requires $4n$ $T$ gates, whereas the best prior result was $8n$. The second contribution is a quantum circuit for the Toffoli gate which can detect a single ${\ensuremath{\sigma}}^{z}$ error occurring with probability $p$ in any one of eight $T$ gates required to produce the Toffoli gate. By postselecting circuits that did not detect an error, the posterior error probability is suppressed to lowest order from $4p$ (or $7p$, without the first contribution) to $28{p}^{2}$ for this enhanced construction. In fault-tolerant quantum computing, this construction can reduce the overhead for producing logical Toffoli gates by an order of magnitude.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
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
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059 · cited 1×
“Additionally, the state-distillation sub-circuits for the error-detecting Toffoli gate can use weaker error correction ( i.e. lower code distance, by about a factor of two) than the same the simple Toffoli, which translates to qubits and gates at the hardware level [22].”
MethodGottesman, 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 2×
“[12] Sergey Bravyi and Alexei Kitaev, “Universal quantum computation with ideal clifford gates and noisy ancillas,” Phys.”
BackgroundPreskill, J. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0167 · Cited by 994
A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits
Amy, M., Maslov, D., Mosca, M., & Roetteler, M. (2013) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2013.2244643 · Cited by 549 · cited 1×
“Amy et al. studied classical search methods for decomposing gates like Toffoli into fault-tolerant primitives [17], and Selinger investigated circuit constructions with particular emphasis on T -gate count and depth, where the latter metric allows parallel T gates on different qubits [18].”
MethodHigh-threshold universal quantum computation on the surface code
Fowler, A. G., Stephens, A. M., & Groszkowski, P. (2009) · Physical Review A · doi:10.1103/physreva.80.052312 · Cited by 486 · cited 1×
“In most quantum codes, including the surface code [21], non-Clifford gates are produced using an ancilla state that is injected into the circuit [2, 20].”
BackgroundLayered architecture for quantum computing
Jones, N. C., Van Meter, R., Fowler, A. G., McMahon, P. L., Kim, J., Ladd, T. D., & Yamamoto, Y. (2012) · Physical Review X · doi:10.1103/physrevx.2.031007 · Cited by 332 · cited 3×
“The most nettlesome of these is the T = exp( iπσ z / 8) gate, which is much more expensive in both time and space resources to produce [3, 4, 11–16]; notably, the Toffoli circuit in Ref.”
Background
Cited by
Majorana zero modes and topological quantum computation
Sarma, S. D., Freedman, M., & Nayak, C. (2015) · npj Quantum Information · doi:10.1038/npjqi.2015.1 · Cited by 1,180
Roads towards fault-tolerant universal quantum computation
Campbell, E. T., Terhal, B. M., & Vuillot, C. (2017) · Nature · doi:10.1038/nature23460 · Cited by 596
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
Application of a Resource Theory for Magic States to Fault-Tolerant Quantum Computing
Howard, M., & Campbell, E. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.090501 · Cited by 387
Simulation of quantum circuits by low-rank stabilizer decompositions
Bravyi, S., Browne, D., Calpin, P., Campbell, E., Gosset, D., & Howard, M. (2019) · Quantum · doi:10.22331/q-2019-09-02-181 · Cited by 302
“This regime may be important for verification of first fault-tolerant quantum circuits where logical nonClifford gates are expected to be scarce due to their high implementation cost [23, 34].”
BackgroundApplying 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
Building a Fault-Tolerant Quantum Computer Using Concatenated Cat Codes
Chamberland, C., Noh, K., Arrangoiz-Arriola, P., Campbell, E. T., Hann, C. T., Iverson, J., Putterman, H., Bohdanowicz, T. C., Flammia, S. T., Keller, A., et al. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010329 · Cited by 281
Halving the cost of quantum addition
Gidney, C. (2018) · Quantum · doi:10.22331/q-2018-06-18-74 · Cited by 279
“This T-count can be achieved either by applying the ancilla-and-fixup construction from [11] to each individual Toffoli gate, or by noting that all but one of the adder’s Toffoli gates appear in compute/uncompute pairs and then applying the matched-phase-error construction from [3, 14] to each pair.”
MethodInfluentialImplementing Grover Oracles for Quantum Key Search on AES and LowMC
Jaques, S., Naehrig, M., Roetteler, M., & Virdia, F. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-45724-2_10 · Cited by 234
Magic State Distillation: Not as Costly as You Think
Litinski, D. (2019) · Quantum · doi:10.22331/q-2019-12-02-205 · Cited by 220
Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation
Babbush, R., McClean, J., Wecker, D., Aspuru-Guzik, A., & Wiebe, N. (2015) · Physical Review A · doi:10.1103/physreva.91.022311 · Cited by 199
Quantum computation with realistic magic-state factories
O'Gorman, J., & Campbell, E. T. (2017) · Physical Review A · doi:10.1103/physreva.95.032338 · Cited by 158
Efficient magic state factories with a catalyzed | C C Z ⟩ to 2 | T ⟩ transformation
Gidney, C., & Fowler, A. G. (2019) · Quantum · doi:10.22331/q-2019-04-30-135 · Cited by 152
Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage
Babbush, R., McClean, J. R., Newman, M., Gidney, C., Boixo, S., & Neven, H. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.010103 · Cited by 148
Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits
Bocharov, A., Roetteler, M., & Svore, K. M. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.080502 · Cited by 142
Extracting Success from IBM’s 20-Qubit Machines Using Error-Aware Compilation
Nishio, S., Pan, Y., Satoh, T., Amano, H., & Meter, R. V. (2020) · ACM Journal on Emerging Technologies in Computing Systems · doi:10.1145/3386162 · Cited by 114
Codes and Protocols for Distilling T , controlled- S , and Toffoli Gates
Haah, J., & Hastings, M. B. (2018) · Quantum · doi:10.22331/q-2018-06-07-71 · Cited by 79
“It requires[12, 23] 4 high-quality T -gates to produce a single high-quality CCZ state, so this protocol’s efficiency is comparable, if the goal is to produce CCZ states, to a protocol that uses only 85.”
MethodInfluentialImproved Quantum Circuits for Elliptic Curve Discrete Logarithms
Häner, T., Jaques, S., Naehrig, M., Roetteler, M., & Soeken, M. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-44223-1_23 · Cited by 76
Early fault-tolerant simulations of the Hubbard model
Campbell, E. T. (2022) · Quantum Science and Technology · doi:10.1088/2058-9565/ac3110 · Cited by 81
ZX-calculus for the working quantum computer scientist
van de Wetering, J. (2020) · arXiv · doi:10.48550/arxiv.2012.13966 · Cited by 68
Vasmer, M., & Kubica, A. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.030319 · Cited by 39
“One option for preparing |CCZ〉 states is to use the circuit of Jones [40], which requires four |T 〉 states to produce a |CCZ〉 state.”
BackgroundMethodInfluentialQuantum computation of eigenvalues within target intervals
Jensen, P. W. K., Kristensen, L. B., Kottmann, J. S., & Aspuru-Guzik, A. (2021) · Quantum Science and Technology · doi:10.1088/2058-9565/abc096 · Cited by 13
Flexible layout of surface code computations using AutoCCZ states
Gidney, C., & Fowler, A. G. (2019) · arXiv · doi:10.48550/arxiv.1905.08916 · Cited by 12
How to factor 2048 bit RSA integers with less than a million noisy qubits
Gidney, C. (2025) · arXiv · Cited by 7
“Since the magic state cultivation targets a logical error rate of 10 − 7 and 8T-to-CCZ distillation has an error suppression of 28 p 2 [Jon13], the distilled CCZ states will have a logical error rate of 28 · (10 − 7 ) 2 10 − 12 .”
Quantum Circuits for Functionally Controlled NOT Gates
Soeken, M., & Roetteler, M. (2020) · 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00052 · Cited by 4
Metadata
- Authors
- Jones, C.
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2013-02-20
- Volume
- 87
- Issue
- 2
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W2343247541
- Cited by
- 204
- References
- 12
- FWCI
- 11.04
- 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
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.