2
$\begingroup$

Where is a classical computer better than a quantum computer? Is there any known domain where classical algorithms always beat quantum ones, say, both in terms of time and space complexity?

If yes, could you please give me examples?
If no, could you please provide me with a link to the prove?

$\endgroup$

closed as too broad by Kyle Kanos, ZeroTheHero, Jon Custer, Yashas, sammy gerbil Jun 10 '17 at 10:45

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

3
$\begingroup$

As fs137 answered, a quantum computer can simulate a classical computer, and so from a purely complexity theory perspective, the classical computer is never superior to the quantum in an asymptotic sense (assuming $P\subset BQP$, currently an open question).

However, quantum computers currently operate with very low numbers of qubits (ruling out adiabatic QC like D-Wave) relative to classical computers with classical bits. Thus, we are not currently in a time where quantum computers can work at a scale where these asymptotics take over. Since quantum computers have a very large overhead to perform an operation that's comparatively simple on a classical computer, they have very large constant factors that dominate for small computations. Any single operation that a classical computer can perform, it will likely be much slower on a quantum computer.

With this in mind, classical computers dominate at small numbers of bits from a practical perspective. However, as we begin to scale the number of bits up, and we are solving a problem with a known quantum algorithm that improves upon the best known classical algorithm, we will see that a quantum computer can finish computations faster because it is executing an entirely different algorithm than the classical computer.

$\endgroup$
2
$\begingroup$

You can simulate a classical computer on a quantum computer (with essentially no overhead), but not vice versa. Here's a link to a list of quantum gates that have been found to be useful: https://en.wikipedia.org/wiki/Quantum_gate If you look close to the bottom, you can find an implementation of the quantum Toffoli gate.

$\endgroup$
-3
$\begingroup$

I would also like to point out, that quantum computer does not allow for the copying of quantum bits. (https://en.wikipedia.org/wiki/No-cloning_theorem). So, for storing data the classical computer is better.

$\endgroup$
  • 3
    $\begingroup$ This answer is misleading. The No Cloning theorem forbids a device that makes full copies of an arbitrary quantum state, including superpositions. However, if you have a guarantee that your state is in the computational basis, it's perfectly possible. As the other answers note, classical computers are a subset of quantum computers, so this is not an issue. $\endgroup$ – Emilio Pisanty Jun 9 '17 at 20:51

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