My angle at quantum computation


During my PhD I came across a quote [*] by the British physicist David Deutsch, and it has fascinated me ever since. The statement is

"[It is not] obvious a priori that any of the familiar recursive functions is in physical reality computable. The reason why we find it possible to construct, say, electronic calculators, and indeed why we can perform mental arithmetic, cannot be found in mathematics or logic. The reason is that the laws of physics 'happen to' permit the existence of physical models for arithmetic such as addition, subtraction and multiplication. If they did not, these familiar operations would be non-computable functions. We might still know of them and invoke them in mathematical proofs (which would presumably be called 'non- constructive') but we could not perform them.

And so, resulting from this stimulation, the question that interests me is this:

What are those quantum algorithmic elements of which, with hindsight, we might later say "without quantum technology, we may still know of them and invoke them in mathematical proofs, but we could not perform them"?


[*] D. Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. Roy. Soc. A 400, 97 (1985).