Simple Algorithm
Quantum Computing · Rydberg State · 28 min

Fault-Tolerant Chemistry: Resource Estimates

What it really takes to beat classical chemistry.

"Quantum computers will simulate FeMoco" is a slogan. A resource estimate turns it into numbers: how many logical qubits, how many Toffoli gates, what code distance, how many physical qubits, how many days. Between 2017 and 2021 better algorithms cut the estimated gate counts by orders of magnitude, and the arithmetic behind those numbers is worth knowing by heart.

What you’ll learn

  • Describe the pipeline of a fault-tolerant resource estimate and explain why the Toffoli (or T) count dominates.
  • Derive the eigenphases of the qubitization walk operator and the resulting cost ≈πλ/(2ε)\approx\pi\lambda/(2\varepsilon) walk steps.
  • Explain how single factorization, double factorization and tensor hypercontraction lower λ\lambda and the cost per step.
  • Convert Toffoli counts and logical-qubit counts into code distance, physical qubits and runtime for a surface-code architecture.
  • Assess claims of chemical quantum advantage in light of initial-state overlap and classical progress.

What a resource estimate counts

On a surface-code machine, Clifford operations are comparatively cheap (lattice surgery, Pauli frame tracking), while each non-Clifford gate consumes a magic state distilled in a dedicated factory occupying many physical qubits for many code cycles. A Toffoli costs four T gates with an ancilla (seven without), or one ∣CCZ⟩\ket{\mathrm{CCZ}} state from a dedicated factory. So estimates report two headline numbers: logical qubits and Toffoli (or T) count. Everything physical follows from these plus the hardware error rate.

StageChoicesWhat it determines
Modelbasis set, active space (e.g. 54 electrons in 54 orbitals)system qubits (one per spin-orbital) and the coefficients of HH
RepresentationPauli sum, single or double factorization, tensor hypercontractionthe 1-norm λ\lambda and the cost of PREPARE and SELECT
Algorithmqubitized phase estimationabout πλ/(2ε)\pi\lambda/(2\varepsilon) walk steps
CompilationClifford + Toffoli, QROM data loadingToffoli count and logical qubits
Error correctionsurface code, magic-state factories, routingcode distance, physical qubits, wall-clock time
The pipeline of a fault-tolerant chemistry estimate. Improvements at any stage multiply through.

Qubitization: the cost is set by λ

Write the Hamiltonian as a linear combination of unitaries H=∑j=1LwjUjH=\sum_{j=1}^Lw_jU_j with wj>0w_j>0 (absorb signs into the unitaries, e.g. Pauli strings) and define the 1-norm λ=∑jwj\lambda=\sum_jw_j. Two oracles do the work:

PREP∣0⟩=∑jwjλ∣j⟩=:∣G⟩,SEL=∑j∣j⟩ ⁣⟨j∣⊗Uj.\mathrm{PREP}\ket{0}=\sum_j\sqrt{\tfrac{w_j}{\lambda}}\ket j=:\ket G,\qquad\mathrm{SEL}=\sum_j\dyad{j}\otimes U_j.

Then (⟨G∣⊗I) SEL (∣G⟩⊗I)=H/λ(\bra G\otimes\id)\,\mathrm{SEL}\,(\ket G\otimes\id)=H/\lambda: a block encoding of H/λH/\lambda.

