dc.contributor.author
Kliesch, Martin
dc.date.accessioned
2018-06-07T21:19:41Z
dc.date.available
2015-04-29T10:53:55.522Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/7724
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-11923
dc.description
1 Introduction 2 Locality and complexity in lattice systems 2.1 Introduction
to Lieb-Robinson bounds and their implications 2.2 Generalizing Hamiltonian
complexity results to open quantum systems 2.2.1 A dissipative Church-Turing
theorem from generalizing the Trotter-Suzuki decomposition 2.2.2 Lieb-Robinson
bounds and quasi-locality of time evolution 2.3 Locality of temperature from a
new thermal Lieb-Robinson type bound 2.4 On state space structures 2.4.1 Real-
space renormalization yields finite correlations 2.4.2 A hard and an
undecidable problem for translation invariant 1D systems 3 Quantum simulations
and the verification problem 3.1 Indication that classical efficient Boson-
Sampling verification is impossible 3.2 Reliable quantum verification for
photonic quantum technologies 4 Conclusions Bibliography A Appendix:
Terminology A.1 Concepts from computational complexity theory A.2 Concepts
from quantum (information) theory B Appendix: Other publications generated
during this thesis C Back matter C.1 Acknowledgements C.2 Abstract C.3
Zusammenfassung C.4 Liste der Publikationen des Verfassers C.5 Anteil des
Autors bei Konzeption, Durchführung und Berichtsabfassung C.6
Eigenständigkeitserklärung
dc.description.abstract
Simulations play a crucial role in the investigation of complex quantum
systems. In this thesis, locality structures of quantum systems are exploited
to obtain complexity theoretic results with various physical implications.
More specifically, rigorous mathematical tools are used and developed further,
to investigate open quantum systems and thermal states. Moreover, important
advances in photonic quantum simulations are discussed. For open quantum spin
lattice systems new simulation schemes are provided. It is shown that
Markovian dynamics can be simulated efficiently in the unitary circuit model,
which can be seen as a dissipative Church-Turing type theorem. Moreover,
Markovian dynamics is quasi-local and can be locally simulated on classical
computers with a cost scaling polynomially in the system size. These results
generalize standard tools from the investigation of Hamiltonian systems to
open quantum systems. In particular, they provide a rigorous basis for their
numerical simulation. However, also a major roadblock for making such
simulations reliable is identified: Testing positivity of certain common
approximations to mixed quantum states, called matrix product operators, is
shown to be NP-hard in the system size and undecidable in the thermodynamic
limit. Also more state space structures, originating from the spatial locality
structure are discussed: Most states in state space cannot be generated
efficiently with local Liouvillian dynamics and pure states generated in real-
space renormalization schemes turn out to have local corrections in spatial
dimensions larger than one. For thermal states on spin and fermionic lattice
systems, a perturbation formula is provided and exponential clustering of
correlations at high enough temperature is proven. This has various
consequences: It leads to the extension of the concept of intensive
temperature to interacting quantum systems, allows for efficient classical
local simulations at high enough temperature, provides an upper bound on phase
transition temperatures, and implies stability of thermal states against
Hamiltonian perturbations. For photonic quantum simulations, sample complexity
lower bounds for the verification of Boson-Sampling simulations are explained,
which are applicable to a restricted setting. These bounds rely on a lower
bound on the min-entropy of the output distribution of Boson-Sampling. This
indicates that Boson-Sampling cannot be verified efficiently classically.
Complementary to that, a reliable verification scheme for photonic state
preparations is discussed, which uses single mode measurements as a simple
quantum resource. The verification scheme is efficient for a large class of
photonic simulations, including Boson-Sampling experiments with constantly
many photons and state preparations necessary for measurement based quantum
computing.
de
dc.description.abstract
Simulationen spielen eine wichtige Rolle in der Untersuchung von komplexen
Quantensystemen. In dieser Arbeit werden unter Ausnutzung von
Lokalitätsstrukturen koplexitätstheoretische Ergebnisse erzielt, die
vielseitige Implikationen haben. Aufbauend auf rigorosen mathematischen
Methoden und deren Weiterentwicklung werden offene Quantensysteme, thermische
Zustände und photonische Quantensimulationen untersucht. Es werden neue
Simulationsmethoden für offene Spingittersysteme eingeführt. Für Markovsche
Zeitentwicklung von Spingittersystemen wird gezeigt, dass sie effizient im
unitären Quantengattermodell simuliert werden können, was als eine Church-
Turing-Aussage interpretiert werden kann. Außerdem ist Markovsche Dynamik
quasilokal und mit klassischen Computern lokal simulierbar, wobei der
Simulationsaufwand polynomiell in der Systemgröße beschränkt ist. Diese
Ergebnisse bilden eine rigorose Grundlage für die Simulation von offenen
Quantensystemen. Allerdings wird auch ein großes Hindernis für die
Verbesserung der Zuverlässigkeit solcher Simulationen identifiziert: Das
Testen von Positivität von bestimmten üblichen Approximationen an gemischte
Quantenzustände, die Matrixproduktoperatoren genannt werden, ist NP-hart in
der Systemgröße und im thermodynamischen Limes unentscheidbar. Zusätzlich
werden auch weitere Zustandsraumstrukturen, welche durch räumliche Lokalität
bedingt sind, diskutiert: Die allermeisten Quantenzustände können nicht
effizient mittels lokaler Liouvillscher Dynamik generiert werden. Für
thermische Zustände auf Spin- und Fermionischen Gittersystemen wird eine
Störungsformel eingeführt und exponentielles Clustering von Korrelationen bei
ausreichend hohen Temperaturen bewiesen. Dies hat eine Reihe von Konsequenzen:
Es führt zu einer Erweiterung des Konzepts der Intensivität von Temperatur auf
wechselwirkende Quantensysteme, zu effizienteren klassischen Simulationen von
Systemen bei ausreichend hoher Temperatur, es bietet eine obere Schranke an
Phasenübergangstemperaturen und impliziert Stabilität von thermischen
Zuständen gegenüber Störungen des Hamiltonoperators. Für photonische
Quantensimulationen werden untere Schranken an die Sample-Komplexität der
Verifizierung von Boson-Sampling-Simulationen in einem eingeschränkten Rahmen
erklärt. Eine untere Schranke an die min-Entropie der Ausgabeverteilung von
Boson-Sampling stellt das technische Hauptresultat dieser Untersuchung dar.
Diese deutet darauf hin, dass Boson-Sampling klassisch nicht effizient
verifiziert werden kann. Ergänzend zu diesem Resultat wird ein zuverlässiges
Verifizierungsschema für photonische Zustandspräparationen vorgestellt, in
welchem Einzelmodenmessungen als Quantenressource verwendet werden. Dieses
Verifizierungsschema ist für eine große Klasse von photonischen Simulationen
effizient, die Boson-Sampling-Simulationen mit konstanter Photonenzahl und
bestimmten Zustandspräparation, die für messbasiertes Quantenrechnen notwendig
sind, mit einschließt.
de
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject
Quantum simulation
dc.subject
spin lattice systems
dc.subject
Markovian quantum dynamics
dc.subject
thermal quantum states
dc.subject
tensor networks
dc.subject.ddc
500 Naturwissenschaften und Mathematik::530 Physik::530 Physik
dc.subject.ddc
500 Naturwissenschaften und Mathematik::530 Physik::539 Moderne Physik
dc.title
Locality and complexity in simulations of complex quantum systems
dc.contributor.contact
martin.kliesch@fu-berlin.de
dc.contributor.firstReferee
Prof. Dr. Jens Eisert
dc.contributor.furtherReferee
Prof. Dr. Piet Brouwer
dc.date.accepted
2015-04-22
dc.identifier.urn
urn:nbn:de:kobv:188-fudissthesis000000099177-7
dc.title.translated
Lokalität und Komplexität in Simulationen komplexer Quantensysteme
de
refubium.affiliation
Physik
de
refubium.mycore.fudocsId
FUDISS_thesis_000000099177
refubium.mycore.derivateId
FUDISS_derivate_000000016968
dcterms.accessRights.dnb
free
dcterms.accessRights.openaire
open access