2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ For a physical QC, no, because it can only run toys up to a few tens or hundreds of qubits in size. For the abstract mathematical construct that's a QC, yes, of course. $\endgroup$ – R.. Jun 29 at 19:57
  • $\begingroup$ Related: Can a quantum computer simulate a normal computer? $\endgroup$ – Glorfindel Jun 29 at 21:20
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "but nobody ever draws the circuit" - actually, that's not true, in part because, at the gate level, QC and classical are different - QC is always reversible (except for measurement), hence the gates are different - a QC doesn't have an "AND" gate (because that's not reversible); circuits need to be tweaked to account for it, and so they really are written out. Now, this sort of difference doesn't change the big-O time of an algorithm, but it is something the a designer of a Quantum Circuit must take into account $\endgroup$ – poncho Jun 29 at 19:40
  • $\begingroup$ @poncho but that’s the difference between an irreversible classical circuit and a reversible classical circuit. It’s not a quantum issue. $\endgroup$ – DaftWullie Jun 29 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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