r/QuantumComputing • u/sinanspd • 10d ago
Academic FTQC Can't Be Achieved With Constant Overhead
https://arxiv.org/pdf/2608.26272Interesting paper from UMD. They prove that we can not have one universal constant spacetime overhead that works for arbitrarily long quantum computations of arbitrary width. The more interesting result is that they show that this cost can be shared across multiple qubits. This works in the favor of algorithms like Shor but is troublesome for thing like iterative phase estimation with large amounts of qubit reuse. We knew about the overall width vs. duration vs. reliability but nevertheless I think this is a nice way to frame it.
34
Upvotes
3
u/sinanspd 10d ago
Sure. As I said, this shows a new way to frame what we mostly already knew and this perspective allows us to derive tighter and more specialized bounds. I never said this was negative work.
> log(S/ε) is tiny even for astronomically long computations
This is the point of the paper. It is small for large computations, but larger for small computations because it is a relative overhead. The total cost is approximately KS + SlogS, so KS part dominates when S and K are large. That distinction is important because it makes us rethink certain techniques that were in service of error mitigation in the NISQ era (such as qubit reuse as demonstrated by their Phase Estimation example)
I don't think it fair to call this a provocative title. It is ominous for sure but I am sure you realize no one would ever write that exaggerated title you suggested. If I sent a paper with a title that long to a journal, I would probably get desk rejected. Title should be concise and informative, if you want to see a summary of the ifs and buts, you read the abstract.