A quantum computer also requires to perform classical computations.

I would like to know if to implement Shor's algorithm, there is a heavy classical computation cost (i.e. that would require a supercomputer).

I exclude the computation costs required by quantum error-correction, and the classical cost required to pre-compile the circuit. I would like to know the classical computation cost while the quantum algorithm is running (maybe there are classical computation to do in parallel of the quantum gates implementations).

For instance, in Zalka's or Gidney's implementation: do we need a classical supercomputer or would a laptop suffice for the job?


1 Answer 1


My guess is that a laptop would be sufficient for computing the lookup tables and delayed choice fixups and various other things-that-aren't-error-correction on the fly. There's tens of microseconds from Toffoli to Toffoli, and that's a lot of time for a computer. But... I fundamentally have to disagree with your question's framing, because it's a complete disaster of a mistake to ignore the cost of error correction.

Each surface code logical qubit would be generating around a gigabit of syndrome data per second. That's easily enough data to keep a CPU core busy decoding the errors. But there are ten thousand logical qubits of space. So, back of the envelope, you need ten thousand CPU cores running alongside the quantum computer, just to error correct the logical qubits.

Modern super computers have millions of CPU cores. So you need an amount of classical compute that's roughly 1% of a modern super computer. The laptop is totally negligible in comparison.

  • $\begingroup$ Thanks. I know that error-correction can be very costly. I simply wanted to "separate" the different contributions simply for a pedagogic understanding (I wanted to know if managing the algorithm "per se" is expected to be costly or not). $\endgroup$
    – HelloMan
    Apr 19 at 11:52
  • $\begingroup$ Thanks for your note on error correction. What about another code than surface code, for example IBM latest results (ibm.com/quantum/blog/…). If I understand correctly, so far this code is available only for Clifford operations. However, once it is adapted to Clifford+T gates, will there be a significant drop in computational power needed for error correction? Lets say, a normal desktop would be sufficient or do we always need a grid of GPUs or similarly powerful computer? $\endgroup$ Apr 20 at 6:37
  • 1
    $\begingroup$ @MartinVesely Decoding error-correction will not necessarily cost a lot (at least this is research question). Riverlane proposed a decoder that consumes 8mW of power to decode a distance 23 surface code (close to what is needed for Shor's algorithm for typical error rates) : arxiv.org/pdf/2309.05558.pdf . Though there is often a tradeoff between the code threshold and the consumption (I think they use a simple energy efficient decoding scheme so maybe they have a threshold a bit worse). My point is just to say that decoding error-correction will not necessarily be super costly. $\endgroup$ Apr 20 at 8:10

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.