Learning theory provides the structural framework for analysing the complexity of problems related to obtaining a description of some unknown object (such as an unknown function, a distribution, a quantum state or process) based on indirect access to it namely via \emph{data}. It is not difficult to see then that a great number of central questions in quantum information and computing can be seen through the lens of learning theory.
In this thesis we will be dealing with questions of this type. As the title suggests, we differentiate between those problems which take the quantum device and its internal workings as the subject of consideration and those in which the quantum device is seen as an integral part of the learning procedure while the object to be learned need not be quantum at all. Put differently, we will study and develop algorithms which allow us to obtain tomographic information about the inner workings of quantum devices on the one hand and study the potential of quantum devices as tools for developing faster learning algorithms.
Motivated by the quest for showing provable quantum advantages for quantum machine learning, we study the problem of learning quantum circuit output distributions. In contrast to what was colloquially expected, we show that this task is in fact hard even for quantum learners barring any meaningful quantum advantage. Even more surprisingly, we show that there exists a sharp transition between the complexity of the task with respect to the types of gates allowed in the circuit. When the circuit consists of purely Clifford gates there exists in fact an efficient algorithm for solving the problem. However, adding a single $T$-gate, as we will see, renders the task inefficient. Further, we show that this hardness is not merely an artefact of some outliers within the class of distributions but that the hardness holds also in the average case.
Obtaining sufficient tomographic information about a quantum device in order to evaluate its performance is an important building block within the engineering cycle which will cultimate in the development of large scale quantum computers. However, at the current point techniques such as quantum state and process tomography are way too costly to be of any practical use. With this in mind we turn our attention towards techniques to efficiently obtain information about the noise present in near term quantum devices. We begin by presenting a variation of the well known randomized benchmarking protocol which both provides more information from the same set of measurements compared to traditional randomized benchmarking. Building upon this general formulation we then develop a randomized benchmarking protocol for analog quantum devices. Switching gears we then focus on the scenario in which we want to verify the correct operation of quantum devices operating in removed locations and potentially completely different physical platforms. Operating within the framework of \emph{cross-device verification} we develop and analyse a protocol for this task based on distributed inner product estimation using Pauli-sampling.
Finally, we combine ideas to study the problem of verification in quantum learning. In particular we study the problem of learning given the chance to interact with an untrusted but more resourceful party. We study different aspects of this problem focusing on different modes of communication and resource discrepancies and finding limitations and possibilities to exploiting the additional resources in a provable manner.
Die Lerntheorie bietet den strukturellen Rahmen zur Analyse der Komplexität von Problemen, die mit der Beschreibung eines unbekannten Objekts (wie z.b einer unbekannten Funktion, einer Wahrscheinlichkeitsverteilung, einem Quantenzustand oder einem Prozess) durch indirekten Zugriff darauf – nämlich über \emph{Daten} – zusammenhängen. Man sieht direkt dass eine große Anzahl zentraler Fragen der Quanteninformationstheorie durch die Linse der Lerntheorie betrachtet werden können.
In dieser Dissertation befassen wir uns mit Fragen dieser Art. Wie der Titel andeutet, unterscheiden wir zwischen Problemen, bei denen der Quntencomputer und seine inneren Prozesse Gegenstand unserer analyse sind, und solchen, bei denen der Quantencomputer als integraler Bestandteil des Lernverfahrens gesehen wird, während das zu lernende Objekt nicht notwendigerweise quantenmechanischer Natur sein muss. Anders ausgedrückt werden wir einerseits Algorithmen untersuchen und entwickeln, die es ermöglichen, tomographische Information über die inneren Prozesse von Quantencomputern zu gewinnen, und andererseits das Potenzial von Quantencomputern als Werkzeuge zur Entwicklung schnellerer Lernalgorithmen analysieren.
Motiviert durch das Ziel, nachweisbare Quantenüberlegenheiten im Bereich des Quanten-Maschinelen lernens zu demonstrieren, untersuchen wir das Problem des Lernens von Wahrscheinlichkeitsverteilungen die durch Quantenschaltkreise generiert werden. Im Gegensatz zu der gängigen Erwartung zeigen wir, dass diese Aufgabe tatsächlich schwierig ist – selbst für Quantenalgorithmen –, wodurch jede bedeutsame Quantenüberlegenheit ausgeschlossen wird. Noch überraschender ist, dass es einen scharfen Übergang in der Komplexität der Aufgabe in Bezug auf die in den Schaltkreisen erlaubten Gatesets gibt. Wenn der Schaltkreis ausschließlich aus Clifford-Gates besteht, existiert ein effizienter Algorithmus zur Lösung des Problems. Ein einzigen $T$-gate jedoch führt schon dazu das dass Problem ineffizient wird. Darüber hinaus zeigen wir, das diese Schwierigkeit nicht nur ein Artefakt einiger besonders komplexen Wahrscheinlichkeitsverteilungen innerhalb der Klasse ist, sondern dass sie auch im Durchschnittsfall besteht.
Ausreichend tomographische Informationen über ein Quantencomputer zu gewinnen, um seine Leistung zu bewerten, ist ein wichtiger Baustein im Entwicklungszyklus, der letztlich zur Entwicklung skalierbarer Quantencomputer führen wird. Derzeit sind Techniken wie die der Quantenzustands- und Prozess-Tomographie jedoch viel zu aufwendig, um praktisch einsetzbar zu sein. Vor diesem Hintergrund wenden wir uns Techniken zu, die es ermöglichen, effizient Informationen über das Rauschen in gegenwärtigen Quanteninstrumenten zu gewinnen. Wir beginnen mit der Vorstellung einer Variation des bekannten randomised Benchmarking Protokolls, das im Vergleich zum traditionellen randomised Benchmarking mit derselben Menge an Messungen mehr Informationen liefert. Aufbauend auf dieser allgemeinen Formulierung entwickeln wir ein Protokoll für analoge Quantencomputer.
Dann konzentrieren wir uns auf das Szenario, in dem die korrekte Funktionalität von Quantencomputer verifiziert werden soll, die sich an entfernten Standorten befinden und möglicherweise auf völlig unterschiedlichen physikalischen Plattformen basieren. Im Rahmen des \emph{cross-device verification} entwickeln und analysieren wir ein Protokoll für diese Aufgabe, das auf distributed inner product estimation unter Verwendung von Pauli-Sampling basiert.
Abschließend kombinieren wir Ideen aus den vorherigen Kapiteln, um das Problem der Verifikation im Kontext des Quantenlernens zu untersuchen. Insbesondere betrachten wir das Problem des Lernens wenn mit einer unzuverlässigen, aber ressourcenreicheren Partei interagiert werden kann. Wir untersuchen verschiedene Aspekte dieses Problems, konzentrieren uns auf unterschiedliche Kommunikationsmodi und Ressourcendiskrepanzen und analysieren die Grenzen und Möglichkeiten, dieser interaktiven Protokolle.
