Quantum Fault Tolerance Costs an Unavoidable Logarithm: What Bharti, Haug and Tanggara Proved on 26 August 2026
Daniel Gottesman opened a 2013 paper with a question that reads like a purchasing question: “What is the minimum number of extra qubits needed to perform a large fault-tolerant quantum circuit?” His answer, in arXiv:1310.2984, was that the ratio of physical qubits to logical qubits can be a constant in the asymptotic limit, using quantum low-density parity check codes. That abstract is careful about what it settles. It counts qubits, and it states no result about time.
Thirteen years later, three researchers have answered the half of the question Gottesman left alone. Their answer is a formula with named variables.
What the 26 August preprint proves about quantum memory
Kishor Bharti, Tobias Haug and Andrew Tanggara submitted Fault-tolerant quantum computation cannot be achieved with constant spacetime overhead to arXiv on 26 August 2026 at 18:00:25 UTC. It runs to forty pages and is filed under quantum physics and information theory. It is a preprint, so it has not yet been through peer review, and every reading of it should carry that qualification for now.
The theorem concerns the least demanding thing a quantum computer can be asked to do, which is to preserve quantum information in a memory, unchanged, for a while. No computation is performed on it. For a memory of width K held for duration S at target error ε, the authors prove that the minimum worst-case number of physical storage locations scales as Θ(S(K + log(S/ε))). The first term is the cost of holding the logical information at all. The second is an additive reliability cost, S log(S/ε), which pays for the state surviving the whole duration. That second term is what no protocol removes inside this model.
The generosity of the assumptions is what gives the result its force, and the assumptions should be stated exactly. The tight bound is proved in an erasure model. Erasures occur independently at each time step with a fixed probability p in the range 0 < p < δGV, where the Gilbert-Varshamov threshold δGV is approximately 0.1100. The erased locations are known to the recovery procedure, and recovery itself is treated as ideal. Real hardware does not generally receive all of those concessions, and recovery is never ideal, though erasure-qubit architectures are being built precisely to deliver known-location erasures. The bound holds under conditions kinder than the ones a machine will meet.
Practical takeaway. The theorem prices quantum error correction as a function of width, duration and target error. It dates no machine, and a claim that it constrains the arrival of a cryptographically relevant quantum computer is a claim the paper declines to make.
Why Gottesman's 2013 constant-overhead construction left the time question open
The 2013 result is a statement about a ratio. Take a large fault-tolerant circuit, ask how many physical qubits it consumes per logical qubit, and that ratio settles to a constant determined by the underlying code family. It was a genuine surprise at the time, because the earlier concatenated constructions consumed qubits at a rate that grew with the size of the computation. Quantum low-density parity check codes removed that growth from the hardware count.
What a qubit ratio never captured is how long each protected step takes. Space overhead and time overhead are separately purchasable and separately billed, and a machine is paid for in both. The 2026 preprint multiplies them, and the product carries a floor. That is a different quantity from the one settled in 2013, which is why both results hold.
The condition stated in the same paper: constant relative overhead once width reaches log(S/ε)
The paper does not stop at the bound. Relative overhead scales as Θ(1 + log(S/ε)/K), so it stays bounded by a constant as soon as the width K reaches Ω(log(S/ε)). The authors put the consequence plainly: constant overhead can be possible for sufficiently wide computations. They add that no single constant bounds the spacetime overhead uniformly over all widths. Those two sentences have to be read together, and the distinction between them is a distinction between two regimes. At K = Ω(log(S/ε)) the ratio is bounded. The additive term becomes asymptotically negligible against SK only in the stronger regime K = ω(log(S/ε)). At no width does the absolute reliability cost go away; a wide machine spreads it across the logical qubits it already needs.
The authors then classify cases. Standard implementations of Shor's algorithm are wide enough to amortize the reliability cost. Grover search sits near the crossover of the width-duration tradeoff. Iterative phase estimation and long-time simulation are named as workloads that can enter the regime where the additive cost dominates, because they run a narrow register for a long time. Polynomial-depth algorithms whose width reaches Ω(log(S/ε)) reach constant relative overhead. The paper also supplies a positive-rate CSS code construction that attains the memory bound, so the floor is reached by an explicit family and not only proved.
One boundary deserves marking. The extension from quantum memory to full fault-tolerant circuits is a conditional upper bound: the authors give sufficient conditions under which the same width-reliability tradeoff carries over to a circuit of width K, depth T and target diamond-norm error ε. The memory converse is not a matching lower bound for every algorithm, and the authors note that finite-device estimates depend additionally on constants and architecture-specific location counts. The result describes asymptotic scaling. It gives no engineering estimate of physical overhead on a real machine.
Why this changes nothing about the 31 December 2030 date in OMB Memorandum M-26-15
The federal migration calendar does not depend on a resource bound. OMB Memorandum M-26-15, issued 24 June 2026, directs agencies to mitigate as much quantum risk as feasible by 31 December 2030 and required migration plans within 120 days, a clock that runs out on 22 October 2026. What the memorandum sets out is an inventory, modernization and phased-migration program; it states no derivation for its dates. Our own reading, offered here as an inference and not as a quotation, is that a schedule of that shape tracks how long a large organization needs to find and replace cryptography it has already deployed. A theorem about the builder's cost reaches no such quantity. We traced the instruments and the procurement lever in a read of the GSA route, and made the general argument about attacker-side estimates and schedules in an earlier piece this month. Today's result differs from that one in direction: it raises a floor under the builder's cost, where that piece concerned a falling estimate of the attacker's.
What a buyer can actually do with a width-and-duration theorem
The theorem yields a test, and the test is a conditional one. Whether the additive term matters for a given workload depends on four quantities the paper makes explicit: the logical width K, the duration S, the target error ε, and whether the architecture satisfies the sufficient conditions under which the memory scaling extends to circuits. Where the width is comfortably above log(S/ε), the cost is amortized and the question is closed. Where a narrow register runs for a long time, which is the shape the authors attribute to iterative phase estimation and long-time simulation, the reliability term is the one to ask about.
That is a narrower question than a market claim, and it should stay narrower. The paper does not license a statement about which commercial products are burdened, and quantum sensing is not automatically a fault-tolerant circuit to which this result applies at all. What it licenses is a question to put to a vendor: what are K, S and ε for the workload being proposed, and does the proposed architecture meet the paper's conditions. When IBM reported a modular cryogenic milestone this month, the achievement we examined in its own dated terms was an engineering step toward wide machines, which is the regime where the logarithm is cheapest to carry.
How Quentir Reads It
Negative and limiting results have a short public life. A theorem that says something cannot be done attracts a day of attention and then leaves the record, while the vendor claim it constrains stays in circulation for years. That asymmetry is why we treat proofs of this kind as durable entries, with the same durability we gave the reversed step two auditors found inside an AI-generated proof in a piece earlier this month. The corrective is the part of the literature that ages well.
A bound this clean invites misuse in two directions, and both misuses drop the qualification. Read as a ceiling on capability, it becomes ammunition for the position that fault-tolerant quantum computing is further away than its advocates claim, which the paper's own width condition refutes. Read defensively, it could be offered as a reason to relax a migration schedule that was never keyed to hardware timelines. Both readings convert a statement about resource accounting into a statement about calendars, which is a step the authors do not take.
What the paper gives is a unit of account. Overhead becomes something that can be quantified, attributed and compared across architectures, in a formula with named variables, and the authors supply a code construction that meets their own bound. The All-access membership carries our full register of these results with their sources and their standing over time, which is the argument for the archive: a proof like this one is worth more in its fifth year than in its first week. Readers who want a lighter entry point can start with the free Quentir Intelligence stream.
Two things remain genuinely open. The first is peer review, and a forty-page proof deserves it before the bound is treated as settled. The second is stated by the authors: the extension from quantum memory to full fault-tolerant circuits holds under sufficient conditions they identify, which leaves open how broadly those conditions are satisfied by the architectures being built. The question worth carrying into the next result is which machines now under construction sit inside those conditions, and at what width and duration their intended workloads actually run.
Sources: Kishor Bharti, Tobias Haug and Andrew Tanggara, “Fault-tolerant quantum computation cannot be achieved with constant spacetime overhead”, arXiv:2608.26272, submitted 26 August 2026, 18:00:25 UTC; 40 pages; quant-ph and cs.IT (abstract and full text read 28 August 2026; preprint, not peer reviewed. Theorem 1's minimum worst-case storage Θ(S(K + log(S/ε))) and the additive S log(S/ε) reliability term; the relative overhead Θ(1 + log(S/ε)/K), the K = Ω(log(S/ε)) condition for bounded relative overhead and the stronger K = ω(log(S/ε)) regime in which the logarithmic term becomes negligible; the authors' statement that constant overhead can be possible for sufficiently wide computations, alongside their further statement that no single constant bounds spacetime overhead uniformly over all widths; the erasure model, in which erasures occur independently at each time step with a fixed probability p in the range 0 < p < δGV, the Gilbert-Varshamov threshold δGV being approximately 0.1100, erased locations are known to recovery, and recovery is ideal, and within which the additive term is the part no protocol removes; the positive-rate CSS construction attaining the memory bound; Theorem 2 as a conditional circuit upper bound holding under sufficient conditions, with no matching lower bound claimed; the algorithm cases in the supplementary material, with Shor's algorithm amortizing the cost, Grover search near the crossover, and iterative phase estimation and long-time simulation able to enter the regime where the cost dominates; and the caveat that finite-device estimates depend additionally on constants and architecture-specific location counts. The arXiv record lists DOI registration as pending at the time of writing, so no DOI is cited here). Daniel Gottesman, “Fault-Tolerant Quantum Computation with Constant Overhead”, arXiv:1310.2984, submitted 10 October 2013 (abstract page read 28 August 2026; the constant asymptotic ratio of physical to logical qubits, the quantum low-density parity check code construction, and the opening question quoted here; the abstract states no time-overhead result). Executive Office of the President, Office of Management and Budget, Memorandum M-26-15, “Execution of the Migration to Post-Quantum Cryptography”, issued 24 June 2026 (the inventory, modernization and phased-migration program, the 31 December 2030 mitigation objective and the 120-day agency migration-plan requirement expiring 22 October 2026; the memorandum states no derivation for its dates, and the reading offered in this article that the schedule tracks organizational replacement time is Quentir's inference, marked as such in the body. Dates as recorded in our 26 August 2026 read of the GSA procurement route).
Published intelligence, built to inform your own decisions. Published: August 28, 2026.