18
$\begingroup$

On the Wikipedia page for quantum algorithm I read that

[a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable using classical computers remain undecidable using quantum computers.

I expected that the fundamental changes that a quantum computer brings would lead to the possibility of not only solving problems that could already be solved with a classical computer, but also new problems that could not be solved before. Why is it that a quantum computer can only solve the same problems?

Improve this question
$\endgroup$
11
  • 6
    $\begingroup$ "the fundamental changes that a quantum computer brings" -- apparently that's the fallacy. There don't seem to be as fundamental changes as you think. $\endgroup$
    – Raphael
    Jul 29, 2015 at 9:36
  • 2
    $\begingroup$ @Raphael, could you elaborate? $\endgroup$
    – user2609980
    Jul 29, 2015 at 11:27
  • 6
    $\begingroup$ the open questions about quantum computers (and there are many still) are about their "speed" wrt classical computers which that excerpt is not referring to. quantum computers do not defy the Church-Turing thesis about the nature of computation. $\endgroup$
    – vzn
    Jul 29, 2015 at 15:01
  • $\begingroup$ Any problem that can be solved, can be solved by a classical computer. If the product cannot be solved, then it cannot be solved by anything - whether it be classical, quantum or powered by magical unicorns. The only benefit of quantum computing, is that it can solve the problems faster. $\endgroup$
    – Benubird
    Jul 30, 2015 at 10:11
  • $\begingroup$ @Benubird "Any problem that can be solved, can be solved by a classical computer." That is not something we know to be true. $\endgroup$
    – David Richerby
    Jul 30, 2015 at 22:22

5 Answers 5

Reset to default
23
$\begingroup$

Because a quantum computer can be simulated using a classical computer: it's essentially just linear algebra. Given a probability distribution for each of the qubits, you can keep track of how each quantum gate modifies those distributions as time progresses. This isn't very efficient (which is why people want to build actual quantum computers) but it works.

Improve this answer
$\endgroup$
10
  • $\begingroup$ What about continuity? I mean quantum probabilities and time for its evolution are tought to be continuum, so that's mean we can not simulate exaclty by discrete values and discrete time, then that could rise a difference (in the case scalable QC could even be builded) $\endgroup$
    – Hernan_eche
    Jul 29, 2015 at 13:12
  • $\begingroup$ @Hernan_eche The problem definition for a decision problem class like BQP, the class of problems solvable in polynomial time with a quantum computer with an error rate of 1/3 or less, puts limits on which states within that presumed continuum are actually reachable, other than through noise (whose effect can be simulated classically). QM waveforms evolve over the continuum, but the decision problem format doesn't leverage it in its entirety. $\endgroup$
    – Cort Ammon
    Jul 29, 2015 at 16:34
  • 1
    $\begingroup$ @Hernan_eche you can simulate down to any accuracy you want. You can't realize unlimited accuracy with a real quantum computer anyhow, so nothing stops a non-quantum simulation from being "good enough". $\endgroup$
    – hobbs
    Jul 29, 2015 at 16:35
  • 1
    $\begingroup$ @Hernan_eche Noise in the gates and in the measurements prevents you from really using the continuity, same as for classical analog computers. $\endgroup$
    – Craig Gidney
    Jul 30, 2015 at 19:24
  • $\begingroup$ It might be useful to provide a link with the details spelled out. Wikipedia gives: Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information. p. 202. $\endgroup$
    – cody
    Aug 4, 2015 at 22:00
11
$\begingroup$

Classical computers are already Turing complete, i.e. they can calculate everything that a Turing machine can (a theoretical computer model from Computer Science). According to the Church–Turing thesis Turing completeness includes all functions which can be calculated using any mechanical process. So if this thesis is true, any computer you could possibly build could never solve more problems than a classical one (disregarding efficiency).

P.S.: Even if you could build a computer that would solve more problems that a classical one, you would never know if that machine is working correctly, because if the machine could generate a proof for the solution for every input verifiable by a classical computer (or a turing machine or a human), the classical computer could just create all possible texts until one text describing such a proof is found.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Are there problems that can be solved by a process that is is not mechanical? If so, what about them? PS I do not completely understand what you mean with your post scriptum. Is that an example of such a non-mechanical process? $\endgroup$
    – user2609980
    Jul 29, 2015 at 12:09
  • $\begingroup$ I guess with mechanical they mean actual, physical process (as in, in this universe) in contrast to a theoretical one. With the PS I mean that even if such a thing as a more powerful classical computer would exist it would not help you as you could never verify whether it was working correctly. $\endgroup$
    – Konrad Höffner
    Jul 29, 2015 at 12:15
  • 4
    $\begingroup$ I think you're conflating the so-called "physical Church-Turing thesis" with the regular one. The physical thesis is rather stronger and states, as you say, that any physically realizable computing system can be simulated by a Turing machine. Church and Turing just said that, essentially, any reasonable model of computation would correspond to Turing machines (albeit that they didn't use most of those actual words). $\endgroup$
    – David Richerby
    Jul 29, 2015 at 12:52
  • $\begingroup$ Thanks for the correction! I didn't know that two types of that thesis exist. $\endgroup$
    – Konrad Höffner
    Jul 29, 2015 at 13:49
1
$\begingroup$

