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.
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.
