Fault-tolerant quantum computation cannot be achieved with constant spacetime overhead

Kishor Bharti; Tobias Haug; Andrew Tanggara

Source-linked AI summary

Fault-tolerant quantum computation cannot be achieved with constant spacetime overhead

Kishor Bharti, Tobias Haug, Andrew Tanggara

arXiv:2608.26272v1Aug 26, 2026quant-phcs.IT

TL;DR

Whether fault-tolerant quantum computation can achieve constant cumulative spacetime overhead remains unresolved. This paper proves a logarithmic lower bound even for quantum memories, while showing the cost can be amortized across sufficiently wide computations.

Problem
Whether cumulative spacetime overhead can remain constant, despite progress toward low space and time overheads, has remained unclear.
Method
The paper combines adaptive lower bounds under erasure and general noise with positive-rate CSS constructions and circuit-size bounds for spacetime codes.
Results
Fault tolerance has an unavoidable logarithmically growing relative spacetime overhead for fixed logical width, while sufficiently wide computations can retain constant relative overhead.
Takeaways & Limitations
Reliability costs can be amortized across space but cannot be eliminated, making width–duration trade-offs central to fault-tolerant design.
Takeaways & Limitations
The bounds must be extended to realistic architectures involving locality, decoding, communication, and non-Clifford resource preparation.

Abstract

from arXiv · show

The threshold theorem states that quantum computations can be made reliable below a physical error threshold, at the cost of additional physical qubits and circuit depth. Recent work has reduced these space and time overheads to polylogarithmic or nearly logarithmic scalings, but whether the cumulative spacetime overhead can be constant has remained unclear. Here, we show that even for the simplest task of preserving quantum information in a quantum memory, under an optimistic noise model and allowing general adaptive protocols, there is an unavoidable logarithmic contribution to the cumulative spacetime overhead. This additional cost can nevertheless be shared among many logical qubits, so sufficiently wide computations, including standard implementations of Shor's algorithm, may still achieve constant relative overhead. We further give a positive-rate CSS code construction that attains the memory bound, identify sufficient conditions under which the same scaling extends from quantum memory to fault-tolerant circuit implementations, and derive circuit-size bounds for subsystem spacetime codes. Our work establishes fundamental limits on the resources required for quantum fault tolerance.

I. CIRCUIT-SIZE BOUNDS FOR ERASURE NOISE … IV. DISCUSSION

The paper establishes logarithmic cumulative spacetime costs for reliable quantum storage, while showing that sufficiently wide computations can amortize this cost to achieve constant relative overhead. Conditional circuit constructions and subsystem spacetime-code bounds extend these conclusions beyond the memory setting.

I. CIRCUIT-SIZE BOUNDS FOR ERASURE NOISE: Cpath ≥ SK, and combining this dimension bound with erasure-reliability inequalities yields the adaptive memory lower bound in Theorem 1.The argument applies to worst-case realizable measurement records under independent erasure noise and ideal recovery.
I. CIRCUIT-SIZE BOUNDS FOR ERASURE NOISE: A positive-rate CSS construction uses distance linear in block length and Chernoff suppression of uncorrectable erasures to attain the memory scaling for p < δGV.The stated threshold parameter is δGV ≃ 0.1100.
I. CIRCUIT-SIZE BOUNDS FOR ERASURE NOISE: The reliability term dominates for K = o(log(S/ε)), is comparable at K = Θ(log(S/ε)), and is lower order for K = ω(log(S/ε)).Bounded relative overhead therefore holds already for K = Ω(log(S/ε)), with the extra locations distributed among logical qubits.
II. CIRCUIT-LEVEL UPPER BOUND: Under positive-rate code and constant-size logical-layer gadget assumptions, an ideal circuit of width K and depth T admits a conditional fault-tolerant implementation with a stated physical-size upper bound.The assumptions include code block lengths within a constant factor of sufficiently large targets and gadgets using at most cqN qubits for at most ct time steps.
II. CIRCUIT-LEVEL UPPER BOUND: O(1 + log(T/ε)/K) is the relative overhead obtained by choosing N = O(K + log(T/ε)) and using O(N) physical qubits per logical layer.The total circuit size is O(TN), while telescoping bounds the total error by TAe−βN.
III. SUBSYSTEM SPACETIME-CODE BOUNDS: Vanishing logical Pauli error requires growing subsystem spacetime distance and growing absolute redundancy under the stated full-support product-Pauli noise assumptions.The bound applies to exact binary linear subsystem spacetime-code descriptions with selected fault coordinates and dressed distance.
IV. DISCUSSION: For fixed logical width, maintaining reliability over longer durations causes logarithmically growing relative spacetime overhead, but sufficiently wide computations can retain constant relative overhead.The same reliability cost is attained for independent erasure noise by a positive-rate CSS construction with ideal recovery.

