Proving The Church-Turing-Deutsch Principle

[n01]

Linked below is the paper detailing Deutsche's Church-Turing-Deutsch principle.

http://www.daviddeutsch.org.uk/wp-content/deutsch85.pdf

In it Deutsch makes the assertion:

"For although a quantum computer has an infinite-dimensional state space, only a finite dimensional unitary transformation need be effected at every step to simulate its evolution."

Can anyone elucidate how this can be known to be true? This seems like a very complex statement that requires some complex justification

Thanks.

 

[Zafa Pi]

Linked below is the paper detailing Deutsche's Church-Turing-Deutsch principle.

http://www.daviddeutsch.org.uk/wp-content/deutsch85.pdf

In it Deutsch makes the assertion:

"For although a quantum computer has an infinite-dimensional state space, only a finite dimensional unitary transformation need be effected at every step to simulate its evolution."

Can anyone elucidate how this can be known to be true? This seems like a very complex statement that requires some complex justification

Thanks.

I'm confused, a recurring affliction. I thought the input to a q-computer was a finite number of qbits, each of which is 2D. And a finite number of gates.

 

[n01]

I'm confused, a recurring affliction. I thought the input to a q-computer was a finite number of qbits, each of which is 2D. And a finite number of gates.

Yes, but if a Q computer occupies an infinite state space doesn't that mean that equally an infinite state space must be simulated? Same confusion on this end.

 

[secur]

If you incorrectly treat "infinity' as something that exists in the real world you will get confused. Paradoxes are inevitable. That's why mathematicians worked out methods to deal with the concept of infinity, such as epsilon-delta definition of limit (Cauchy, Weierstrass). Math deals with the concept of infinity, not "infinity" itself, which has no meaning apart from finite formal limit definitions. The simplest example, we say a sequence "goes to infinity" if, for any N, we can produce a member of the sequence which is greater than N. When dealing with infinity, if you can't express what you mean by a finite limit algorithm like this, you literally don't know what you're talking about.

This is what we mean by an "infinite-dimensional" space: given any finite number N, I can demonstrate that the number of axes or dimensions in the space is greater than N. You might think otherwise. The position operator, for instance, has "infinite" eigenvalues simply because it's defined on the real number line. That doesn't seem to involve a finite definition like epsilon-delta. But, in fact, the mathematical underpinnings of all "infinities" are expressible in a finite algorithm. In this case, Cantor's diagonal proof, which demonstrates the real line's "order of infinity" (uncountable).

So when simulating (or calculating, or even just considering) evolution of a system, Deutsch is correct that "only a finite dimensional unitary transformation need be effected" - because nothing else can possibly be effected by a real-world simulation.

 

[n01]

Disregard.