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.