METHODS … 1. States and channels

The methods define adaptive memory and circuit-size models, establish erasure-noise lower bounds, and construct CSS-code and gadget-based upper bounds. They also specify subsystem spacetime-code bounds and the channel-distance tools used throughout.

A. Memory model and error criterion: Adaptive protocols select each complete physical register from prior measurement records, while only systems present at a modeled time step count as storage locations.Ideal control may measure, discard, reset, or introduce quantum systems after noise; classical records are excluded from quantum circuit size.
A. Memory model and error criterion: A storage-location lower bound also lower-bounds gate-level circuit locations, because refining time steps into elementary operations can only increase the count.The model uses fixed-duration storage, with Cmin(K, S, ε) defined by infimizing worst-case circuit size over protocols achieving diamond-norm error at most ε.
B. Time-step convention: One time step has duration τ, so a fixed-width memory with N physical qubits over S steps contains NS storage locations and physical qubit-time τNS.The same convention is used for unencoded and encoded memories, with N = Nτ for noise accumulated during one interval.
C. Erasure-noise lower bound: Complete erasure occurs when all live qubits are independently erased, and adaptive width choices are bounded by optimizing deterministic allocations across the remaining storage budget.The proof uses the recurrence for F(s, v), followed by 1−x ≤e−x and Jensen’s inequality.
C. Erasure-noise lower bound: At least one complete measurement record has qs ≥K at every time step, implying Cpath ≥KS for K logical qubits.If a record ever had fewer than K physical qubits, the conditional output would have insufficient Schmidt number and could not achieve diamond-norm error below one.
D. CSS-code upper bound: For p < ∆< δGV and 0 < R < 1 −2h2(∆), sufficiently large CSS codes encode at least RN logical qubits with distance at least ∆N.The construction uses δGV ≃0.1100 and a = D(∆∥p) > 0.
D. CSS-code upper bound: The CSS construction achieves total error at most 2Se−aN with fixed-width circuit size Cpath = NS.The per-step error is at most 2e−aN, and the bound follows from Chernoff correction of erasure patterns below distance plus telescoping over S steps.
E. Circuit-level upper bound: Circuit gadgets with block rate Rgad, qubit factor cq, and duration ct give error at most TAe−βN, implementation depth at most ctT, and CFT ≤ cqctNT.Subsystem spacetime codes use a circuit-to-code map with Cst distinct from Cpath, while recovery failure is measured by PL; analytical derivations are supplied in the SI.

2. Schmidt number … 4. Fixed-duration memories

The paper defines the information-theoretic and circuit-accounting framework for quantum memories, including Schmidt-number and entanglement tools, subsystem-code noise models, adaptive execution costs, and fixed-duration requirements. These definitions support resource lower bounds applying to protocols that achieve prescribed logical error.