Actually, it depends of what you mean by "solving a problem". As previously stated, a classical computer is already Turing complete and can decide any decidable problem in finite time. There is no such thing of a computer able to decide an undecidable problem in finite time (that would actually lead to a contradiction).
[Edit: as David Richerby stated in the comments, that hasn't been proved (only conjectured)
However most of the undecidability proofs can be repeated for any reasonable kind of computer (this doesn't prove the conjecture, but in my opinion it's a good hint)
The good argument regarding why a quantum computer couldn't decide more problems than a classic Turing machine has already been given by David Richerby (you can simulate a quantum Turing machine with a classical Turing machine)]

Hence a classical computer can theoretically solve any "reasonable" problem... given enough time (it will be finite, it doesn't mean it will be fast).

The wikipedia quote doesn't talk about time at all, and a quantum computer is expected to solve some problems faster than a classical computer. By "faster", i mean that some problems which would have taken millenia to decide on a classical computer could be solved in minutes on a quantum computer (provided such a computer can be built, we don't know for sure yet, although there are promising results, and provided BQP != BPP which is a weaker hypothesis than NP != P if i'm not mistaken).

For instance, the famous Shor's algorithm shows that factoring an integer in its prime factors is in BQP (Bounded error Quantum Polynomial time) whereas that problem isn't believed to be in P (Polynomial time) or BPP (Bounded error Probabilistic Polynomial time). That doesn't mean factoring an integer on a classical computer is impossible, but it will be a time consuming task, and for sufficiently big numbers the computation may exceed any reasonable time limit (like the age of the universe; of course that's true of almost any computation given a sufficiently big entry, but that would happen much faster for problems outside of BPP on a classical computer than for problems inside of BPP).

So, even though all decidable problems can be solved on classical computers, some problems are still practically out of reach because of unreasonable computation times. A quantum computer may allow us to decide such problems in more reasonable time.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ "There is no such thing of a computer able to decide an undecidable problem in finite time (that would actually lead to a contradiction)." We don't know that to be true. Church-Turing is a thesis, not a theorem. We don't know that no physical device can decide problems not decidable by Turing machines. $\endgroup$
    – David Richerby
    Jul 29, 2015 at 15:10
  • 2
    $\begingroup$ You're right that was a too strong. However, even though I can't prove the thesis (obviously), given reasonable properties about the "computer" (mainly the ability to simulate itself running a program and to compose) the undecidability proofs are basically the same (as far as i know). That may be a good hint, and new computer designs should be supposed not to be able to compute undecidable problems for Turing machines unless proven otherwise for that reason. Still you're right, that was too strong, i'll edit it. $\endgroup$
    – Caninonos
    Jul 29, 2015 at 15:48
1
$\begingroup$

The roadblock to more powerful computers isn't speed; it's space. Technically, classical computers aren't even really equivalent to Turing machines. The reason for this is that a Turing machine has an infinite tape, and although we can simulate very large tapes, we can't go infinite. This matters more than you might think. There are entire classes of problems where we know how they could be solved if we had infinite space to work with, but are currently stymied in actually solving them by the finite-space problem. There are other problems that we can currently solve slowly, but could be solved much more quickly if we had infinite space.

A Turing-like machine with a finite tape (the thing we're usually really simulating when we talk about "Turing machines" in this context) is called a linear bounded automaton, and it's a closer match for classical computing than true Turing machines are. However, the difference between finite and infinite is pretty stark: LBAs just plain aren't as powerful as true Turing machines.

Quantum computers don't solve the finite-space problem, and they don't try to. They can tackle many computations at once, but we can already simulate that on classical machines. Quantum machines don't do more; they just do it faster.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I'm not sure this answers the question. The question talks about decidability, which means it's implicitly asking about Turing machines (where the halting problem is undecidable) rather than real computers (which have a large but finite state space so their halting problem is decidable, though there aren't enough resources in the universe to do the computations). Also, note that a Turing machine doesn't need infinite tape: it just needs to be able to stop and say "Give me more tape so I can continue." $\endgroup$
    – David Richerby
    Jul 30, 2015 at 16:48
-5
$\begingroup$

One thing that quantum computers should be able to do that regular computers will never do is to use quantum entanglement.

Quantum entanglement is a property that allows to communicate instantly across the whole universe, without transmitting anything. The communication cannot be intercepted or tampered with. Also I can communicate several chips. This means that I can communicate the CPU with the RAM and with the SSD instantly.

So you could have super fast computers. And if I buy some special chip, for example from Amazon Quantum Web Servers, then I could use their infrastructure to perform computations AS IF they were running on my machine... no communication overhead... at least theoretically...

Having a CPU perform all computations in parallel like solving the traveling salesman problem... that makes no sense... if a CPU could do that, all possible results would come out at once... a giant map reduce done in a single chip... how do I pick the right answer?

I mean if the correct answer is 5, but it spells out 5,6,7,8,9,10,15,20,30,40,50,60,70,80... etc. at the same time, how can I know that the correct value is 5?

Improve this answer
$\endgroup$
2
  • 8
    $\begingroup$ 1) Even quantum entanglement doesn't give you instant communication. 2) This question is about what can be computed, not about communication or how fast the computation is. $\endgroup$
    – CodesInChaos
    Jul 29, 2015 at 14:28
  • 8
    $\begingroup$ This is incorrect. Quantum entanglement doesn't allow you to transmit arbitrary amounts of data instantly. In particular, you need to prepare an entangled state for each data item you wish to communicate. If you then physically separate the two halves of the entangled state, you can transmit one data item between the locations you put them in. But you need to physically move the entangled objects for that to happen, and that physical movement is limited by the speed of light. $\endgroup$
    – David Richerby
    Jul 29, 2015 at 14:45

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