[Solved]: Quantum computers and computable functions

Problem Detail: 

A quantum computer can possibly calcluate computable functions faster, but it can't calculate functions which a normal computer can't calculate?

If a function is not computable? Does this mean it will never be computable? Even if we change the axioms which our mathematical system is based on or we find a contradiction in it? Are we never be able to find something in the universe which can calculate these functions?

Is that right?

Asked By : user3613886

Answered By : Artem Kaznatcheev

You are correct, a quantum computer defined properly: with a finite gate set and rational (you can relax this to algorithmic, but that can be bit circular) transition probabilities will get you only the computable (by a classical Turing machine) functions. Although it might compute them faster than a classical computer.

To get a hyper-computer (something that computes functions that are not computable by a classical Turing machine), you need to sneak something that usually feels 'non-finitary' into the model -- the most common suspect is a non-computable real number -- which your model then extracts its power from. You can make these sort of models of computation from modifying classical or quantum systems. If I recall correctly, the first definitions of quantum TMs were actually accidentally hyper-computing because they allowed non-algorithmic phases in their operators.

To turn to your last question of "Does this mean it will never be computable?", what you are asking about is the Church-Turing thesis. It states, in its vaguest form, that anything that is computable is computable by a Turing Machine. Most people believe this thesis.

Even if we change the axioms which our mathematical system is based on or we find a contradiction in it?

Here you are asking about Kleene's variant of the Church-Turing thesis. Since the CT-thesis cannot be 'proven' (we can always continue to disagree about the first 'computable' in the vague definition), we have to rely on mathematician's beliefs and philosophical discussion. Most mathematicians believe that in any reasonable axiomatic system, any 'finite-feeling' model of computation will be at most Turing-complete.

Are we never be able to find something in the universe which can calculate these functions?

It is important to note that here you are asking a completely different (but related) question than the previos. You are asking about the physicalist variant of the Church-Turing thesis. Although historically this was not the preferred interpretation of the CT-thesis, from my experience it is now the most common way of reading the thesis. Again, here most computer scientists and physicists familiar with CS believe that all functions computable by machines in the physical world are Turing-computable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37299