2. Schmidt number: Schmidt number is the minimum decomposition bound on pure-state Schmidt rank and cannot increase under local channels or conditioning on local classical outcomes.For bipartite mixed states, it is the smallest integer d permitting a convex decomposition into pure states of Schmidt rank at most d.
3. Paulis and subsystem codes: Subsystem codes are specified as [[N, k, r, d]] codes with stabilizer and gauge groups, protected logical qubits, gauge qubits, and dressed distance.The binary subsystem Singleton inequality applies for d ≥2, while d = 1 reduces to k + r ≤N.
3. Paulis and subsystem codes: The noise framework includes full-support product Pauli distributions, local-stochastic faults with rate p, and independent erasures whose locations are revealed to recovery.A local-stochastic rate p bounds the probability that every coordinate in any set A is faulty by p|A|.
4. The entanglement functional: Eχ tracks entanglement loss by measuring the smallest χ2-divergence from ρAB to a separable state across A : B.The proof uses norm control, monotonicity under separable channels, convexity, and the bound Eχ(Φ) ≤3.
1. Ideal and fault-tolerant circuits: Circuit size counts one logical circuit location per logical qubit present at each time step, including identity locations; a K-qubit memory therefore has Cideal = KT.The physical protocol may adapt its register based on prior outcomes, but its schedule cannot depend on later noise outcomes.
2. Circuit-size measures: Resource measures distinguish peak width, summed maximum width, worst-case execution size, and mean execution size.Adaptive executions can have different realized costs, and worst-case and mean size need not coincide with summed per-time-step maxima.
3. Circuit locations: Fault-tolerant gadgets replace ideal preparation, gate, measurement, and storage locations, while gate-level implementations add preparation, recovery, routing, measurement, and wait locations.The total gate-level location count is at least the storage-location count used for the modeled time steps.
4. Fixed-duration memories: A fixed-duration adaptive memory receives an unknown K-qubit state, returns it after S time steps, and chooses its width from earlier classical measurement records.It cannot shorten the prescribed storage interval or transfer input-dependent quantum information to an uncounted noiseless memory before the final time.

Supplementary Information D: Circuit-size lower bound for general noise … 1. Complete erasure

The supplementary results establish circuit-size lower bounds for general non-unitary noise and erasure noise. They combine entanglement contraction, information dimension, and complete-erasure arguments to rule out uniform constant relative overhead.

1. Entanglement contraction: For every non-unitary qubit channel, applying noise to m qubits followed by separable control contracts entanglement by a channel-dependent factor κN.The bound applies to layer-specific noisy-qubit counts and allows finite-dimensional classical registers without coherent quantum side information.
2. Layerwise circuit-size lower bound: Accumulating layerwise contraction over storage time yields a lower bound on Clay, the sum of the largest physical widths across time steps.The one-qubit theorem applies when 0 < κ < 1 and sufficiently long duration, while κ = 1 excludes error δ < 1/2 after one nonempty step.
2. Layerwise circuit-size lower bound: A Bell-pair test shows that accurate decoded states must retain entanglement, whereas repeated noisy layers and separable adaptive control impose the contraction upper bound.The proof uses two independent memory copies, local encoders and decoders, measurement records, and classical feedforward across the copy bipartition.
3. Dimension bound and combined result: K logical qubits require at least K live physical qubits at every time step, giving Clay ≥KS.The information-dimension argument feeds half of a maximally entangled state into the memory and bounds its Schmidt number at each boundary.
3. Dimension bound and combined result: Combining the dimension and one-qubit bounds gives a general K-qubit layerwise circuit-size lower bound for fixed error δ < 1/2 and duration S > Cδ.The K-qubit result reduces K−1 inputs to fixed pure states and discards their outputs before applying the one-qubit theorem.
3. Dimension bound and combined result: No compiler for a non-unitary qubit channel can satisfy one constant relative bound Clay ≤ CCideal across every memory width and duration.For a one-qubit ideal memory with Cideal = T, the general-noise theorem gives Clay = Ω(T log T) when 0 < κN < 1; κN = 1 excludes sub-half error.
1. Complete erasure: Under erasure noise, a time step erasing every physical qubit removes entanglement with the reference, limiting conditional final Bell-state fidelity to at most 1/2.The result holds even when erasure locations, the event time, and preceding measurement records are available to recovery.
1. Complete erasure: Adaptive protocols with bounded circuit size have a survival probability constrained by the probability of avoiding complete erasure, yielding a one-qubit circuit-size bound for erasure noise.The survival argument uses dynamic programming over remaining time and storage locations; randomized width choices cannot outperform deterministic choices.

2. Dimension along one execution · Supplementary Information F: CSS-code upper bound for erasure noise · 1. Code existence and concentration

