The interaction of computational complexity and quantum physics touches a wide range of topics from emerging technologies such as quantum computers to the physics of black holes. While tools from quantum information theory can help to answer questions in theoretical computer science, conversely, the ideas developed for analyzing the power of classical computers can shed light on physical phenomena. Deeply intertwined with both, quantum theory and the theory of complexity, is randomness. Indeed, quantum theory is a probabilistic theory and can predict, in general, only expectation values for observables. In the theory of algorithms, randomness is not only a key design primitive but also indispensable as a proof technique. In this thesis we make advances at the intersection of randomness, complexity and quantum theory. This includes a mathematical analysis of random ensembles of tensor network states, leading to new results on the average-case complexity of tensor network contraction, contributions to the foundation of verifiable quantum supremacy experiments as well as novel bounds on the generation of quantum pseudorandomness. In particular, we show that unitary t-designs can be generated with a system-size independent number of non-Clifford resources and that random quantum circuits generate designs in depth O(nt^(5+o(1))). These results have numerous applications including the best bounds on the growth of operational notions of quantum circuit complexity. Moreover, we provide a proof of the Brown-Susskind conjecture for the linear growth of exact circuit complexity in random quantum circuits. The majority of the results in this thesis are theorems published in academic journals. The tools exploited for this analysis range from the concepts of theoretical computer science, such as complexity classes, over ideas from harmonic analysis and Markov chains to the techniques of quantum many-body physics. In an appendix, this thesis contains several unpublished results such as the first non-trivial upper bounds on moments of the permanent and generation of quantum pseudorandomness with random measurements on the cluster state.
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.
