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.
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.
Randomness is an intrinsic feature of quantum theory. The outcome of any measurement will be random, sampled from a probability distribution that is defined by the measured quantum state. The task of sampling from a prescribed probability distribution therefore seems to be a natural technological application of quantum devices. And indeed, certain random sampling tasks have been proposed to experimentally demonstrate the speedup of quantum over classical computation, so-called “quantum computational supremacy”. In the research presented in this thesis, I investigate the complexity-theoretic and physical foundations of quantum sampling algorithms. Using the theory of computational complexity, I assess the computational power of natural quantum simulators and close loopholes in the complexity-theoretic argument for the classical intractability of quantum samplers (Part I). In particular, I prove anticoncentration for quantum circuit families that give rise to a 2-design and review methods for proving average-case hardness. I present quantum random sampling schemes that are tailored to large-scale quantum simulation hardware but at the same time rise up to the highest standard in terms of their complexity-theoretic underpinning. Using methods from property testing and quantum system identification, I shed light on the question, how and under which conditions quantum sampling devices can be tested or verified in regimes that are not simulable on classical computers (Part II). I present a no-go result that prevents efficient verification of quantum random sampling schemes as well as approaches using which this no-go result can be circumvented. In particular, I develop fully efficient verification protocols in what I call the measurement-device-dependent scenario in which single-qubit measurements are assumed to function with high accuracy. Finally, I try to understand the physical mechanisms governing the computational boundary between classical and quantum computing devices by challenging their computational power using tools from computational physics and the theory of computational complexity (Part III). I develop efficiently computable measures of the infamous Monte Carlo sign problem and assess those measures both in terms of their practicability as a tool for alleviating or easing the sign problem and the computational complexity of this task. An overarching theme of the thesis is the quantum sign problem which arises due to destructive interference between paths – an intrinsically quantum effect. The (non-)existence of a sign problem takes on the role as a criterion which delineates the boundary between classical and quantum computing devices. I begin the thesis by identifying the quantum sign problem as a root of the computational intractability of quantum output probabilities. It turns out that the intricate structure of the probability distributions the sign problem gives rise to, prohibits their verification from few samples. In an ironic twist, I show that assessing the intrinsic sign problem of a quantum system is again an intractable problem.
It remains questionable whether all physically realizable computational model can be simulated by currently available digital computer in an efficient manner. The theory of Quantum Mechanics offers an answer to this question through one of its branches that intersects with Computer Science, known as Quantum Computing. It claims that current computers, which is operating based on classical mechanics cannot efficiently simulate quantum mechanical process. Under this claim, a computer that is operating based on quantum mechanics holds more computational power than classical computers, promising a possibility to computationally solve problems that are classically intractable. To show that this claim holds, numerous quantum computational models have been proposed and analyzed through the lens of Computational Complexity Theory, providing a rigorous notion of efficiency. Models that are more feasible experimentally, although not necessarily universal, have also been of a particular interests given the numerous complicated challenges surrounding the experimental implementation of a universal quantum computer. One of this non-universal models is called Gaussian Boson Sampling (GBS), which embraces the methods of Quantum Optics by sampling the number of photon outputs from a linear optical network as a means to process quantum information. Compared to its prototype model, Boson Sampling, GBS is more experimentally feasible due to its method of generating photon that is based on the Continuous Variable (CV) paradigm of Quantum Information. Nevertheless as with Boson Sampling, it was also shown that classical simulation of GBS cannot be performed efficiently under some highly plausible conjectures. In the work presented in this thesis, we probe the complexity of classically constructing the probability distribution induced by GBS using the method of Quantum Homodyne Tomography. Instead of photon number measurement, this method further embraces the CV paradigm in the measurement of GBS by using Homodyne measurements that outputs real numbers. Sample data obtained from the measurement outcomes is then classically processed using Pattern Functions, which we use to approximate the probability distribution of GBS. A series of computer simulations that approximates some probability values of GBS are presented here, which shows that the number of samples needed to decrease the error of the approximation increases rapidly for more accurate approximation. We have derived a bound for the approximation error which can be achieved given that the sampled data satisfies a certain statistical property. This statistical property can eventually be satisfied as the number of Homodyne samples increases. Having shown another evidence for the complexity of approximating GBS using Homodyne Tomography, we further investigate the nature of the complexity of GBS by analyzing its classical-quantum computational boundary in the spectrum of amount of noise present in a GBS setup. In doing this, we built our discussions on the measure of non-classicality using the presence of negative values in the Quasi-probability distribution (QPD) representation of states of a quantum system. We then discuss existing results that shows the possibility of efficient classical simulation of a quantum computational model given a sufficient amount of noise. These results impose a necessary criteria of the minimum amount of noise that an experiment has to surpass in order for it to be impossible to simulate classically in an efficient manner. We extend this idea for GBS, where we propose a modified GBS where we consider noise in its measurements that opens a way for a possible formulation of a noise condition that a GBS experiment has to fulfill to rule out possible efficient classical simulation. To further probe the classical-quantum computational boundary, we also propose a different quantum computational model called the Photon-added Thermal State CV-Sampling (PATS CVS), which can be formulated similarly to our noisy GBS model. We then discuss existing results that analyzes the negativity of the QPD representation of a noisy Photon-added Thermal state (PATS), which constitutes the inputs for PATS CVS. Using the result that shows the quantum-classical transition in terms of the QPD negativity for a PATS state when the amount of noise changes, we discuss the potential of PATS CVS model as a possible avenue to further probe the transition between efficiently simulable and non-efficiently simulable quantum mechanical experiment.
Quantum computing is the offspring of quantum mechanics and computer science, two great scientific fields founded in the 20th century. Quantum computing is a relatively young field and is recognized as having the potential to revolutionize science and technology in the coming century. The primary question in this field is essentially to ask which problems are feasible with potential quantum computers and which are not. In this dissertation, we study this question with a physical bent of mind. We apply tools from computer science and mathematical physics to study the complexity of simulating quantum systems. In general, our goal is to identify parameter regimes under which simulating quantum systems is easy (efficiently solvable) or hard (not efficiently solvable). This study leads to an understanding of the features that make certain problems easy or hard to solve. We also get physical insight into the behavior of the system being simulated. In the first part of this dissertation, we study the classical complexity of simulating quantum dynamics. In general, the systems we study transition from being easy to simulate at short times to being harder to simulate at later times. We argue that the transition timescale is a useful measure for various Hamiltonians and is indicative of the physics behind the change in complexity. We illustrate this idea for a specific bosonic system, obtaining a complexity phase diagram that delineates the system into easy or hard for simulation. We also prove that the phase diagram is robust, supporting our statement that the phase diagram is indicative of the underlying physics. In the next part, we study open quantum systems from the point of view of their potential to encode hard computational problems. We study a class of fermionic Hamiltonians subject to Markovian noise described by Lindblad jump operators and illustrate how, sometimes, certain Lindblad operators can induce computational complexity into the problem. Specifically, we show that these operators can implement entangling gates, which can be used for universal quantum computation. We also study a system of bosons with Gaussian initial states subject to photon loss and detected using photon-number-resolving measurements. We show that such systems can remain hard to simulate exactly and retain a relic of the "quantumness" present in the lossless system. Finally, in the last part of this dissertation, we study the complexity of simulating a class of equilibrium states, namely ground states. We give complexity-theoretic evidence to identify two structural properties that can make ground states easier to simulate. These are the existence of a spectral gap and the existence of a classical description of the ground state. Our findings complement and guide efforts in the search for efficient algorithms.
We make the case for studying the complexity of approximately simulating (sampling) quantum systems for reasons beyond that of quantum computational supremacy, such as diagnosing phase transitions. We consider the sampling complexity as a function of time t due to evolution generated by spatially local quadratic bosonic Hamiltonians. We obtain an upper bound on the scaling of t with the number of bosons n for which approximate sampling is classically efficient. We also obtain a lower bound on the scaling of t with n for which any instance of the boson sampling problem reduces to this problem and hence implies that the problem is hard, assuming the conjectures of Aaronson and Arkhipov [Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (ACM Press, New York, New York, USA, 2011), p. 333]. This establishes a dynamical phase transition in sampling complexity. Further, we show that systems in the Anderson-localized phase are always easy to sample from at arbitrarily long times. We view these results in light of classifying phases of physical systems based on parameters in the Hamiltonian. In doing so, we combine ideas from mathematical physics and computational complexity to gain insight into the behavior of condensed matter, atomic, molecular, and optical systems.
The nonequilibrium effects of dissipation and drive play a key role in an immense variety of nanoscale and mesoscale quantum systems. To understand the behaviour of open quantum systems, we need accurate methods that capture the influence of the environment on the system, while managing the exponentially large Hilbert space required to describe the system. Tensor network algorithms offer an efficient way to approach this challenge. In this thesis, we develop and apply tensor network techniques to study the dynamics and steady states of various open quantum systems. The first part of the thesis focuses on the driven dissipative many body physics in coupled cavity arrays described by Born-Markov master equations. We extend transfer matrix product operator methods to Liouvillian dynamics, and utilize them to compute dynamical correlation functions and fluorescence spectrum of an infinite coupled cavity array in 1D. We also investigate thermalization, and observe the emergence of a quasi-thermal steady state with a negative effective temperature. In another study, we use infinite projected entangled pair state (iPEPS) methods to compute steady states of coupled cavity lattices in 2D. We find that a straightforward adaptation of iPEPS to Liouvillian dynamics is unstable, contradicting a recent publication in the field. The second part investigates more general systems involving strong couplings and structured environments that induce non-Markovian dynamics. We develop a powerful time-evolving matrix product operator (TEMPO) algorithm that builds on Feynman-Vernon influence functional formalism, and uses matrix product states (MPS) to represent the temporal non-Markovian correlations efficiently. We apply TEMPO to study the localization phase transition of the spin-boson model and the dynamics of two spatially separated two-level systems coupled to a common environment. Finally, we propose the Toblerone TEMPO algorithm, which extends TEMPO to many-body systems interacting with general bosonic environments.
Understanding and simulating non-Markovian quantum dynamics remains an important challenge in open quantum system theory. A key advance in this endeavour would be to develop a unified mathematical description of non-Markovian dynamics, and classify its complexity in the many-body setting. In this paper, we identify a general class of non-Markovian memory kernels, described by complex-valued radon measures, and define their dynamics through a regularization procedure constructing the corresponding system-environment unitary groups. Building on this definition, we then consider k−local many-body non-Markovian systems with physically motivated assumptions on the total variation and smoothness of the memory kernels. We establish that their dynamics can be efficiently approximated on quantum computers, thus providing a rigorous verification of the Extended Church-Turing thesis for this general class of non-Markovian open quantum systems.