I. INTRODUCTION

A. Fault tolerant quantum chemistry

When numerically simulating quantum chemistry problems, typically, a set of independent functions, known as a basis set, are introduced to describe the physical wave function of the system. This introduction does not remedy the exponential increase in parameters with system size but enables one to balance the achievable accuracy against the required computational resources. Feynman was perhaps the first to envisage a quantum computer and its application to the simulation of physics and chemistry.³³33.
R. P. Feynman, Int. J. Theor. Phys.
21, 467 (1982). https://doi.org/10.1007/BF02650179 It is now expected that quantum computers will eventually be able to perform electronic structure calculations with a quality of solution typical to the most accurate classical methods but with run times comparable to the approximate techniques, such as density functional theory.

The quantum phase estimation (QPE) algorithm generates eigenvalues for a general unitary operator, and it can be applied to quantum chemistry to find the eigenenergies of chemistry Hamiltonians to FCI (full configuration interaction, i.e., exact) precision. Unlike the variational quantum eigensolver (VQE)³⁴34.
A. Peruzzo,
J. McClean,
P. Shadbolt,
M. H. Yung,
X. Q. Zhou,
P. J. Love,
A. Aspuru-Guzik, and
J. L. O’Brien, Nature Commun.
5, 4213 (2014). https://doi.org/10.1038/ncomms5213 that involves many iterations [$\mathcal{O}(1/{ϵ}^2)$ with accuracy ϵ] of low depth circuits, the QPE algorithm requires $\mathcal{O}(1)$ iterations of a circuit with a depth scaling as $\mathcal{O}(1/ϵ)$. The large depth required in the QPE algorithm means that it will only be possible with error corrected devices because NISQ devices would lose their coherence long before the end of the circuit.

Hamiltonian simulation is used as a subroutine in the quantum phase estimation (QPE) algorithm, and it involves constructing a quantum circuit that approximates the evolution of the input state according to the Hamiltonian. Two of the main paradigms for Hamiltonian simulation are trotterization and qubitization. Qubitization^35,3635.
G. H. Low and
I. L. Chuang, Quantum
3, 163 (2019). https://doi.org/10.22331/q-2019-07-12-16336.
D. W. Berry,
C. Gidney,
M. Motta,
J. R. McClean, and
R. Babbush, Quantum
3, 208 (2019). https://doi.org/10.22331/q-2019-12-02-208 can be used to simulate the Hamiltonian evolution by using quantum signal processing,³⁷37.
G. H. Low and
I. L. Chuang, Phys. Rev. Lett.
118, 010501 (2017). https://doi.org/10.1103/PhysRevLett.118.010501 but more commonly, it is used to generate a quantum walk³⁸38.
D. Poulin,
A. Kitaev,
D. S. Steiger,
M. B. Hastings, and
M. Troyer, Phys. Rev. Lett.
121, 010501 (2018). https://doi.org/10.1103/PhysRevLett.121.010501 upon which one can directly perform phase estimation. Qubitization is perhaps the most favored method for simulating chemistry Hamiltonian dynamics because it achieves the provably optimal scaling in query complexity and approximation error albeit while requiring more logical qubits than other methods.

Previous work has investigated the potential for quantum computers to provide a quantum advantage by performing ground state energy estimations on the catalytic complex known as FeMo-co.^39–4239.
M. Reiher,
N. Wiebe,
K. M. Svore,
D. Wecker, and
M. Troyer, Proc. Natl. Acad. Sci. U. S. A.
114, 7555 (2017). https://doi.org/10.1073/pnas.161915211440.
Z. Li,
J. Li,
N. S. Dattani,
C. J. Umrigar, and
G. K. L. Chan, J. Chem. Phys.
150, 024302 (2019). https://doi.org/10.1063/1.506337641.
V. von Burg,
G. H. Low,
T. Häner,
D. S. Steiger,
M. Reiher,
M. Roetteler, and
M. Troyer, arXiv:2007.14460 (2020).42.
J. Lee,
D. W. Berry,
C. Gidney,
W. J. Huggins,
J. R. McClean,
N. Wiebe, and
R. Babbush, PRX Quantum
2, 030305 (2020). https://doi.org/10.1103/PRXQuantum.2.030305 FeMo-co is a large molecule expressed in biology, which reduces N₂ from the atmosphere, and a better understanding of this process could provide a significant commercial advantage by improving the efficiency of nitrogen fixation for the production of ammonia for fertilizer. In this work, we start our investigation with the latest logical resource requirements for simulating FeMo-co and calculate the number of physical qubits required to reach a desirable run time as a function of the code cycle time of the hardware.

