We classify phases of a bosonic lattice model based on the computational complexity of classically simulating the system. We show that the system transitions from being classically simulable to classically hard to simulate as it evolves in time, extending previous results to include on-site number-conserving interactions and long-range hopping. Specifically, we construct a complexity phase diagram with easy and hard "phases" and derive analytic bounds on the location of the phase boundary with respect to the evolution time and the degree of locality. We find that the location of the phase transition is intimately related to upper bounds on the spread of quantum correlations and protocols to transfer quantum information. Remarkably, although the location of the transition point is unchanged by on-site interactions, the nature of the transition point does change. Specifically, we find that there are two kinds of transitions, sharp and coarse, broadly corresponding to interacting and noninteracting bosons, respectively. Our Letter motivates future studies of complexity in many-body systems and its interplay with the associated physical phenomena.
We classify phases of a bosonic lattice model based on the computational complexity of classically simulating the system. We show that the system transitions from being classically simulable to classically hard to simulate as it evolves in time, extending previous results to include on-site number-conserving interactions and long-range hopping. Specifically, we construct a complexity phase diagram with easy and hard "phases" and derive analytic bounds on the location of the phase boundary with respect to the evolution time and the degree of locality. We find that the location of the phase transition is intimately related to upper bounds on the spread of quantum correlations and protocols to transfer quantum information. Remarkably, although the location of the transition point is unchanged by on-site interactions, the nature of the transition point does change. Specifically, we find that there are two kinds of transitions, sharp and coarse, broadly corresponding to interacting and noninteracting bosons, respectively. Our Letter motivates future studies of complexity in many-body systems and its interplay with the associated physical phenomena.
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.
Motivated to elucidate the nature of quantum phases and their criticality when entangled with a correlated quantum bath, we study interacting bosons on a "comb lattice"-a one-dimensional backbone (system) coupled at its sites to otherwise independent one-dimensional "teeth" chains (bath). We map out the corresponding phase diagram, detailing the nature of the phases and phase transitions. Controlled by the backbone and teeth hopping amplitudes, short-range interactions, and chemical potential, phases include a Mott insulator, backbone, and teeth Luttinger liquids and the long-range ordered incoherent superfluid. We explore their properties and potential realizations in condensed matter and cold-atom experiments and simulations.
Equilibrium phase transitions usually emerge from the microscopic behavior of many-body systems and are associated to interesting phenomena such as the generation of long-range order and spontaneous symmetry breaking. They can be defined through the non-analytic behavior of thermodynamic potentials in the thermodynamic limit. This limit is obtained when the number of available configurations of the system approaches infinity, which is conventionally associated to spatially-extended systems formed by an infinite number of degrees of freedom (infinite number of particles or modes). Taking previous ideas to the extreme, we argue that such a limit can be defined even in non-extended systems, providing a specific example in the simplest form of a single-mode bosonic Hamiltonian. In contrast to previous non-extended models, the simplicity of our model allows us to find approximate analytical expressions that can be confronted with precise numerical simulations in all the parameter space, particularly as close to the thermodynamic limit as we want. We are thus able to show that the system undergoes a change displaying all the characteristics of a second-order phase transition as a function of a control parameter. We derive critical exponents and scaling laws revealing the universality class of the model, which coincide with that of more elaborate non-extended models such as the quantum Rabi or Lipkin-Meshkov-Glick models. Analyzing our model, we are also able to offer insights into the features of this type of phase transitions, by showing that the thermodynamic and classical limits coincide. In other words, quantum fluctuations must be tamed in order for the system to undergo a true phase transition.
Abstract The quantum phase transition of the hardcore boson model on a Lieb lattice by quantum Monte Carlo simulations is studied. Considering nearest‐neighbor interchain hopping, the phase diagram of the Bose‐Hubbard model on the Lieb lattice contains solid phases with average density = 2/3, and superfluid phases between solid phases.Two ways of controlling quantum states are discussed: to add an alternating on‐site potential, and to add an alternating hopping amplitude in the X‐ and Y‐directions. For the above cases, there exists a new filling state, = 1/3. Adding an alternating on‐site potential to the Hamiltonian, the phase transition from to is sharp and discontinuous, featuring the nature of a first order. Considering a dimerization term, for large V, it is expected that there is a direct transition from the valence‐bond insulator to the CDW as the interaction is strengthened. For the three cases, upper boundary for and lower boundary for are calculated.
Quantum many body physics is an exciting research area, involving novel phases of matter with fundamentally new properties, but is also notoriously hard due to complexity of interacting quantum systems. Some popular approaches involve approximation techniques and numerical simulations, which are known to fail in several important cases. In contrast, rigorous mathematical tools, such as exact solutions and operator inequalities, have a narrower range of applicability, but provide guaranteed results and insights into the underlying physical mechanisms. This research aims to develop new techniques in this direction and use them to explore novel phases of matter. My first direction is to construct toy models where exact solutions are possible. Such models are important as they prove that certain physical phenomena are theoretically possible in nature, and often lead to the discovery of new phases. Such insights are provided by three exactly solvable models I have discovered: (1) a family of 1D quantum spin models hosting free parastatistical quasiparticles (an exotic type of identical particles beyond fermions, bosons, and anyons), proving for the first time that parastatistics is theoretically possible as an emergent phenomenon; (2) a 3D classical Ising model whose phases are characterized by topological features of certain loop observables, suggesting existence of previously unknown classical phases and phase transitions with topological order parameters; and (3) a family of models with exact p-wave superconducting ground states demonstrating the existence of Majorana quasiparticles and non-Abelian statistics in particle number-conserving systems. My second direction is to derive rigorous bounds and exact constraints on physical observables, which are applicable to large families of quantum many-body systems. I present three directions of progress: (1) a method that dramatically improves the upper bounds on the speed of information propagation in locally-interacting systems, which significantly extends the scope of these bounds and enables new applications; (2) bounds on finite-size errors in numerical simulations of lattice systems, including quench dynamics and gapped ground states; and (3) a locality bound on gapped ground states of power-law interacting systems, which leads to a generalization of the aforementioned error bounds to such systems. These error bounds have important theoretical implications such as proving the existence of the thermodynamic limit and stability of phases, and are practically useful in determining the validity of finite-size numerical simulations.
The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer science. In this work, we address this question for the simulation of exponentially large bosonic Hamiltonians with quadratic interactions. We present two results: First, we introduce a broad class of quadratic bosonic problems for which we prove that they are BQP-complete. Importantly, this class includes two known BQP-complete problems as special cases: Classical oscillator networks and continuous-time quantum walks. Second, we show that extending the aforementioned class to even more general quadratic Hamiltonians results in a PostBQP-complete problem, which constitutes a jump in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.