The section proves that any adaptive protocol preserving K logical qubits for S steps must retain full logical dimension along some execution path, yielding a circuit-size lower bound. It then constructs positive-rate CSS codes with linear distance under erasure noise and establishes exponential concentration for excessive erasures.

2. Dimension along one execution: A successful K-qubit memory lasting S time steps has an execution path with physical dimension at least K at every step, so Cpath ≥ KS.This follows by preserving entanglement with a reference: a path whose register dimension ever falls below K cannot retain the full logical dimension.
2. Dimension along one execution: The combined erasure-memory lower bound adds the dimension cost to the one-qubit temporal circuit-size term.The proof obtains the dimension term from Proposition 13 and the temporal term by fixing K−1 logical inputs and discarding their outputs.
2. Dimension along one execution: For fixed ε0 < 1 and sufficiently large S, the lower bound’s logarithmic dependence can be expressed uniformly using log(S/ε).Because cε = −log(1−ε) is within constant multiples of ε for 0 < ε ≤ ε0, log(S/cε) = Θ(log(S/ε)).
Supplementary Information F: CSS-code upper bound for erasure noise: The CSS-code construction combines positive rate, linear distance, erasure concentration, and a fixed-width memory protocol to attain the stated memory scaling.The section identifies Theorems 15 and 18 and Lemma 17 as the ingredients used with the erasure lower bound in Corollary 19.
1. Code existence and concentration: For 0 < ∆ < δGV and 0 < R < 1 −2h2(∆), sufficiently large block lengths admit binary CSS stabilizer codes with parameters [[N, KN, dN]].The guaranteed-rate condition lies strictly below the balanced CSS Gilbert–Varshamov curve at relative distance ∆.
1. Code existence and concentration: The balanced CSS construction encodes KN = N −(k1,N + N −k2,N) = k2,N −k1,N = N −2k1,N logical qubits.The balance condition is k1,N = N −k2,N; it equates the constituent-rate arguments but does not assert equal realized X- and Z-distances.
1. Code existence and concentration: For X ∼ Bin(N, p) and p < ∆ < 1, the binomial Chernoff bound gives Pr[X ≥∆N] ≤e−ND(∆∥p).The exponent uses binary Kullback–Leibler divergence with natural logarithms, and D(∆∥p) > 0 because ∆ ≠ p.

2. Block size and logical error

A positive-rate CSS-code construction preserves K logical qubits for S erasure-noise steps with fixed width, while matching the optimal worst-case circuit-size scaling up to constants. The construction is existential and assumes ideal recovery rather than providing an efficient or local implementation.

CSS-code construction: Theorem 18 encodes K logical qubits into one [[N, KN, dN]] CSS code block with KN ≥ K, ideal recovery, and diamond error at most ε.The code parameters satisfy dN ≥ ∆N under 0 < p < ∆ < δGV and 0 < R < 1 − 2h2(∆).
CSS-code construction: Because the block width is fixed across S time steps, both cumulative spacetime measures equal NS.Here S is the number of memory time steps, equivalently the number of erasure-channel applications.
Error analysis: Independent erasures are correctable whenever fewer than dN physical qubits are erased; the failure probability is bounded using the binomial erasure count.The erased-qubit count satisfies X ∼ Bin(N, p), and bad patterns have |E| ≥ dN.
Optimal worst-case circuit size: Corollary 19 establishes matching lower and upper bounds, up to constants depending only on p and ε0, for adaptive protocols under independent erasure noise and ideal recovery.The bounds hold for all K ≥ 1 and sufficiently large S, uniformly over ε ∈ (0, ε0].
Limitations: The construction is an existence proof with ideal recovery and lacks an efficient decoder or geometrically local implementation.Dimension and reliability terms are comparable when K = Θ(log(S/ε)).

Supplementary Information G: Circuit-level upper bound

Under a strong positive-rate gadget-family assumption, width-K, depth-T circuits can be simulated with exponentially suppressed gadget error and circuit resources having additive dependence on logical width and target error. This result is conditional and is not claimed for existing architectures.

