How accurate must QM be for applications of quantum computing?

Question

The Tale of One-Way Functions (section 2.4) claims that quantum mechanics would have to be accurate to an remarkable (absurd?) degree for an application such as factoring large numbers. So, orthogonal to the thousands of qubits and billions of gates that might be necessary to break 2048-bit RSA, can someone give a numerical estimate of this? Something along the lines of

Factoring $N$-bit numbers with Shor would require $D$ digits of accuracy in qubit amplitudes.

More generally, is this something that people (you quantum computer people) consider, i.e. models of quantum computing with bounded precision amplitudes?

(Please forgive my ignorance and inability/unwillingness to go through the algorithm and come up with an answer myself.)

---

Addendum:

I suppose what I had in mind is along the lines of simulating a quantum computer with a classical computer, with some finite representation of $\mathbb{C}^2$ for qubits. If one does all the exponentiations, DFTs, sums over the superpositions, etc., would the necessary size of that "finite representation" be ludicrous in order to achieve the necessary interference?

However, this mindset may not be physical or model-independent, and might not give any intuition about quantum computing in any case.

Is there some way of quantifying a regime where we experimentally feel that linearity holds and can this be translated into parameters going outside that regime for something "practical" like factoring? Or, at what point does something like factoring start testing quantum mechanics?

Answer 1

Because quantum mechanics is linear, and all operations have eigenvalues on the complex unit circle, relative precision is the key metric. A uniform superposition over 1000 qubits has amplitudes smaller than $10^{-150}$. Additive perturbations to those amplitudes by tiny amounts, like $10^{-12}$, would be disastrous. But multiplicative perturbations by tiny amounts, like $1 + 10^{-12}$, would be extremely difficult to detect.

Floating point numbers are great at achieving good relative precision. I think it's totally plausible that storing amplitudes using double precision floating point numbers would be sufficient to simulate Shor's algorithm factoring 1024 bit numbers (ignoring that it's totally intractable due to the amount of FLOPs required). For factoring 2048 bit numbers you would probably need quads, because the amplitudes would be getting uncomfortably close to the minimum positive double. Asymptotically I expect you need $O(\lg n)$ exponent bits and mantissa bits for each amplitude, where $n$ is the number of bits of the number being factored.

It's notable that in practice we will be using error correction, and to factor bigger numbers we will be using bigger code distances. The number of qubits is scaling up with the size of the problem; with the amount of precision required. It's conceivable that, when you account for error correction, this reduces the per-amplitude precision required for factoring to work.

It should also be noted that this is all highly interpretation dependent. For example, a path summation simulator will have qualitatively different space and precision requirements compared to a state vector simulator. And don't forget we're making artificial separations between the state of the computer and the rest of the universe in order to decide on the precision of our floats, while nature presumably does not have a separation in that sense. And of course it's a bit strange to imagine nature storing and operating on amplitudes using floats, since floating point arithmetic circuits are quite complex and driven by engineering concerns rather than simplicity concerns.