8
$\begingroup$

I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve. In my understanding, this should mean, intuitively, that this problem is "effectively computable", since we have an effective, real method to compute it: build a quantum computer and solve it. But, since a Turing Machine (turing machines are not quantum computers, I think?) can not solve it, this is not turing-computable.

Hence, does this mean that "effectively computable" and "turing-computable" are not the same concept? So, is the Church-Turing thesis wrong? My intuition says "no", because in that case, this would be very big news. So, if not, why not?

Also, I am aware that there exist already models of computation that are more powerful than turing machines, but those are only "theoretic", aren't they? Quantum computers, on the other hand, could be physically buildable.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
14
$\begingroup$

There are many different meanings of the word "can". Is there an algorithm that can break AES-512 encryption? One strategy would be to take all 2^512 possible blocks of 512 bits, encrypt all of them with the public key, and for each of them check whether they match the ciphertext. In a purely abstract sense, this is an algorithm that "can" break AES-512. From a practical point of view, converting all the matter in the known universe into computers, and running the program on them until the heat death of the universe, would not be able to check all 2^512 blocks.

Thus, there's an abstract, theoretical concept of "can" that does not take into account the amount of resources required, and a practical meaning that does.

Turing Computability is concerned with the first type of "can". A Turing machine is a device that is allowed to run for unlimited time with unlimited memory. It is an abstract model used to formulate theoretical claims. No true TM actually exists in the real world.

Thus, there is no contradiction between claiming, on the one hand, that anything a quantum computer can do, a TM can also do, and on the other hand claiming that there are problems that a quantum computer can solve, but no classical computer can solve; an actual computer will have computer power restrictions that a TM does not have.

Improve this answer
$\endgroup$
0
18
$\begingroup$

First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they're talking about.

The difference between quantum computers and classical ones is speed. This is where complexity theory comes in. Here, we want to know more than just whether a problem is computable. Most problems considered by this field are computable, but some may be very inefficient to solve in terms of asymptotic running time or memory usage.

The polynomial Hierarchy (PH) is a big class that contains problems which are basically an alternating game between non-deterministically guessing a solution and finding one (or rather, alternating existential and universal quantifiers), but all in polynomial time. P is the most basic class inside the PH and roughly corresponds to problems we can solve in reasonable time on classical computers. NP is another basic subclass of PH.

BQP is the analogue for P for quantum computers. Well, not entirely, BQP is closer to BPP, where we allow our classical computer to give a wrong answer with only small probability. The quantum effects cannot really be exploited without involving probability in a meaningful manner. In any case, BPP is still within PH.

This article is about a problem that has been proven to not lie in PH, but in BQP. In a way, the 'quantum step' allows to solve a problem that isn't even close to P or BPP classically, not even in the same infinite hierarchy, in polynomial time on a quantum computer. So, this is strong evidence for the (theoretical) power of the quantum computing model.

As for the Church-Turing thesis, quantum computation being faster than classical does not contradict it, as the thesis does not care about computation time. The stronger Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)

Improve this answer
$\endgroup$
3
  • $\begingroup$ But then why it says "That Only Quantum Computers Will Ever Be Able to Solve" and "Raz and Tal’s proof demonstrates that there would still be problems only quantum computers could solve."? $\endgroup$
    – olinarr
    Commented Apr 30, 2019 at 15:30
  • 6
    $\begingroup$ Because realistically, while something may be computable, but takes longer than the age of the universe to finish, it's not going to be solved. It is not that much of a stretch to call a problem outside of PH something we won't be effectively solving on a classical computer. $\endgroup$
    – Discrete lizard ♦
    Commented Apr 30, 2019 at 15:41
  • 1
    $\begingroup$ @NetHacker "Will Ever Be Able to Solve" can mean things other than "can't actually compute". Notably, you can write algorithms that provably would terminate and give the result you want, but that would take longer than the heat death of the universe to actually terminate. Problem is computable, but realistically a classical computer "Will Never Be Able to Solve". $\endgroup$
    – Delioth
    Commented Apr 30, 2019 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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