Die Theorie der Quantenalgorithmen

Andreas Klappenecker, Martin Rötteler

Seit der Entdeckung von effizienten Quantenalgorithmen für das Faktorisieren von ganzen Zahlen und für die Berechnung von diskreten Logarithmen durch Shor in 1994 wuchs das Interesse an Quantenalgorithmen innerhalb der theoretischen Informatik- und der Physik-Gemeinde. Überraschenderweise ist die Anzahl der Quantenalgorithmen, die bisher entdeckt wurden, vergleichsweise gering, obwohl die Anzahl der Forscher, welche an diesem Gebiet arbeiten, stark angestiegen ist. Die Aufgabe, neue Quantenalgorithmen zu entwerfen, hat sich in der Tat als extrem schwierig herausgestellt. Wir geben einen kurzen Überblick über eine Auswahl von Problemen, für welche effiziente Quantenalgorithmen bekannt sind, und beschreiben kurz die zu Grunde liegenden Ideen. Ein großes Gebiet, bei dem ein Quantenrechner allen klassischen Rechnern überlegen zu sein scheint, sind die verborgenen Untergruppenprobleme. Wir erklären deren Relevanz und geben Motivation für diese abstrakte Problemklasse.

Florian A. Scheck

Werner Vogd

Thomas F. Sturm, Jörg Schulze

Nach einer physikalischen Betrachtung der Quantenmechanik werden zunächst die benötigten mathematischen Grundlagen eingeführt bzw. wiederholt: Vektorräume, darauf aufbauend Hilberträume und die Tensorrechnung, gefolgt von den Grundlagen der Wahrscheinlichkeitsrechnung. Auf diesen Grundlagen wird ein Quantencomputer insoweit modelliert, wie es für die Formulierung von Algorithmen notwendig ist, d.h. als mathematisches Modell der Quantenbits, der Zeitentwicklung durch Gates und der abschließenden Messungen. Auf diesem Modell werden dann die klassischen Quantenalgorithmen jeweils vollständig eingeführt und erklärt. Schließlich wird die denkbare Umsetzung von Quantenalgorithmen auf heute existierende klassische Computer diskutiert.

Tim Schwägerl

Tensornetzwerke ermöglichen eine effiziente Simulation quantenmechanischer Vielteilchensysteme und gewinnen zunehmend an Bedeutung in der Quanteninformationswissenschaft und der Gittereichtheorie. In dieser Dissertation dienen sie als einheitliches numerisches Werkzeug für zwei Untersuchungen: die Studie variationeller Quantenalgorithmen für kombinatorische Optimierungsprobleme und die Analyse der Skalierungseigenschaften verschiedener Fermiondiskretisierungen im Zwei-Flavour-Schwinger-Modell. Der erste Teil untersucht flache variationelle Quantenschaltkreise für kombinatorische Optimierungsprobleme. Mithilfe von Tensornetzwerksimulationen führen wir eine systematische Benchmark-Studie für Max-Cut- und QUBO-Instanzen durch und vergleichen die Ergebnisse bei festem Ressourcenbudget mit klassischen Referenzverfahren, insbesondere zufälligem Ziehen mit Zurücklegen und lokaler Suche. Wir bestimmen die minimalen Problemgrößen, ab denen Quantenalgorithmen das zufällige Ziehen zuverlässig übertreffen, und analysieren Korrelationen der Ergebnisse auf Instanzebene. Der zweite Teil widmet sich den Skalierungseigenschaften von Staggered-, Wilson- und Twisted-Mass-Fermionen in der Hamiltonschen Gittereichtheorie, wobei das Zwei-Flavour-Schwinger-Modell als Referenz dient. Wir bestätigen die erwartete O(a)-Verbesserung für Twisted-Mass-Fermionen in der freien Theorie und finden Evidenz dafür, dass sie im wechselwirkenden Fall erhalten bleibt. Nach Massenrenormierung konvergiert die Pionenmasse rasch gegen den Kontinuumsgrenzwert. Twisted-Mass-Fermionen zeigen deutlich reduzierte Volumeneffekte sowie charakteristische Verletzungen der Isospin-Symmetrie. Insgesamt demonstrieren diese Ergebnisse die Vielseitigkeit von Tensornetzwerksimulationen für Quantenoptimierung und Gittereichtheorien.