Entanglement is one of the physical properties of quantum systems responsible for the computational hardness of simulating quantum systems. But while the runtime of specific algorithms, notably tensor network algorithms, explicitly depends on the amount of entanglement in the system, it is unknown whether this connection runs deeper and entanglement can also cause inherent, algorithm-independent complexity. In this Letter, we quantitatively connect the entanglement present in certain quantum systems to the computational complexity of simulating those systems. Moreover, we completely characterize the entanglement and complexity as a function of a system parameter. Specifically, we consider the task of simulating single-qubit measurements of k-regular graph states on n qubits. We show that, as the regularity parameter is increased from 1 to n-1, there is a sharp transition from an easy regime with low entanglement to a hard regime with high entanglement at k=3, and a transition back to easy and low entanglement at k=n-3. As a key technical result, we prove a duality for the simulation complexity of regular graph states between low and high regularity.
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.
In this paper, we construct two-dimensional bipartite cluster states and perform single-qubit measurements on the bulk qubits. We explore the entanglement scaling of the unmeasured one-dimensional boundary state and show that under certain conditions, the boundary state can undergo a volume-law to an area-law entanglement transition driven by variations in the measurement angle. We bridge this boundary state entanglement transition and the measurement-induced phase transition in the nonunitary (
1+1)D circuit via the transfer matrix method. We also explore the application of this entanglement transition on the computational complexity problems. Specifically, we establish a relation between the boundary state entanglement transition and the sampling complexity of the bipartite 2D cluster state, which is directly related to the computational complexity of the corresponding Ising partition function with complex parameters. By examining the boundary state entanglement scaling, we numerically identify the parameter regime for which the 2D quantum state can be efficiently sampled, which indicates that the Ising partition function can be evaluated efficiently in such a region.
Recently developed quantum algorithms suggest that quantum computers can solve certain problems and perform certain tasks more efficiently than conventional computers. Among other reasons, this is due to the possibility of creating non-classical correlations, or quantum entanglement, which is a phenomena hard or impossible to reproduce by classical-information methods. In this thesis I first investigate the simulation of quantum systems on a quantum computer constructed of two-level quantum elements or qubits. For this purpose, I present algebra mappings that allow one to obtain physical properties and compute correlation functions of fermionic, anyonic, and bosonic systems with such a computer. The results obtained show that the complexity of preparing a quantum state which contains the desired information for the computation is crucial. Second, I present a wide class of quantum computations, which could involve entangled states, that can be simulated with the same efficiency on both types of computers. The notion of generalized quantum entanglement then naturally emerges. This generalization of entanglement is based on the idea that entanglement is an observer-dependent concept, that is, relative to a set of preferred observables.
The search for quantum advantage, understood as the point at which quantum computation surpasses classical computation, has led to the study of the emergence of quantum complexity, and consequently to the investigation of what makes a quantum algorithm hard to simulate on a classical computer. Quantum complexity can be characterized in different ways: the first is given by the entanglement present within the state of the system, which characterizes the non-classical correlations among its subsystems. In general, entanglement provides a measure of how physically complex the system is, but it is not informative about the complexity of simulating the system. This latter kind of complexity is quantified by non-stabilizerness, which is generated, in particular, by all the operations forming a quantum algorithm that do not belong to the Clifford group. Recently, the anti-flatness has been introduced to provide a bridge between the entanglement present in a bipartition of the system and non-stabilizerness, a global property of the system's state. This thesis considers these three complementary quantities in the context of the simulation of a specific quantum algorithm: the quantum sawtooth map, for which an efficient implementation on a quantum computer exists. The dynamics of the sawtooth map is governed by a kicking strength parameter
k and the period of the kicking
T; depending on their values, the system exhibits a rich phenomenology, including integrable, diffusive, and localized regimes. Among them, this thesis focuses on dynamical localization, a phenomenon strictly analogous to Anderson localization in disordered systems, in which the evolution of momentum eigenstates suppresses momentum diffusion, causing the wavefunction to remain localized in the momentum basis around a given eigenvalue, over a characteristic localization length
ξ. The study investigates how dynamical localization affects bipartite entanglement, non-stabilizerness, and anti-flatness, and how these quantities vary as a function of the system size, the parameters characterizing the sawtooth map, and the choice of initial state. The main result is that, as the system is driven out of the localized regime and into the ergodic one, the onset of ergodicity is clearly and consistently marked by all three quantities, each approaching the corresponding theoretical prediction for Haar-random states. This behavior makes entanglement, non-stabilizerness, and anti-flatness reliable and complementary probes for distinguishing the two regimes: entanglement and anti-flatness capture the correlations that arise during the application of the algorithm, including features that depend on the logical position of the qubits within the register due to the encoding, while non-stabilizerness offers a basis-independent, global measure of computational complexity. Furthermore, this work promotes the use of the sawtooth map as a test and benchmarking algorithm for quantum hardware.
We study the universality of scaling of entanglement in Shor's factoring algorithm and in adiabatic quantum algorithms across a quantum phase transition for both the
NP-complete exact cover problem as well as Grover's problem. The analytic result for Shor's algorithm shows a linear scaling of the entropy in terms of the number of qubits, therefore making it hard to generate an efficient classical simulation protocol. A similar result is obtained numerically for the quantum adiabatic evolution exact cover algorithm, which also shows universality of the quantum phase transition near which the system evolves. On the other hand, entanglement in Grover's adiabatic algorithm remains a bounded quantity even at the critical point. The classification of scaling of entanglement appears as a natural grading of the computational complexity of simulating quantum phase transitions.
Dynamical quantum phase transitions, encompassing phenomena like many-body localization transitions and measurement-induced phase transitions, are often characterized and identified through the analysis of quantum entanglement. Here, we highlight that the dynamical phases defined by entanglement are further enriched by complexity. We investigate both the entanglement and Krylov complexity for fermions on regular graphs, which can be implemented by systems like
6Li atoms confined by optical tweezers. Our investigations unveil that while entanglement follows volume laws on both types of regular graphs with degree
d=2 and
d=3, the Krylov complexity exhibits distinctive behaviors. We analyze both free fermions and interacting fermions models. In the absence of interaction, both numerical results and theoretical analysis confirm that the dimension of the Krylov space scales as
D∼N for regular graphs of degree
d=2 with
N sites, and we have
D∼N2 for
d=3. The qualitative distinction also persists in interacting fermions on regular graphs. For interacting fermions, our theoretical analyses find the dimension scales as
D∼4Nα for regular graphs of
d=2 with
0.38≤α≤0.59, whereas it scales as
D∼4N for
d=3. The distinction in the complexity of quantum dynamics for fermions on graphs with different connectivity can be probed in experiments by measuring the out-of-time-order correlators.