2
$\begingroup$

There are many instances, at least in theory, of problems that quantum computers can solve faster than classical computers. On the other hand, quantum computers are capable of computing anything that a classical computer can. I am curious to know if there are problems that, for whatever reason, classical computer would be more efficient in doing them than an ideal quantum computers? You can think of it as "classical advantage" if you will.

$\endgroup$
1

1 Answer 1

8
$\begingroup$

It is proved that the complexity class P (loosely the problems we can efficiently solve on classical computers) is a subset of the complexity class BQP (loosely the problems we can efficiently solve on a QC). So no, as far as "computing efficiency" goes, there is no case in which a classical computer would outperform a universal, fault-tolerant quantum computer.

In practical terms, you can start talking about how efficient we are at building classical computers vs quantum computers. And you can come up with any number of metrics for why a classical computer would be preferred over a quantum one. But all that aside, if you give me an ideal CC and an ideal QC, any problem the CC can solve efficiently so too can the QC.

$\endgroup$
2

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.