DerivationProof: a rotation in a two-dimensional plane
  1. ∣ψk⟩=∣G⟩∣Ek⟩,Π=∣G⟩ ⁣⟨G∣⊗I,Π SEL∣ψk⟩=Ekλ∣ψk⟩\ket{\psi_k}=\ket G\ket{E_k},\qquad\Pi=\dyad G\otimes\id,\qquad\Pi\,\mathrm{SEL}\ket{\psi_k}=\tfrac{E_k}{\lambda}\ket{\psi_k}

    The block-encoding identity applied to an eigenvector.

  2. SEL∣ψk⟩=c∣ψk⟩+s∣ψk⊥⟩,c=Ekλ,s=1−c2,Π∣ψk⊥⟩=0\mathrm{SEL}\ket{\psi_k}=c\ket{\psi_k}+s\ket{\psi_k^\perp},\qquad c=\tfrac{E_k}{\lambda},\quad s=\sqrt{1-c^2},\quad\Pi\ket{\psi_k^\perp}=0

    Split SEL∣ψk⟩\mathrm{SEL}\ket{\psi_k} into its part inside and outside the image of Π\Pi.

  3. SEL∣{ψk,ψk⊥}=(css−c),R∣{ψk,ψk⊥}=(100−1)\mathrm{SEL}\big|_{\{\psi_k,\psi_k^\perp\}}=\begin{pmatrix}c&s\\s&-c\end{pmatrix},\qquad R\big|_{\{\psi_k,\psi_k^\perp\}}=\begin{pmatrix}1&0\\0&-1\end{pmatrix}

    SEL\mathrm{SEL} is Hermitian and unitary, so on this plane it is a reflection; RR fixes ∣ψk⟩\ket{\psi_k} and flips ∣ψk⊥⟩\ket{\psi_k^\perp}.

  4. W∣{ψk,ψk⊥}=(cs−sc),eigenvalues c±is=e±iarccos⁡(Ek/λ)■W\big|_{\{\psi_k,\psi_k^\perp\}}=\begin{pmatrix}c&s\\-s&c\end{pmatrix},\qquad\text{eigenvalues } c\pm is=e^{\pm i\arccos(E_k/\lambda)}\qquad\blacksquare

    Two reflections make a rotation, exactly as in Grover's algorithm. The energy is encoded in the rotation angle θk=arccos⁡(Ek/λ)\theta_k=\arccos(E_k/\lambda).

  5. δE=λsin⁡θ δθ≤λ δθ ⇒ Nwalk≈πλ2ε\delta E=\lambda\sin\theta\,\delta\theta\le\lambda\,\delta\theta\ \Rightarrow\ N_{\text{walk}}\approx\frac{\pi\lambda}{2\varepsilon}

    Phase estimation of θ\theta to precision ε/λ\varepsilon/\lambda needs O(λ/ε)\order{\lambda/\varepsilon} applications of WW; with the standard Heisenberg-limited variant the count is about πλ/(2ε)\pi\lambda/(2\varepsilon) (Babbush et al. 2018).

Predict before you look

Take a Hamiltonian with λ=100\lambda=100 hartree and a target precision of ε=1.6\varepsilon=1.6 mHa. About how many walk steps (in thousands) does qubitized phase estimation need?

Show the answer

98 thousand

πλ/(2ε)=π×100/(2×0.0016)≈9.8×104\pi\lambda/(2\varepsilon)=\pi\times100/(2\times0.0016)\approx9.8\times10^4. Multiply by the Toffoli cost of one walk step, typically thousands to tens of thousands for large active spaces, and you land between 10810^8 and 101010^{10} Toffolis. Halving λ\lambda halves the runtime.

RepresentationIdeaEffect
Pauli (sparse) LCUH=∑jcjPjH=\sum_jc_jP_j with O(M4)\order{M^4} termssimple; large λ\lambda and costly PREPARE
Single factorizationCholesky / density fitting: V=∑ℓ(∑pqLpqℓap†aq)2V=\sum_{\ell}\bigl(\sum_{pq}L^{\ell}_{pq}a_p^\dagger a_q\bigr)^2, rank O(M)\order{M} in practicefewer data to load
Double factorizationdiagonalize each one-body factor: ∑ℓUℓ(∑pfpℓnp)2Uℓ†\sum_\ell U_\ell\bigl(\sum_p f^\ell_p n_p\bigr)^2U_\ell^\daggerlower λ\lambda; orbital rotations via Givens circuits
Tensor hypercontractionVpqrs≈∑μνχpμχqμ Zμν χrνχsνV_{pqrs}\approx\sum_{\mu\nu}\chi^\mu_p\chi^\mu_q\,Z_{\mu\nu}\,\chi^\nu_r\chi^\nu_slowest published Toffoli counts for FeMoco (Lee et al. 2021)
Factorizations of the two-electron tensor VV trade classical preprocessing for smaller λ\lambda and cheaper oracles. QROM-based data loading makes PREPARE cost scale with the amount of data, so compression pays twice.

From logical to physical

A standard heuristic for the surface code at physical error rate pp below the threshold pth≈10−2p_{\text{th}}\approx10^{-2}: the logical error per logical qubit per code cycle is

pL(d)≈A(ppth)(d+1)/2,A≈0.1,p_L(d)\approx A\left(\frac{p}{p_{\text{th}}}\right)^{(d+1)/2},\qquad A\approx0.1,

and a distance-dd patch uses about 2d22d^2 physical qubits. The whole computation must finish with total failure probability of order a percent.

