# Why is it not a good idea to run Shor's algorithm on a big noisy quantum computer?

Suppose I try to run Shor's algorithm on a big noisy quantum computer.

For a given input I repeat the circuit many times and collect statistics for the measurements of each qubit.

Now based on the measurement statistics, I try to guess a factor (or more the order in the order finding subroutine). Since I allow for polynomial overhead and it is easy to check I can make fairly many guesses.

Since the circuit is fairly deep and the qubits are noisy the measurements of individually qubits will probably be very close to 50%/50%, but if I just have a slight bias 49,9% then the probability gets boosted by Chernoff bounds and since the samples are independent for the measurements of a single qubit.

Furthermore, with substantial classical overhead, I get to try many combinations based on my simulated data.

I sense that the strategy sketched above will never work and we need error correction? But what is the exact reason? Will the bias be so small that I need exponentially many samples or checks? Do I need finer control over the noise to make sure that the noise is unbiased?

## 1 Answer

Factoring a 2048 bit number with Shor's algorithm involves performing one billion Toffoli gates under superposition (ref).

Suppose your superposed Toffoli gate error rate is an amazing 0.01%. Note that if you experience a single Pauli error the output is useless. The chance of finishing is $$0.9999^{1000000000}$$. Which is less than $$10^{-40000}$$.

So no, you can't make it work. You will never ever in your whole life get a shot without a fatal error. You would be better off just randomly guessing at the factors.

• So you're saying there's a chance. Commented Mar 1 at 5:11