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 1


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.

  • 11
    $\begingroup$ So you're saying there's a chance. $\endgroup$
    – squiggles
    Mar 1 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.