4

I realize that fundamentally speaking quantum and classical computers might as well be apples and oranges, and that for very specific problems such as integer factorization with Shor's algorithm quantum computers blow conventional computers out of the water, but could a quantum computer run classical algorithms?

If so, using a comparable classical computer, how would the calculation speed of a quantum computer running a classical algorithm compare to the calculation speed of the classical computer?

Steve Mucci
  • 161
  • 4

1 Answers1

7

Quantum computers can run classical computations using exactly the same algorithms, and hence have the same running time in terms of scaling. For example, if you look at shor’s algorithm, a major component of that is modular exponentiation, but nobody ever draws the circuit because they just say “use the classical algorithm”.

In terms of absolute running time, that is heavily hardware dependant so you can’t make comparisons so easily.

Quantum computers offer the possibility of other algorithms in addition to the classical ones that could be faster, but there’s no standard method for generating an improvement.

DaftWullie
  • 62,671
  • 4
  • 55
  • 140