B. Breaking Bitcoin’s encryption

Bitcoin, the first decentralized cryptocurrency, is continuing to grow in popularity. Bitcoin has properties that make it desirable as a hedge against inflation, for example, the rate of supply is known, decreases with time, and is entirely independent of demand. The decentralized nature of the blockchain makes it censor resistant, and it can operate in a trustless manner. There are two main ways in which a quantum computer may pose a threat to the Bitcoin network.^43,4443.
D. Aggarwal,
G. K. Brennen,
T. Lee,
M. Santha, and
M. Tomamichel, arXiv:1710.10377 (2017).44.
L. Tessler and
T. Byrnes, arXiv:1711.04235 (2017). The first and least likely is the threat to the proof of work mechanism (mining) for which a quantum computer may achieve a quadratic speedup on the hashing of the SHA256 protocol with the Grover’s algorithm.⁴⁵45.
L. K. Grover, in Proceedings of the Annual ACM Symposium on Theory of Computing Part F1294 (
ACM, 1996), pp. 212–219. The algorithmic speedup is unlikely to make up for the considerably slower clock cycle times relative to state of the art classical computing for the foreseeable future.⁴⁴44.
L. Tessler and
T. Byrnes, arXiv:1711.04235 (2017). The second and more serious threat would be an attack on the elliptic curve encryption of signatures. Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) that relies on the hardness of the Elliptic Curve Discrete Log Problem (ECDLP), and a modified version of Shor’s algorithm^46–4846.
P. W. Shor, SIAM J. Comput.
26, 1484 (1997). https://doi.org/10.1137/S009753979529317247.
T. Häner,
S. Jaques,
M. Naehrig,
M. Roetteler, and
M. Soeken, in Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) LNCS (
Springer, 2020), Vol.
12100, pp. 425–444.48.
M. Roetteler,
M. Naehrig,
K. M. Svore, and
K. Lauter, in Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) LNCS (
Springer, 2017), Vol.
10625, pp. 241–270. can provide an exponential speedup using a quantum computer for solving this problem. Bitcoin uses ECDSA to convert between the public and private keys, which are used when performing transactions. With best practices (using new addresses for each transaction), the only point at which a public key is available and relevant to a eavesdropper is after a transaction has been broadcast to the network but prior to its acceptance within the blockchain. In this window, transactions wait in the “mem pool” for an amount of time dependent on the fee paid; the time taken for this process is on average 10 min, but it can often take much longer. Gidney and Ekerå estimated that it would require 20 × 10⁶ noisy qubits and 8 h to break the 2048 Rivest-Shamir-Adleman (RSA) encryption,³¹31.
C. Gidney and
M. Ekerå, Quantum
5, 433 (2021). https://doi.org/10.22331/q-2021-04-15-433 which is of a comparable difficulty to the EC encryption of Bitcoin. The maximum acceptable run time for breaking Bitcoin’s encryption makes it particularly well suited to our investigation into the cost of parallelization and the interplay between the code cycle time and scalability, which we present in Sec. III.

In Sec. II, we introduce considerations for error correction and provide an overview of the space and time optimizations within the surface code that we make use of in this work.

II. SPACE AND TIME OPTIMIZATIONS IN THE SURFACE CODE

A. The available gate set

