2
$\begingroup$

Henry Yuen's youtube comment on this video https://www.youtube.com/watch?v=HL7DEkXV_60 (should be one of the top comments) explains that with the help of quantum entanglement (or quantum computers), it is possible to solve a problem that has been proven to be unsolvable by a turing machine.

Does that mean quantum computers are effectively hypercomputers more powerful than turing machines?

If indeed we found out that they are, would that mean that we, humans, were able to find a way to surpass the Turing barrier, meaning the human mind is more powerful than a turing machine, making us effectively hypercomputers?

Improve this question
$\endgroup$
2
  • $\begingroup$ Nobody said that a human brain works like a quantum computer. It might just work like a regular computer $\endgroup$
    – nir shahar
    Jul 2 '21 at 16:09
  • $\begingroup$ @nirshahar Of course nobody said a human brain works like a quantum computer, even I didn't imply that. However, if a human is ever able to conceptualize a way to break the Turing barrier, they are automatically considered to be a hypercomputer, by definition. $\endgroup$
    – Alex
    Jul 2 '21 at 17:30
5
$\begingroup$

To summarize: No, this paper does not provide an example of something a quantum computer can compute that a Turing computer can't.

I believe you have misunderstood Henry's comment. The problem in question isn't the halting problem (given any Turing machine and input, will it halt). Rather, the problem is to prove that a program halts, given that it halts. As Henry describes, there is a simple means of solving this problem that Turing computers are capable of-They can list out the steps leading to the program's halting.

What the quantum computer can do that the Turing computer can't is the following. Given a Turing computer and input that halts, once the quantum computer knows that the process halts (which can take arbitrarily long to determine by itself), it can provide proof that the process halts in constant time.

Key points: This problem has no relevance to solving the halting problem, because the quantum computer needs to know that the process halts to proceed. Turing computers can also solve this problem, but the time to provide an answer can be arbitrarily long for given inputs.

To your bonus question about humans surpassing Turing computers if we solve a problem they can’t: In theory, the answer is yes, but it is quite hard to do so. To prove that a computer (Turing or human) can solve a problem, you must prove that they can solve it for all inputs. Our current rules of mathematics are describable by a Turing computer, so we would need to provide this proof with something that transcends current mathematics. Additionally, solving the problem for some inputs is not proof we can solve it for all inputs.

Secondly, a very substantial implication of the answer being yes would be that either: Turing computers cannot simulate the laws of physics, or the laws of physics do not fully describe the function of the human brain. As it currently stands, it seems that both of those aren't true - physics fully explains the human brain, and a quantum computer can simulate the laws of physics. (It is 100% true that a quantum computer can simulate our current laws of physics, while it is likely that it can simulate whatever the true laws of physics are).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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