Abstracts Physics

Zufall und Komplexität in zufälligen komplexen Quantensystemen

by Jonas Haferkamp

Die Schnittstelle von Komplexitätstheorie und Quantenphysik umfasst Quantentechnologien bis hin zu fundamentalen Fragen über die Physik schwarzer Löcher. Während die Methoden der Quanteninformationstheorie dabei helfen können, Fragen in der Informatik zu beantworten, tragen algorithmische Ideen dazu bei physikalische Phänomene zu erklären. Sowohl in der Komplexitätstheorie als auch in der Quantentheorie ist das Konzept des Zufalls allgemeingegenwärtig. Für die Entwicklung neuer Algorithmen ist Zufall ein mächtiges Werkzeug und erlaubt oft effiziente Methoden, wo es keine schnellen deterministischen Lösungen gibt. Die Quantentheorie ist inhärent probabilistisch und erlaubt nur Vorhersagen über Erwartungswerte. In dieser Dissertation machen wir mehrere Fortschritte an der mathematischen Theorie dieser Schnittstelle. Das beinhaltet die Untersuchung von zufälligen Ensembles sogenannter Tensorproduktzustände, Komplexitätsresultate für den typischen Fall von Tensornetzwerken, rigorose Evidenz für verifizierbare Quantenüberlegenheitssexperimente und mehrere neue Schranken auf die Erzeugung von Quantenpseudozufall. Insbesondere zeigen wir, dass unitäre t-Designs mit einer systemunabhängigen Anzahl an nicht-Clifford Gattern erzeugt werden können und das zufällige Quantenschaltkreise t-Designs in einer Tiefe von O(nt^(5+o(1))) erzeugen. Diese Resultate haben zahlreiche Anwendungen und implizieren insbesondere die momentan besten Schranken auf das Wachstum fehlerrobuster Definitionen von Schaltkreiskomplexität. Letztlich enthält diese Dissertation einen Beweis der Brown-Susskind Vermutung für das lineare Wachstum der exakten Schaltkreiskomplexität in zufälligen Quantenschaltkreisen. Die Mehrzahl der Ergebnisse in dieser Arbeit sind mathematische Theoreme mit rigorosen Beweisen. Die Methoden für diese Analyse rangieren von den Konzepten der theoretischen Informatik, über harmonische Analysis und Markovketten zu den Techniken der Vielteilchentheorie. In einem Appendix enthält diese Arbeit mehrere unveröffentlichte Resultate wie die ersten nicht-trivialen oberen Schranken auf Momente der Permanente zufälliger Matrizen so wie die Erzeugung von Pseudozufall mit zufälligen Messungen auf Cluster-Zuständen.