Universität Augsburg

Professor Dr. Robert König
Technische Universität München
spricht am
Donnerstag, 7. Februar 2019
um
16:00 Uhr
im
TUM, Boltzmann3, Garching, Raum 03.08.011, Etage 3
über das Thema:
Abstract: 
Quantum effects can significantly enhance informationprocessing capabilities and speed up the solution of certain computational problems. Whether a quantum advantage can be rigorously proved in some setting or demonstrated experimentally using nearterm devices is the subject of active debate. Here we show that parallel quantum algorithms running in a constant time are strictly more powerful than their classical counterparts: they are provably better at solving certain linear algebra problems associated with binary quadratic forms. Our work gives the first unconditional proof of a computational quantum advantage and simultaneously pinpoints its origin: it is a consequence of quantum nonlocality. The proposed quantum algorithm is a suitable candidate for nearfuture experimental realizations as it requires only constantdepth quantum circuits with nearestneighbor gates on a 2D grid of qubits. 
Hierzu ergeht herzliche Einladung. 