Detailansicht
On the computational power of quantum computers
Martin Schwarz
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Physik
Betreuer*in
Frank Verstraete
DOI
10.25365/thesis.31407
URN
urn:nbn:at:at-ubw:1-30247.08267.406659-7
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Dissertation beschäftigt sich mit der Frage, wie viel Rechenkraft Quantencomputer bieten können. Diese Frage geht in ihrer allgemeinsten Form weit über die aktuellen Möglichkeiten und Methoden der Komplexitätstheorie hinaus. Dennoch liefert die Komplexitätstheorie Beispiele von Problemen, die sogar für Quantencomputer als nicht effizient lösbar gelten. Andererseits können Quantencomputer vermutlich nicht effizient von klassischen Computern simuliert werden. Wir wollen mit dieser Arbeit zum Verständnis des dazwischen liegenden Bereichs von Problemen, die effizient auf Quantencomputern, aber nicht effizient auf klassischen Computern berechnet werden können, beitragen. Um besseren Einblick in die Fragestellung zu erlagen, entwickeln wir in dieser Dissertation klassische und quantenmechanische Algorithmen zur Lösung von Problemen, die unter einschränkenden Annahmen a priori als nicht effizient lösbar geltende Probleme dennoch effizient lösen. Wir erforschen in diesem Sinne also die Grenzen des auf Quantencomputern und klassischen Computern Machbaren, in dem wir Annahmen identifizieren, die dazu geeignet sind grundsätzlich als schwer geltende Probleme in den Bereich des Machbaren zu bringen. Im Speziellen entwickeln wir einen Quantenalgorithmus, der sogenannte Projective Entangled-Pair States (PEPS) effizient herstellen kann, sobald Injektivität und Wohlkonditierung des PEPS gegeben ist. In einem zweiten Schritt erweitern wir diesen Algorithmus auf sogenannte G-injektive PEPS, einer wesentlich allgemeineren Klasse von Quantenzuständen, die auch die exotische Eigenschaft der topologischen Ordnung besitzen können. Weiters entwickeln wir einen Quantenalgorithmus, der das im Allgemeinen für Quantencomputer als schwer geltende Problem den Grundzustand von lokalen Hamiltonoperatoren zu erzeugen löst, sofern diese die Voraussetzungen des (nicht-konstruktiven) Quanten-Lovász-Local-Lemma erfüllen und die Operatoren kommutieren. Unser Quantenalgorithmus kann in diesem Fall auch als unabhängiger, konstruktiver Beweis des Quanten-Lovász-Local-Lemmas betrachtet werden. Um die Grenze zu klassischen Computern zu erforschen, entwickeln wir einen klassischen Algorithmus, der das sehr allgemeine Problem Quantenschaltkreise zu simulieren unter gewissen Annahmen effizient lösen kann. Wäre es in voller Allgemeinheit lösbar, würden Quantencomputer keinen Vorteil bieten. Unser Algorithmus kann Quantenschaltkreise simulieren, die in ihrer Struktur jener des Quantenalgorithmus von Shor zur Faktorisierung ganzer Zahlen, der als exponentiell schneller als der schnellste bekannte klassische Faktorisierungsalgorithmus gilt, sehr ähnlich sind. Weiters treffen wir die Annahme, dass die erzeugte Wahrscheinlichkeitsverteilung annähernd dünn-besetzt ist. Unser Ergebnis impliziert daher, dass die von Algorithmen dieser Struktur erzeugte Wahrscheinlichkeitsverteilung notwendigerweise dicht-besetzt sein muss, um einen exponentiellen Geschwindigkeitsvorteil erzielen zu können.
Abstract
(Englisch)
In this thesis we make progress in our understanding of the computational power made available by quantum computers. While answering this question in full generality in the framework of computational complexity theory appears beyond the reach of current methods, research in this direction has identified certain problems that are conjectured to be hard even for quantum computers, such as the Local Hamiltonian problem, or more general quantum state preparation problems. On the other hand, the generic problem of simulating quantum computers is conjectured to be hard for classical computers. We make progress in understanding the delineations among the classical and quantum models of computation by designing algorithms that explore these borders by identifying critical assumptions that allow us to efficiently solve certain problems which otherwise would be considered intractable. More specifically, towards exploring the power of quantum computers, we present a quantum algorithm that efficiently prepares quantum states specified by so-called projected entangled-pair states (or PEPS). While this problem is known to be hard in general even for quantum computers, assuming the PEPS is injective and well-conditioned allows us to prepare it efficiently. In a second step, we generalize this algorithm to efficiently prepare quantum states with topological order as specified by well-conditioned G-injective PEPS. A third quantum algorithm presented in this thesis prepares the zero-energy ground state of a certain class of Local Hamiltonians characterized by the non-constructive Quantum Lovász Local Lemma. While the lemma guarantees the existence of such a state, we present a quantum algorithm to efficiently prepare it assuming commutativity of the local projector terms. Finally, we explore the opposite direction towards the power of classical computers. We present a classical algorithm to simulate quantum circuits of a specific structure that is similar to Shor's integer factorization quantum algorithm (which is exponentially faster than any known classical factoring algorithm). Assuming approximate sparseness of the output distribution produced by quantum circuits of this structure allows us to simulate them classically. Thus we have discovered a region where quantum computers cannot retain their
presumed computational advantage. Moreover, this result implies that no exact quantum algorithm of this structure can offer exponential speed-up, and that output distributions of such quantum circuits must necessarily have super-polynomially large support and must have additional structure (e.g. group structure) to allow for an exponential speed-up.
Schlagwörter
Schlagwörter
(Englisch)
quantum computer complexity simulation quantum algorithms
Schlagwörter
(Deutsch)
Quantencomputer Komplexität Simulation Quantenalgorithmen
Autor*innen
Martin Schwarz
Haupttitel (Englisch)
On the computational power of quantum computers
Paralleltitel (Deutsch)
Über die Rechenkraft von Quantencomputern
Publikationsjahr
2013
Umfangsangabe
101 S. : graph. Darst.
Sprache
Englisch
Beurteiler*innen
Barbara Kraus ,
David Gross
Klassifikation
33 Physik > 33.23 Quantenphysik
AC Nummer
AC11708708
Utheses ID
27926
Studienkennzahl
UA | 091 | 411 | |