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.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ see quantumcomputing.stackexchange.com/q/18465/55, quantumcomputing.stackexchange.com/q/9951/55 $\endgroup$– glS ♦Feb 7 at 10:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
3$\begingroup$ And just for fun here's the original paper (from 1985) that formalizes a Quantum Turing Machine and implicitly demonstrates that ideal quantum computers are at least as efficient as classical computers royalsocietypublishing.org/doi/abs/10.1098/rspa.1985.0070 and this paper (from 1993) which builds upon it to formalize the class of BQP dl.acm.org/doi/10.1145/167088.167097 $\endgroup$ Feb 7 at 10:03
-