Assumption 21: A positive-rate code block encodes at least RgadN logical qubits, while each complete logical-layer gadget uses at most cqN live physical width and lasts at most ct time steps.The gadget family need only support the operations used by the ideal circuit, unless arbitrary circuits are intended.
Assumption 21: Ae−βN bounds the composable error of one logical gadget uniformly over layers, preceding measurement records, inputs, and external reference systems.The comparison includes both quantum outputs and newly produced classical outcomes.
Limitations: The result requires stronger assumptions than currently established general-purpose compiler theorems and does not claim that any existing architecture satisfies them.Comparing the circuit-level scaling directly with the memory converse also requires an explicit relation between ideal depth T and implementation depth S.
Conditional circuit achievability: Theorem 23 conditionally constructs simulations for width K and depth T circuits achieving every target diamond-norm error 0 < ε ≤1 with an available block length and bounded implementation depth.The construction uses complete quantum–classical channels, including classical measurement records passed between gadgets.
Conditional circuit achievability: The resulting worst-case physical circuit size has the asserted additive dependence on logical width and target error, with cgad depending only on the gadget-family constants.The logarithmic contribution to the selected block length is determined by the target-error requirement, while width and depth convert it into circuit size.

Supplementary Information H: Subsystem spacetime-code bounds

This supplementary section states the circuit-to-code assumption, proves subsystem spacetime-code bounds, and gives a three-qubit repetition-code example.

Assumption 24 states the circuit-to-code assumption used by the subsystem spacetime-code analysis.
Theorems 25 and 27, together with Corollary 30, establish the bounds used in the main text and corresponding Methods subsection.
Remark 28 provides a three-qubit repetition-code example.

1. Circuit-to-code relation · 2. Singleton and exact correction · 3. Same-syndrome fault bound

The sections connect fault-tolerant circuits to exact subsystem spacetime codes, then derive Singleton and same-syndrome limits on correction. These bounds show that vanishing logical error requires growing absolute redundancy, while relative overhead need not grow when protected logical-qubit count increases.

1. Circuit-to-code relation: Clifford circuits and Pauli reductions naturally induce exact binary linear subsystem codes, but the correspondence is not asserted for every fault-tolerant protocol.The code length counts selected Pauli fault locations rather than physical storage locations, so circuit-size transfer requires a separate location-count assumption.
1. Circuit-to-code relation: Circuit-size comparisons require Assumption 24, which can fail when coordinates unite mutually exclusive adaptive branches or abstract-code Paulis are unrealizable circuit faults.The stated constant comparison holds when each physical circuit location maps to at most a constant number of selected fault coordinates.
2. Singleton and exact correction: Every exact binary linear subsystem spacetime code [[Nst, k, r, dst]] with k ≥1 obeys a Singleton circuit-size bound.The proof treats dst = 1 by dimension counting and dst ≥2 using the subsystem Singleton inequality, then transfers the result through the location-count assumption.
2. Singleton and exact correction: Exact correction of every Pauli fault of weight at most t forces code distance at least 2t + 1, assuming relevant Pauli strings are realized by circuit faults.Otherwise a dressed logical of weight at most 2t splits into two same-syndrome faults that no recovery can both correct.
3. Same-syndrome fault bound: Theorem 27 lower-bounds logical failure for any complete-syndrome decoder by pairing faults related by a dressed logical Pauli with identical syndromes.The decoder receives only the syndrome, and each pair contributes at least the smaller of its two fault probabilities; the result applies to deterministic and randomized decoders.
3. Same-syndrome fault bound: Under full-support product Pauli noise, the pair-overlap bound depends on ρ = qmin/qmax and code distance, while the completely depolarizing case has qmin = qmax and forces PL ≥1/2.For the three-qubit repetition code, majority decoding attains the overlap bound under independent X faults, although the code does not correct arbitrary single-qubit Pauli faults.
3. Same-syndrome fault bound: The results establish growing absolute redundancy as logical error vanishes, but do not require growing relative overhead when the number of protected logical qubits increases simultaneously.The Singleton-to-circuit-size conclusion still depends on Assumption 24, whereas the overlap inequality applies to arbitrary Pauli fault distributions under syndrome-only Pauli recovery.