DerivationWorked estimate: 10¹⁰ Toffolis on 2000 logical qubits
  1. T≈NToff tToff=1010×25 μs=2.5×105 s≈3 daysT\approx N_{\text{Toff}}\,t_{\text{Toff}}=10^{10}\times25\,\mu\text{s}=2.5\times10^5\,\text{s}\approx3\ \text{days}

    Assume 1 μs code cycles and Toffolis consumed one after another, each taking about 25 cycles (the order of the code distance).

  2. V=NL⋅Ttcycle=2×103×2.5×1011=5×1014 logical-qubit cyclesV=N_L\cdot\frac{T}{t_{\text{cycle}}}=2\times10^3\times2.5\times10^{11}=5\times10^{14}\ \text{logical-qubit cycles}

    The spacetime volume that must survive.

  3. V pL≤10−2 ⇒ pL≤2×10−17V\,p_L\le10^{-2}\ \Rightarrow\ p_L\le2\times10^{-17}

    Total failure probability about 1%.

  4. 0.1×10−(d+1)/2≤2×10−17 ⇒ d+12≥15.7 ⇒ d=310.1\times10^{-(d+1)/2}\le2\times10^{-17}\ \Rightarrow\ \tfrac{d+1}{2}\ge15.7\ \Rightarrow\ d=31

    At p=10−3p=10^{-3}, so p/pth=0.1p/p_{\text{th}}=0.1. Distances are odd.

  5. Nphys≈NL⋅2d2=2000×1922≈3.8×106 (+ routing and factories)N_{\text{phys}}\approx N_L\cdot2d^2=2000\times1922\approx3.8\times10^6\ (+\ \text{routing and factories})

    Several million physical qubits for a few days: the same ballpark as published FeMoco estimates, which report a few million physical qubits and runtimes of days under similar assumptions (Lee et al. 2021).

Predict before you look

Same model with p/pth=0.1p/p_{\text{th}}=0.1 and A=0.1A=0.1. Which (odd) code distance first achieves pL≤10−15p_L\le10^{-15}?

Show the answer

27

0.1×10−(d+1)/2≤10−150.1\times10^{-(d+1)/2}\le10^{-15} requires (d+1)/2≥14(d+1)/2\ge14, so d=27d=27, about 2⋅272≈14602\cdot27^2\approx1460 physical qubits per logical qubit. Each extra factor of 10 in required reliability costs only 2 in distance: the exponential suppression that makes fault tolerance viable.

When does quantum actually win?

The overlap is where the debate lives. For LL weakly coupled fragments, a product trial state with overlap γ<1\gamma<1 per fragment has total overlap γL\gamma^L, exponentially small in system size (an orthogonality catastrophe). Lee et al. (2023) argued that in the regimes where a classically computable trial state has good overlap, classical heuristics also tend to work, and found no conclusive evidence of exponential advantage for ground-state chemistry across the systems they examined, while leaving room for large polynomial speedups.

The time scale matters too. Babbush et al. (2021) estimated that each error-corrected non-Clifford operation runs many orders of magnitude slower than a classical operation, so quadratic speedups need impractically long runs to pay off. Chemistry is attractive precisely because its speedups, where they exist, are much larger than quadratic.

Think first A press release says a quantum algorithm needs "only 4,000 qubits" for a chemistry problem. What should you ask?

Logical or physical? At p≈10−3p\approx10^{-3} each logical qubit costs on the order of 10310^3 physical qubits, plus factories and routing. Also ask: what Toffoli count and runtime, what precision ε\varepsilon, what active space and basis, what trial state and overlap, and how the result compares with the best classical method (DMRG, coupled cluster, AFQMC) on the same model.

Key takeaways

  • Fault-tolerant estimates headline logical qubits and Toffoli/T count; magic-state distillation makes non-Clifford gates the dominant cost.
  • Qubitization turns a block encoding of H/λH/\lambda into a walk with eigenphases ±arccos⁡(Ek/λ)\pm\arccos(E_k/\lambda); phase estimation then needs about πλ/(2ε)\pi\lambda/(2\varepsilon) steps, so λ\lambda is the key figure of merit.
  • Single and double factorization and tensor hypercontraction cut λ\lambda and the cost per step, lowering FeMoco-class estimates from the 2017 Trotter numbers to roughly 10910^9–101010^{10} Toffolis.
  • Surface-code arithmetic (pL≈A(p/pth)(d+1)/2p_L\approx A(p/p_{\text{th}})^{(d+1)/2}, ∼2d2\sim2d^2 qubits per patch) turns that into millions of physical qubits and days of runtime at p≈10−3p\approx10^{-3}.
  • Advantage hinges on trial-state overlap and on classical competition; the strongest cases have speedups far larger than quadratic.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In qubitized phase estimation, the number of walk steps for precision ε\varepsilon is about πλ/(2ε)\pi\lambda/(2\varepsilon). What is λ\lambda?

  1. The spectral norm ∥H∥\norm{H}
  2. The 1-norm ∑jwj\sum_jw_j of the LCU coefficients
  3. The number of terms LL
  4. The spectral gap E1−E0E_1-E_0
