On the completeness of quantum computation models

Date: 
Thursday, April 15, 2010 - 16:00 - 18:00
Speaker: 
Gilles Dowek (LIX, École Polytechnique, TypiCal)
(Joint work with Pablo Arrighi) The notion of computability is stable (i.e. independent of the choice of an indexing) over infinite-dimensional vector spaces provided they have a finite ``tensorial dimension''. Such vector spaces with a finite tensorial dimension permit to define an absolute notion of completeness for quantum computation models and give a precise meaning to the Church-Turing thesis in the framework of quantum theory.