Supplementary Information I: Distance and threshold conditions

Distance growth alone does not guarantee a decoder threshold because malignant fault sets may proliferate too quickly. Theorem 32 gives sufficient conditions ensuring a positive threshold by controlling malignant-set growth and suppressing failure probability.

Sufficient condition: Theorem 32 provides a sufficient condition for a positive decoder threshold by counting malignant fault sets by weight.The condition controls malignant-set growth but does not imply optimal physical circuit size.
Assumptions: The theorem assumes scale-uniform local stochastic faults, correction of all patterns up to weight tλ, malignant-set coverage, and log Nst(λ) = o(dst(λ)).The covering hypothesis requires every failed pattern to contain a malignant set of weight at least tλ + 1.
Threshold consequence: lim λ→∞PL(λ, p) = 0 for every fixed 0 ≤p < p0, for some p0 > 0.Thus pth ≥p0 > 0 in the sense of Eq. (C7).
Proof mechanism: ζtλ+1 provides exponential suppression in the spacetime-code distance, while log Nst(λ) = o(dst(λ)) prevents the prefactor from overcoming it.Here ζ = µpst(p), and the argument applies whenever µpst(p) < 1.
Limitation: The result establishes threshold existence but does not imply optimal physical circuit size.The theorem is sufficient rather than converse-optimal.

Supplementary Information J: Consequences for resource scaling · 1. Resource lower bounds from error converses · 2. Resource upper bounds from error suppression

The supplementary section converts error converses into resource lower bounds and derives sufficient resource upper bounds from exponentially suppressing logical gadgets. It also clarifies that per-gadget accuracy allocations do not establish necessary logarithmic costs for complete circuits.

1. Resource lower bounds from error converses: Proposition 33 converts a converse lower bound on logical error and a size–distance relation into an accuracy-dependent lower bound on a specified resource.The resource may be physical-qubit count, spacetime-code length, circuit-to-code location count, or worst-case physical resource.
1. Resource lower bounds from error converses: The lower-bound conversion applies to code or gadget families indexed by distance d, with fixed resource choice Cres(d) and positive distance-scaling parameters.The proposition assumes constants a(p), b(p), cres, β, and γ that are positive and independent of d.
1. Resource lower bounds from error converses: For a depth-T circuit with gadget error at most ε/T, Eq. (B6) provides a sufficient composable-error allocation across gadgets.This allocation leads to distance and resource upper bounds containing log(T/ε) for exponentially suppressing gadget families.
1. Resource lower bounds from error converses: A log(T/ε) reliability contribution is not proven necessary for every complete T-layer computation.Applying the converse with target ε/T would require every individual gadget to have error at most ε/T, which does not follow from the overall circuit-error requirement.
2. Resource upper bounds from error suppression: Proposition 34 gives sufficient costs for M logical gadgets implementing complete ideal logical layers, including gates, preparations, measurements, and classical feedforward.The proposition fixes physical noise strength p and considers distances realized by a code-and-gadget family.
2. Resource upper bounds from error suppression: The upper-bound construction assumes a uniform composable gadget error satisfying q(d, p) ≤ B(p)e−α(p)dβ.The same bound applies to every gadget and permitted preceding measurement record, with B(p), α(p), and β independent of d, M, and ε.
2. Resource upper bounds from error suppression: The sufficient upper bound distinguishes a calculated target distance from an available distance realized by an actual code-and-gadget family member.A distance-availability condition supplies an available d near every real target distance x ≥ d0, and its multiplicative replacement factor does not alter asymptotic scaling.
2. Resource upper bounds from error suppression: For total composable error bounded by the proposition’s condition, target error 0 < ε ≤1 is achieved with the stated per-gadget circuit-size bound.Direct diamond-norm telescoping permits Ccomp = 1; the available distance may differ from the calculated target distance by a factor independent of M and ε.

3. Relation among the results … 2. Shor’s factoring algorithm

The results relate memory and circuit overhead through a shared logarithmic contribution, whose relative importance decreases for sufficiently wide, polynomial-depth algorithms. Standard implementations of Shor’s algorithm fall in this regime, although abstract asymptotic ratios do not estimate practical physical overhead.