Show the answer

B. The 1-norm ∑jwj\sum_jw_j of the LCU coefficients

The block encoding represents H/λH/\lambda with λ=∑jwj≥∥H∥\lambda=\sum_jw_j\ge\norm H. The walk encodes arccos⁡(E/λ)\arccos(E/\lambda), so energy resolution ε\varepsilon needs angle resolution ε/λ\varepsilon/\lambda. Factorizations aim to shrink λ\lambda toward ∥H∥\norm H.

Question 2

With SEL2=I\mathrm{SEL}^2=\id, what are the eigenvalues of the qubitization walk W=R⋅SELW=R\cdot\mathrm{SEL} on the invariant plane associated with H∣Ek⟩=Ek∣Ek⟩H\ket{E_k}=E_k\ket{E_k}?

  1. e±iEke^{\pm iE_k}
  2. e−iEk/λe^{-iE_k/\lambda}
  3. ±Ek/λ\pm E_k/\lambda
  4. e±iarccos⁡(Ek/λ)e^{\pm i\arccos(E_k/\lambda)}
Show the answer

D. e±iarccos⁡(Ek/λ)e^{\pm i\arccos(E_k/\lambda)}

On the plane, SEL\mathrm{SEL} and RR are reflections, and their product is a rotation by θk=arccos⁡(Ek/λ)\theta_k=\arccos(E_k/\lambda), with eigenvalues e±iθke^{\pm i\theta_k}.

Question 3

Why do fault-tolerant chemistry estimates headline the Toffoli (or T) count rather than the CNOT count?

  1. Non-Clifford gates require magic-state distillation, which dominates the spacetime cost of the computation
  2. CNOTs cannot be performed on surface-code qubits
  3. Toffolis are needed only for the QFT
  4. CNOT counts are always smaller than Toffoli counts
Show the answer

A. Non-Clifford gates require magic-state distillation, which dominates the spacetime cost of the computation

In the surface code, Clifford gates are implemented by lattice surgery or tracked in software, while each non-Clifford gate consumes a distilled magic state from a large factory. Toffoli or T count is therefore the best single proxy for runtime and footprint.

Question 4

With pL≈0.1 (p/pth)(d+1)/2p_L\approx0.1\,(p/p_{\text{th}})^{(d+1)/2}, pth=10−2p_{\text{th}}=10^{-2} and a target pL=10−15p_L=10^{-15}, how does the required odd distance change if the physical error rate improves from 10−310^{-3} to 5×10−45\times10^{-4}?

  1. From 27 to 25
  2. From 27 to 13
  3. From 27 to 21
  4. It does not change
Show the answer

C. From 27 to 21

At p/pth=0.1p/p_{\text{th}}=0.1: (d+1)/2≥14(d+1)/2\ge14, so d=27d=27. At 0.050.05: 0.05x≤10−140.05^{x}\le10^{-14} needs x≥14/log⁡1020≈10.8x\ge14/\log_{10}20\approx10.8, so x=11x=11 and d=21d=21. Physical qubits per logical patch drop from about 1460 to about 880: better hardware compounds.

Further reading

  • M. Reiher, N. Wiebe, K. M. Svore, D. Wecker & M. Troyer, "Elucidating reaction mechanisms on quantum computers", PNAS 114, 7555 (2017).
  • G. H. Low & I. L. Chuang, "Hamiltonian simulation by qubitization", Quantum 3, 163 (2019).
  • V. von Burg, G. H. Low, T. Häner, D. S. Steiger, M. Reiher, M. Roetteler & M. Troyer, "Quantum computing enhanced computational catalysis", Phys. Rev. Research 3, 033055 (2021).
  • J. Lee, D. W. Berry, C. Gidney, W. J. Huggins, J. R. McClean, N. Wiebe & R. Babbush, "Even more efficient quantum computations of chemistry through tensor hypercontraction", PRX Quantum 2, 030305 (2021).
  • S. Lee et al., "Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry", Nat. Commun. 14, 1952 (2023).