CoChat
Sign Up
PreprintCited by 45Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum many-body systems

Time-optimal quantum computation

Open access
Fowler, Austin G.·2012·arXiv
DOI 10.48550/arxiv.1210.4626arXiv 1210.4626
Open this paper in CoChat — free accountOpen PDF

Abstract

Given any quantum error correcting code permitting universal fault-tolerant quantum computation and transversal measurement of logical X and Z, we describe how to perform time-optimal quantum computation, meaning the execution of an arbitrary Clifford circuit followed by a layer of independent T gates and any necessary feedforward measurement determined corrective S gates all in the time of a single physical measurement. We assume fast classical processing and classical communication, and argue the reasonableness of this assumption. This enables fault-tolerant quantum computation to be performed orders of magnitude faster than previously thought possible, with the execution time independent of the error correction strength.

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

DataCite · 10.48550/arxiv.1210.4626

Cites

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?

  • Ekerå and Håstad's derivatives of Shor's algorithms require fewer multiplications than Shor's original algorithms.

    “It is also reduced by using Eker˚ a and H˚ astad's derivatives [21, 23-25] of Shor's algorithms, that require fewer multiplications to be performed compared to Shor's original algorithms.”

    From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [25]

    In Time-optimal quantum computation (p. 3), Fowler discusses the time required for a factoring computation, while the references (p. 4) list Shor's original work. Our copy does not discuss Ekerå and Håstad's derivatives or compare their multiplication counts with Shor's; searches for those names and for modular-multiplication comparisons found no supporting passage. (LLM, conf=0.75)

    Experimental — accuracy not yet measured

  • Ekerå and Håstad's algorithm factors RSA integers N=pq by computing a short discrete logarithm d = log_g y ≡ p+q (mod r).

    “In [21, 23, 25], Eker˚ a and H˚ astad explain how to factor RSA integers N = pq in a different way; namely by computing a short discrete logarithm.”

    From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [25]

    The discussion of factoring in “Time-optimal quantum computation” (p. 3) estimates hardware requirements for factoring a 2000-bit integer; it does not describe a short-discrete-logarithm algorithm. Searches for Ekerå and Håstad, RSA integers, and d = log_g y found no passage in our copy addressing the attributed method. (LLM, conf=0.77)

    Experimental — accuracy not yet measured

  • To compute short logarithms in safe-prime groups, the best option is to use Ekerå-Håstad's algorithm that is specialized for this purpose.

    “To compute short logarithms in safe-prime groups, the best option is to use Eker˚ a-H˚ astad's algorithm [23, 25] that is specialized for this purpose.”

    From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [25]

    The introduction (p. 1) and summary (p. 4) discuss time-optimal fault-tolerant quantum computation, not algorithms for short logarithms in safe-prime groups. Searches for Ekerå–Håstad, short logarithms, safe primes, and discrete logarithms found no passage addressing the claim. (LLM, conf=0.78)

    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

No references could be resolved yet.

Research works printed but not linked: 28

  1. [1]P. W. Shor, in Proc. 35th Annual Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, CA, 1994), pp. 124-134, quantph/9508027.
  2. [3]V. Subramaniam and P. Ramadevi, quant-ph/0210095 (2002). · arXiv
  3. [5]B. Eastin and E. Knill, Phys. Rev. Lett. 102 , 110502 (2009), arXiv:0811.4262. · arXiv
  4. [6]R. Raussendorf, P. Sarvepalli, T.-C. Wei, and P. Haghnegahdar, EPTCS 95 , 219 (2012), arXiv:1210.0620. · arXiv
  5. [7]B. W. R. Robert K¨ onig, Greg Kuperberg, Ann. of Phys. 325 , 2707 (2010), arXiv:1002.2816. · arXiv
  6. [8]N. E. Bonesteel and D. P. DiVincenzo, Phys. Rev. B 86 , 165113 (2012), arXiv:1206.6048. · arXiv
  7. [9]A. M. Steane, Proc. R. Soc. Lond. A 452 , 2551 (1996), quant-ph/9601029. · arXiv
  8. [10]P. Aliferis, D. Gottesman, and J. Preskill, Quant. Info. Comp. 6 , 97 (2006), quant-ph/0504218. · arXiv
  9. [11]S. Bravyi and A. Kitaev, Phys. Rev. A 71 , 022316 (2005), quant-ph/0403025. · arXiv
  10. [12]B. W. Reichardt, Quant. Info. Proc. 4 , 251 (2005), quantph/0411036.
  11. [13]S. B. Bravyi and A. Y. Kitaev, quant-ph/9811052 (1998). · arXiv
  12. [14]E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Math. Phys. 43 , 4452 (2002), quant-ph/0110143. · arXiv
  13. [15]R. Raussendorf and J. Harrington, Phys. Rev. Lett. 98 , 190504 (2007), quant-ph/0610082. · arXiv
  14. [16]R. Raussendorf, J. Harrington, and K. Goyal, New J. Phys. 9 , 199 (2007), quant-ph/0703143. · arXiv
  15. [17]A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Phys. Rev. A 86 , 032324 (2012), arXiv:1208.0928. · arXiv
  16. [18]D. S. Wang, A. G. Fowler, and L. C. L. Hollenberg, Phys. Rev. A 83 , 020302(R) (2011), arXiv:1009.3686. · arXiv
  17. [19]A. G. Fowler, A. C. Whiteside, and L. C. L. Hollenberg, Phys. Rev. Lett. 108 , 180501 (2012), arXiv:1110.5133. · arXiv
  18. [20]A. G. Fowler and S. J. Devitt, arXiv:1209.0510 (2012). · arXiv
  19. [21]M. E. Amy, D. Maslov, M. Mosca, and M. Roetteler (2012), arXiv:1206.0758. · arXiv
  20. [22]P. Selinger, arXiv:1210.0974 (2012). · arXiv
  21. [23]A. Bocharov and K. M. Svore, arXiv:1206.3223 (2012). · arXiv
  22. [24]V. Kliuchnikov, D. Maslov, and M. Mosca, arXiv:1206.5236 (2012). · arXiv
  23. [25]A. G. Fowler, A. M. Stephens, and P. Groszkowski, Phys. Rev. A 80 , 052312 (2009), arXiv:0803.0272. · arXiv
  24. [28]A. G. Fowler, A. C. Whiteside, and L. C. L. Hollenberg, Phys. Rev. A 86 , 042313 (2012), arXiv:1202.5602. · arXiv
  25. [29]S. Bravyi and J. Haah, arXiv:1209.2426 (2012). · arXiv
  26. [30]N. C. Jones, arXiv:1210.3388 (2012). · arXiv
  27. [31]A. G. Fowler, S. J. Devitt, and C. Jones, arXiv:1301.7107 (2013). · arXiv
  28. [32]O. A. Mukhanov, IEEE Trans. Appl. Supercond. 21 , 760 (2011).

Cited by

Sorted by citations

Authors
Fowler, A. G.
Affiliations
The University of Melbourne (AU)
Corresponding author
Fowler, Austin G.
ORCID
Fowler, Austin G.
Venue
arXiv
Publisher
arXiv
Published
2012
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1210.4626
arXiv
1210.4626
OpenAlex
W60936899
Cited by
45
References
0
Citations by year
2026: 2 · 2025: 2 · 2024: 1 · 2023: 3 · 2022: 5 · 2021: 2 · 2020: 2 · 2019: 5 · 2018: 1 · 2017: 3 · 2016: 5 · 2015: 4 · 2014: 4 · 2013: 6
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
fault-tolerant quantum computing, quantum error-correcting codes, Clifford circuits, T-gate, execution time, classical communication

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