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, Boltzmann-3, Garching, Raum 03.08.011, Etage 3
über das Thema:
Abstract: |
Quantum effects can significantly enhance information-processing 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 near-term 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 near-future experimental realizations as it requires only constant-depth quantum circuits with nearest-neighbor gates on a 2D grid of qubits. |
Hierzu ergeht herzliche Einladung. |