The normal question about this topic would be: Can a classical computer implement a quantum computer? But now I wonder the exact opposite: can a quantum computer implement a classical one? Can we say that classical computation is a subset of quantum computing?

  • $\begingroup$ Isn't the question whether one class of computer can tractably implement the other? I believe that a classical computer can simulate a quantum computer, but the complexity just gets bad very rapidly in the worst cases. $\endgroup$ – Ben Crowell Feb 16 '18 at 16:01
  • $\begingroup$ Your current computer is using tons of qubits without taking advantage of any of the special quantum features. $\endgroup$ – Erik Eidt Feb 24 '18 at 21:37

Yes, it is perfectly possible to run a quantum computer as a classical one, simply by keeping all the qubits in 0 or 1 and deciding not to use the capability to place them on superpositions of those states or entangle them to each other.

To be a bit more precise, the computation complexity class BQP (of problems that can be efficiently solved in a quantum computer) contains as a subset the class BPP (of problems that can be efficiently solved in a classical computer, if you allow for a finite probability of success) which itself contains the class P (of problems that can be efficiently solved in a classical computer). The Wikipedia pages for those complexity classes have more detail on those inclusions.

  • $\begingroup$ I think OP may be referring to the issue where you can only use reversible gates, e.g. fully quantum computers cannot use AND gates. $\endgroup$ – knzhou Feb 16 '18 at 15:38
  • 1
    $\begingroup$ @knzhou Reversible computing is Turing complete and can be happily implemented in quantum computers. (In more detail: quantum computers cannot implement 'standard' (lossy) AND gates, but they have no problem with the reversible-computing equivalent $(x,y,z)\mapsto (x,y,z\oplus(x\otimes y))$.) $\endgroup$ – Emilio Pisanty Feb 16 '18 at 16:25

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.