Berlin 2014 – wissenschaftliches Programm
AGPhil 2.3: Vortrag
Mittwoch, 19. März 2014, 17:30–18:00, SPA SR22
Quantum and Classical Computation: Foundational Issues besides the Speed-up — •Filippo Annovi — Department of Philosophy, University of Bologna, Italy
The divide between quantum and classical computation does not concern which tasks can be performed, but the amount of resources necessary to achieve them. Does this entail that the computational divide is only relevant from a practical point of view, but not from a foundational one? No, because both the formal structure of quantum computers (based on the properties of Hilbert spaces) and the physical tools used by them (e.g. entangled states) are not classically available, thus the differences between quantum and classical computation go beyond complexity questions: the divide would remain in place even in the extremely unlikely case that the discovery of new classical algorithms were to nullify the quantum speed-up.
Moreover, there exist alternative equivalent models of quantum computation, some of which, like the cluster-state model, make an essential use of classical resources. Then, while the "where does the quantum speed-up come from?" question can satisfyingly receive a different answer for each model, the "where does the quantum-classical computational divide lie?" question requires an unified answer. This could be the first step towards a "representation theorem" for quantum computation, which would turn out to be very fruitful for the debate over the foundations of quantum mechanics.