Apologies if this is a silly question. But I've heard quantum computers can solve problems that classical computers can't. What about the converse, are there any problems that a classical computer can solve and a quantum computer can never solve?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ From the article you cite: "For one, theoretical computer scientists already knew that quantum computers can solve any problems that classical computers can." Also check the complexity map they give further down the page. $\endgroup$– seraliJul 17, 2021 at 9:45
-
3$\begingroup$ related: quantumcomputing.stackexchange.com/q/23/55, quantumcomputing.stackexchange.com/q/9951/55 and links therein $\endgroup$– glS ♦Jul 17, 2021 at 9:58
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
The classical computer only manipulates logic 0 and logic 1, composing the essence of the logical circuit. So the question that classical computers can solve is merely by manipulating logic 0 and logic 1, while quantum can easily mimic it by only manipulating $|0\rangle$ and $|1\rangle$. So I think there does not exist any question that classical computers can solve while the quantum computers cannot.
-
1$\begingroup$ Nice answer (+1), but I would add that you also need a tool to manipulate qubits in the same way as on a classical computer. Such tool is Toffoli gate - see my answer below. $\endgroup$ Jul 18, 2021 at 16:52
$\begingroup$
$\endgroup$
Some additional ideas to narip's answer.
Consider a gate-based quantum computer. Such computer allows to implement so-called Toffoli's gate which under specific circumstances (in particular when input to target qubits is $|1\rangle$) behaves like logical gate NAND. Since NAND is a universal gate in classical computing, i.e. it allows to implement any Boolean function and thus any algorithm, also quantum computer is able to perform any classical algorithm.
Another question is speed of the algorithm. When the classical algorithm is implemented with Toffoli's gates (i.e. "quantum NANDs"), its complexity is preserved. In other words, the algorithm runs on a quantum computer at least as fast as on a classical one. Of course, in terms of a O-notation, actual execution time is another question and it depends on speed of quantum gates.
Adding a Hadamard gate to Toffoli's gate we get a universal set of gates for performing any quantum algorithm (note that there are also others sets of universal gates - e.g. set composed of H, T and CNOT gates). Under such setting, we can reach a speed-up for some problems - factoring (Shor's algortihm), linear systems solving (HHL algorihtm), database search (Grover's algoritm) or Monte Caro simulations in finance. While the first two algorithms have exponential speed-up, the latter two have only quadratic. Moreover, there are problems, like evaluation of a binary function parity, where a quantum computer does not bring any advantage.
answered Jul 18, 2021 at 16:51