In dieser Arbeit zeigen wir, dass das Lernen der Ausgabeverteilungen von Mauerwerks-zufälligen Quantenkreisen im statistischen Abfragemodell durchschnittlich schwer ist. Dieses Lernmodell wird häufig als abstraktes Rechenmodell für die meisten generischen Lernalgorithmen verwendet. Insbesondere für Mauerwerks-zufällige Quantenkreise mit n Qubits und einer Tiefe von d zeigen wir drei Hauptresultate:– Bei überlogarithmischer Schalttiefe d=(log(n)) benötigt jeder Lernalgorithmus überpolynomiale viele Abfragen, um eine konstante Erfolgschance über die zufällig gezogene Instanz zu erreichen.– Es existiert ein d=O(n), sodass jeder Lernalgorithmus (2n) Abfragen benötigt, um eine O(2n) Erfolgschance über die zufällig gezogene Instanz zu erreichen.– Bei unendlicher Schalttiefe d benötigt jeder Lernalgorithmus 22(n) viele Abfragen, um eine 22(n) Erfolgschance über die zufällig gezogene Instanz zu erreichen. Als Hilfsergebnis von unabhängigem Interesse zeigen wir, dass die Ausgabeverteilung eines Mauerwerks-zufälligen Quantenkreises konstant weit von jeder festen Verteilung in totaler Variation entfernt ist mit einer Wahrscheinlichkeit von 1O(2n), was eine Variante einer Vermutung von Aaronson und Chen bestätigt.
Nietner et al. (Mon,) haben diese Frage untersucht.