Robert König (München): Algorithms for noisy quantum hardware: Can-Dos and Can't-Dos

Montag, 17. Juni 2019, 10:45 Uhr, Lehrprobe 11:30 Uhr

Institut für Organische Chemie, Seminarraum 3 / ORC_SR, Boltzmanngasse 1, 1. Stock

In recent work (Science vol. 362, no. 6412, Oct 2018) we have established the first provable separation between analogously defined classical and quantum complexity classes: There is a computational problem which can be solved with certainty by a constant-depth quantum circuit, but cannot be solved with bounded error by a classical circuit unless its depth scales at least logarithmically in the problem size. We ask if this complexity-theoretic result can be strengthened to apply to realistic settings: Available quantum devices are affected by noise, and are typically limited in size and/or connectivity of interactions. Is there a way of demonstrating a quantum advantage of such non-ideal devices? I will discuss why standard fault-tolerance approaches are unsuitable to address this problem, and present a fault-tolerant quantum advantage scheme using a 3D architecture. There is partial evidence suggesting that analogous schemes using a lower spatial dimension may not exist: This is related to fundamental limitations on protected gates.

Im Rahmen des Vortrages findet eine Lehrprobe zum Thema "The concept of information in mathematics and physics" statt.


Fakultät für Chemie, Seminarraum 3, Boltzmanngasse 1 - 1. Stock, 1090 Wien

Foto: Joseph Krpelan