The surface code has transversal access to the CNOT, and the H and S gates can be realized with a low overhead using other techniques.⁵¹51.
D. Litinski and
F. von Oppen, Quantum
2, 62 (2018). https://doi.org/10.22331/q-2018-05-04-62 The T-gate is not transversal in the surface code, and it must be effectuated using methods that incur a large space-time volume overhead relative to the other gates listed here. The T gate can be constructed by consuming a magic state, $|m⟩=(|0⟩+e^{i\pi /4}|1⟩/\sqrt{2}$,⁵²52.
S. Bravyi and
A. Kitaev, Phys. Rev. A
71, 022316 (2005). https://doi.org/10.1103/PhysRevA.71.022316 where the magic state can be produced with an error proportional to the physical error, independent of the code distance.⁵³53.
D. Litinski, Quantum
3, 205 (2019). https://doi.org/10.22331/q-2019-12-02-205 To create a sufficiently high-quality magic state, a distillation protocol^54,5554.
S. Bravyi and
J. Haah, Phys. Rev. A
86, 052329 (2012). https://doi.org/10.1103/PhysRevA.86.05232955.
A. G. Fowler,
S. J. Devitt, and
C. Jones, Sci. Rep.
3, 01939 (2013). https://doi.org/10.1038/srep01939 can be used, which essentially involves converting multiple low fidelity states into fewer higher fidelity states. Due to the high time cost associated with magic state distillation (the production and consumption), we can make a simplifying assumption that the time required to perform the T-gates effectively determines the final run time of an algorithm, as the relative cost of performing the Clifford gates fault-tolerantly is negligible. Some algorithms more naturally lend themselves to being expressed in terms of Toffoli gates, and there exist distinct specialized distillation factories to produce the magic states required to effectuate both of these non-Clifford operations. A Toffoli gate can be decomposed using 4 T gates,⁵⁶56.
C. Jones, Phys. Rev. A
87, 022328 (2013). https://doi.org/10.1103/PhysRevA.87.022328 whereas the control-control-Z (CCZ) states normally produced for the Toffoli gate can be efficiently catalyzed into two T states.⁵⁷57.
C. Gidney and
A. G. Fowler, Quantum
3, 135 (2019). https://doi.org/10.22331/q-2019-04-30-135

B. Error correction and logical error rate

The efficiency of the error protection decreases as the base physical error rate approaches from below the threshold of the code (here assumed to be 1%). For feasible final resource estimates, the base physical error rate will need to be close to or below ${10}^{-3}$, where the necessary code distance is chosen based upon both the base physical error rate and the length of the desired computation. The physical error model here is the assumption that each physical operation has a probability p of also introducing a random Pauli error. The achieved gate fidelity (the go-to metric for experimentalists) cannot be directly converted with confidence to the physical error rate, without further information. The cause of the gate infidelity, where it exists on the spectrum between the two extremes of depolarizing error (decoherent noise) and unitary error (coherent noise), will determine the corresponding gate error rate. The best-case situation is the one-to-one mapping between the gate error (one-fidelity) and depolarizing error rate, and this has often been an assumption in the experimentally focused literature. A measure of gate fidelity alone cannot determine the unitarity of the noise, i.e., the relative contribution of coherent and decoherent errors. Coherent errors, such as an over rotation of an intended gate, can positively interfere with each other and, therefore, cause worse case errors than those that are decoherent. The worst case scaling of the physical error rate, p, with gate fidelity F and dimension of gate D is $p=\sqrt{D(D+1)(1-F)}$.⁵⁹59.
Y. R. Sanders,
J. J. Wallman, and
B. C. Sanders, New J. Phys.
18, 012002 (2015). https://doi.org/10.1088/1367-2630/18/1/012002 To illustrate an example of this worst case scenario on noise quality, to guarantee an error rate of below 1%, a gate fidelity of 99.9995% would be required.⁵⁹59.
Y. R. Sanders,
J. J. Wallman, and
B. C. Sanders, New J. Phys.
18, 012002 (2015). https://doi.org/10.1088/1367-2630/18/1/012002 To determine where on the unitarity spectrum, the actual hardware noise exists, protocols based on randomized bench marking can be used.^60,6160.
J. Wallman,
C. Granade,
R. Harper, and
S. T. Flammia, New J. Phys.
17, 113020 (2015). https://doi.org/10.1088/1367-2630/17/11/11302061.
S. T. Flammia and
J. J. Wallman, ACM Trans. Quantum Comput.
1, 08039 (2020). https://doi.org/10.1145/3408039 This information can then be used to estimate the base physical error rate with confidence.^59,6259.
Y. R. Sanders,
J. J. Wallman, and
B. C. Sanders, New J. Phys.
18, 012002 (2015). https://doi.org/10.1088/1367-2630/18/1/01200262.
R. Kueng,
D. M. Long,
A. C. Doherty, and
S. T. Flammia, Phys. Rev. Lett.
117, 170502 (2016). https://doi.org/10.1103/PhysRevLett.117.170502

C. Code cycle, reaction time, and measurement depth