3. Relation among the results: The paper summarizes its main results and their relationships in Table II.
Supplementary Information K: Width and depth regimes for quantum algorithms: The tight erasure-noise memory result extends as an upper bound to circuits with logical width K and depth T, using εFT for implementation error.εFT is distinct from the ideal algorithm’s approximation error.
Supplementary Information K: Width and depth regimes for quantum algorithms: K = Ω(log(T/εFT)) suffices for constant relative overhead in the conditional circuit upper bound, while erasure-noise memory has minimum relative overhead Θ(1 + log(S/εFT)/K).The logarithmic contribution is negligible only when K = ω(log(T/εFT)); the circuit converse is not matching for every algorithm.
1. Polynomial-depth quantum algorithms: K(n) = Ω(n), T(n) = poly(n), and εFT(n) ≥ 1/poly(n) make the logarithmic term asymptotically smaller than ideal logical circuit size.
1. Polynomial-depth quantum algorithms: This regime includes polynomial-depth quantum Fourier transforms, reversible arithmetic, variational algorithms, Hamiltonian simulation, and Shor’s factoring algorithm.The comparison concerns only conditional-upper-bound terms and does not establish small practical physical overhead.
2. Shor’s factoring algorithm: For factoring an n-bit integer, standard Shor implementations use at least linearly many logical qubits and polynomial logical depth, so log(T/εFT)/K → 0 for constant or inverse-polynomial εFT.
2. Shor’s factoring algorithm: The abstract Shor estimate has a small logarithmic contribution relative to KT, but its numerical ratio is not a physical overhead estimate because practical constants and implementation costs can dominate.State distillation, routing, decoding, connectivity, and logical-operation duration may dominate.

3. Unstructured quantum search … 8. Long-lived memories, networking and sensing

The logarithmic spacetime-overhead term is negligible for sufficiently wide, polynomial-depth computations but can dominate when a small logical register must remain coherent for long durations. Its impact therefore depends strongly on circuit implementation, width, depth, and required precision.

3. Unstructured quantum search: Grover search has logical width K and query depth T, with the two conditional circuit-bound contributions having the same asymptotic order for constant or inverse-polynomial εFT.An explicit oracle implementation may add circuit depth.
3. Unstructured quantum search: Amplitude amplification has the same implementation-dependent comparison: the relative contribution of the logarithmic term depends on how the initial success probability scales with logical width.Its query depth is determined by the initial success probability a.
4. Phase estimation: For q = O(m) in standard phase estimation, the logarithmic term and KT have the same asymptotic order; for q ≫ m, the logarithmic term is asymptotically smaller.Standard phase estimation uses an m-qubit control register and controlled evolutions of total duration approximately 2^m.
4. Phase estimation: For a fixed-size target system with increasing precision, iterative phase estimation makes the ratio diverge, so the logarithmic term dominates regardless of the abstract problem.Iterative phase estimation reuses one control qubit, demonstrating that implementation choices affect the comparison.
5. Amplitude estimation: For fixed, small problem registers, iterative and maximum-likelihood amplitude-estimation variants can make the logarithmic term dominate as the required precision increases.These variants reuse a small control register, unlike full phase-estimation implementations that increase K with precision.
6. Long-time Hamiltonian simulation and quantum signal processing: When simulated time, inverse simulation error, and block-encoding implementation have polynomial scaling in q, D = poly(q) and the ratio tends to zero.For fixed q and increasing simulated time or required polynomial degree, the ratio diverges and the logarithmic term eventually dominates.
7. Adiabatic algorithms and quantum walks: For adiabatic algorithms with K = Θ(n) logical qubits and polynomial runtime, the ratio log(T/εFT)/K tends to zero; exponentially small gaps can instead yield Θ(1).The logarithmic term dominates only when log T grows asymptotically faster than the logical width.
8. Long-lived memories, networking and sensing: Long-lived memories, network buffers, heralded-entanglement memories, sequential discrimination, and sensing protocols can fall within the memory setting and obey its circuit-size lower bound.These tasks require a small logical register to remain coherent over many rounds or a prescribed duration.