The code cycle is the base unit of operation in the surface code, and it involves performing a full round of stabilizer measurements. As all operations in the computer are assumed to be subject to errors, including the stabilizer measurement process, the code cycle needs to be repeated d times before corrections can be applied. We will refer to the time it takes to perform these d rounds of code cycles as a “beat,” where many surface code operations will have a time cost measured in beats. A fault tolerant quantum computer using the surface code can be envisaged as partitioned into two sections: data-blocks that consume magic states to effectuate T gates for the desired algorithm and distillation-blocks that produce high fidelity magic states. Each of these constructs in the surface code consists of a number of logical qubits, sometimes referred to as tiles, and each tile contains $2d^2$ physical qubits. The data block has a size scaling with the number of abstract qubits required for the algorithm, and this then sets the minimum required number of physical qubits when paired with a single magic state factory and given the code distance.

The T (or Toffoli) gates of an algorithm can be arranged into layers of gates (measurement layers), where all of the gates within a layer could potentially be executed simultaneously. Measurement layers are sometimes instead referred to as T layers when the relevant non-Clifford gate is the T gate, and the measurement (T) depth is the number of measurement layers in the algorithm. When a magic state is consumed by the data block, a Pauli product measurement is performed to determine whether an error has occurred, so that a (Clifford) correction can be applied if required. The algorithm cannot proceed to the next measurement layer until all of the necessary corrections have been applied in the current layer, and this process requires a classical computation (decoding and feed-forward). The characteristic time cost that includes the quantum measurement, classical communication, and classical computation is referred to as the “reaction time, RT.” It is conjectured that the fastest an error-corrected quantum algorithm can run, i.e., the time optimal limit⁶³63.
A. G. Fowler, arXiv:1210.4626 (2012). is by spending only one reaction time per measurement layer, independent of code distance, and we will refer to this as reaction limited. In the case of superconducting devices that have relatively fast physical gates and measurements, the reaction time may be dominated by the classical communication and computation. A reaction time of 10 μs has been used in recent resource estimation work,³¹31.
C. Gidney and
M. Ekerå, Quantum
5, 433 (2021). https://doi.org/10.22331/q-2021-04-15-433 as compared to the 1 μs code cycle time, which requires both physical two qubit operations and measurements. In this work, we have defined the reaction time (RT) as a function of the code cycle time (CC) with $RT=(CC/4)+10\hspace{0.17em}\hspace{0.17em}\mu \mathrm{s}$ unless otherwise stated. This assumption is motivated by the fact that generally, the quantum measurement within the code cycle represents a fraction of the total time, for example, with the shuttling-based trapped ion architecture with a code cycle time of 235 μs, the quantum measurement is estimated to represent $\sim 10\%$ of that total time. We include a code cycle independent additional cost of $10\hspace{0.17em}\mu \mathrm{s}$ to represent the (somewhat) hardware independent classical processing. With our resource estimation tool, which is available upon request, one could recreate the results of this paper with a different relationship between the code cycle time and reaction time. If particular surface code set up contained only a single distillation factory, then the rate of computation would likely not be limited by the reaction time but instead by the rate of magic state production. We refer to the regime of being limited by magic state production as “tick” limited. There are then three relevant regimes for surface code strategies, which are separated by the limiting factor of computation rate. Beat limited implies that the limiting factor is the rate of magic state consumption by the data block, tick limited, the rate of magic state production by the distillation blocks, and reaction limited, where the conjectured time-optimal limit is reached, and one reaction time is spent per measurement layer.

In this work, we utilize and compare two distinct strategies of incrementally trading qubits for run-time up to the reaction limit and introduce them later in this section.

D. Distillation and topological errors

When choosing a surface code setup, one must decide upon the acceptable final success probability, where, in principle, a success probability greater than 50% would be sufficient to reach the desired precision by repeating the computation. The acceptable success probability then allows one an additional method of trading space for time, as the lower the acceptable success probability, the lower the various code distances would need to be. There are two contributions to the probability of failure: the topological error associated with the data block and the total distillation error. The topological error is the chance for at least a single logical error within the data block across the entirety of the algorithm, which can be calculated with the product of the number of logical qubits, the number of code cycles required for the algorithm, and the logical error rate, where the logical error rate is defined in Eq. (2) by the base physical error rate and the code distance on the data block. The total distillation error corresponds to the probability of at least a single faulty magic state, which is calculated by the product of the total required number of requi