Physics
Permanent URI for this communityhttp://hdl.handle.net/1903/2269
Browse
125 results
Search Results
Item QUANTUM APPLICATIONS, PARALLEL OPERATIONS, AND NOISE CHARACTERIZATION ON A TRAPPED ION QUANTUM COMPUTER(2024) Zhu, Yingyue; Linke, Norbert M.; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Quantum computing holds vast potential for solving classically hard problems ranging from optimization to simulations critical in material science research and drug discovery. While large-scale fault-tolerant quantum computers capable of these tasks are yet to come, small and noisy prototypes have been demonstrated on several candidate platforms. Among these, trapped-ion qubits have been at the forefront of quantum computing hardware because of their long coherence times, high-fidelity quantum gates, and all-to-all connectivity. This dissertation investigates new methods for efficient quantum computing at the interface of quantum information theory and trapped-ion experiments, and advances both the control of physical trapped-ion hardware and the characterization of their decoherence processes. We present a number of proof-of-principle experiments for early quantum applications on a trapped-ion quantum computer (TIQC). First, we experimentally show that the results of the Quantum Approximate Optimization Algorithm (QAOA)---a method to solve graph combinatorial optimization problems by applying multiple rounds of variational circuits---improve with deeper circuits for multiple graph-theoretic problems on several arbitrary graphs. We also demonstrate a modified version of QAOA that allows sampling of all optimal solutions with predetermined weights. Additionally, we implement the real-time evolution of a one-dimensional scattering process and demonstrate a more efficient and accurate method to extract the phase shift, forming a tentative first step toward the goal of lattice quantum chromodynamics (QCD) simulation. Furthermore, we demonstrate two Bell-type nonlocal games that can be used to prove quantum computational advantage as well as offer a set of practical and scalable benchmarks for quantum computers in the pre-fault-tolerant regime. Our experimental results indicate that the performance of quantum strategies for the non-local games exceeds basic classical bounds, and is on the cusp of demonstrating quantum advantage against more complicated classical strategies. We propose and demonstrate a high-fidelity and resource-efficient scheme for driving simultaneous entangling gates on different sets of orthogonal motional modes of a trapped-ion chain. We show the advantage of parallel operation with a simple digital quantum simulation where parallel implementation improves the overall fidelity significantly. We test and improve the performance of an ancilla-assisted protocol for learning Pauli noise in Clifford gates on a TIQC. With N ancilla, Pauli noise in an N-qubit Clifford gate can be learned with a sample size linear to N. We also design and demonstrate a way to improve the protocol's performance by reducing ancilla noise in post-processing.Item Characterization of Gap-Engineered Josephson Junctions and Gate Fidelities for a Superconducting Qubit(2024) Steffen, Zachary Andrew; Kollár, Alicia; Palmer, Benjamin S; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Quantum computing promises applications in physics, cryptography, material science, pharmaceuticals, and a wide range of other science. Superconducting qubits offer a possible platform for developing a quantum computer. To perform useful quantum computations, the coherence and control of present day superconducting qubits must be greatly improved. In this dissertation, I present two main results to improve the performance of transmon qubits. For the first project, I fabricated and characterized the coherence of transmon devices with asymmetric superconducting gaps. Previous models suggested that devices with asymmetric superconducting gaps on either side of the Josephson junction can be designed to be less subject to loss from quasiparticle tunneling. To gap-engineer the Josephson junctions, I used Ti metal to proximitize and lower the superconducting gap of the Al counter-electrode. Unfortunately, the energy relaxation time constant for an Al/AlOx/Al/Ti 3D transmon I fabricated and tested was T1 = 1 us, over two orders of magnitude shorter than the measured T1 = 134 us of an Al/AlOx/Al 3D transmon with Al capacitor pads and the measured T1 = 143 us of an Al/AlOx/Al 3D transmon with Ta capacitor pads. DC IV measurements of proximitized Josephson junctions showed a reduced superconducting gap, demonstrating that the gap-engineering in the Al/Ti layer was successful. However, these same IV measurements showed greatly increased excess current for voltage biases below the superconducting gap compared to my Al/AlOx/Al junctions. This suggests the addition of Ti caused the junction quality to worsen, potentially being a source of tunneling loss in the transmon devices. Intentionally adding oxygen disorder between the Al and Ti layers reduced the proximity effect and subgap current in DC measurements while increasing the relaxation time of a 3D transmon to T1 = 32 us. Additionally, I designed an Al/AlOx/Al SQUID device to perform DC IV measurements of junctions with tunable total critical current. In a single junction, subgap tunneling features can be due to the critical current interacting with the environment, subgap quasiparticle processes, or other sources. Reducing the critical current allows these features to be differentiated and more accurately measure the effects from quasiparticle tunneling alone. Characterizing this device showed subgap tunneling features consistent with inelastic Cooper pair tunneling and quasiparticle transport via multiple Andreev reflection in a low transparency junction. This measurement technique could be used to further study gap-engineered junctions. For the second project, I characterized an Al/AlOx/Al 2D transmon device with Ta features and performed high-fidelity single qubit gates. First, I used error amplifying pulse sequences to fine-tune the qubit gate pulses. I evaluated the gate error with randomized benchmarking. I characterized gates with Gaussian and cosine shaped pulses at a variety of pulse lengths. Analyzing the pulse envelopes in the frequency domain and directly measuring leakage to the transmon's second excited state revealed that leakage from driving higher qubit transitions was a major source of gate error. Next, I characterized gates using a pulse shape designed by a physics informed neural network designed by Güngördü and Kestner and found improved gate error for 16~ns pulses achieving an average error per gate of (3.36 +/- 0.03) x 10^-4. This outperformed errors of (5.54 +/- 0.24) x10^-4 for a cosine shaped pulse and (3.93 +/- 0.12) x10^-4 for a Gaussian shaped pulse of the same length. Further optimization of the pulse using predistortion or leakage reduction strategies may yield even greater performance.Item EXCURSION IN THE QUANTUM LOSS LANDSCAPE: LEARNING, GENERATING AND SIMULATING IN THE QUANTUM WORLD(2024) Rad, Ali; Hafezi, Mohammad; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Statistical learning is emerging as a new paradigm in science. This has ignited interestwithin our inherently quantum world in exploring quantum machines for their advantages in learning, generating, and predicting various aspects of our universe by processing both quantum and classical data. In parallel, the pursuit of scalable science through physical simulations using both digital and analog quantum computers is rising on the horizon. In the first part, we investigate how physics can help classical Artificial Intelligence (AI) by studying hybrid classical-quantum algorithms. We focus on quantum generative models and address challenges like barren plateaus during the training of quantum machines. We further examine the generalization capabilities of quantum machine learning models, phase transitions in the over-parameterized regime using random matrix theory, and their effective behavior approximated by Gaussian processes. In the second part, we explore how AI can benefit physics. We demonstrate how classical Machine Learning (ML) models can assist in state recognition in qubit systems within solid-state devices. Additionally, we show how ML-inspired optimization methods can enhance the efficiency of digital quantum simulations with ion-trap setups Finally, in the third part, we focus on how physics can help physics by using quantum systems to simulate other quantum systems. We propose native fermionic analog quantum systems with fermion-spin systems in silicon to explore non-perturbative phenomena in quantum field theory, offering early applications for lattice gauge theory models.Item EXPLORING QUANTUM MANY-BODY SYSTEMS IN PROGRAMMABLE TRAPPED ION QUANTUM SIMULATORS(2024) De, Arinjoy; Monroe, Christopher R; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Quantum simulation is perhaps the most natural application of a quantum computer, where a precisely controllable quantum system is designed to emulate a more complex or less accessible quantum system. Significant research efforts over the last decade have advanced quantum technology to the point where it is foreseeable to achieve `quantum advantage' over classical computers, to enable the exploration of complex phenomena in condensed-matter physics, high-energy physics, atomic physics, quantum chemistry, and cosmology. While the realization of a universal fault-tolerant quantum computer remains a future goal, analog quantum simulators -- featuring continuous unitary evolution of many-body Hamiltonians -- have been developed across several experimental platforms. A key challenge in this field is balancing the control of these systems with the need to scale them up to address more complex problems. Trapped-ion platforms, with exceptionally high levels of control enabled by laser-cooled and electromagnetically confined ions, and all-to-all entangling capabilities through precise control over their collective motional modes, have emerged as a strong candidate for quantum simulation and provide a promising avenue for scaling up the systems. In this dissertation, I present my research work, emphasizing both the scalability and controllability aspects of \ion based trapped-ion platforms, with an underlying theme of analog quantum simulation. The initial part of my research involves utilizing a trapped ion apparatus operating within a cryogenic vacuum environment, suitable for scaling up to hundreds of ions. We address various challenges associated with this approach, particularly the impact of mechanical vibrations originating from the cryostat, which can induce phase errors during coherent operations. Subsequently, we detail the implementation of a scheme to generate phase-stable spin-spin interactions that are robust to vibration noise. In the second part, we use a trapped-ion quantum simulator operating at room temperature, to investigate the non-equilibrium dynamics of critical fluctuations following a quantum quench to the critical point. Employing systems with up to 50 spins, we show that the amplitude and timescale of post-quench fluctuations scale with system size, exhibiting distinct universal critical exponents. While a generic quench can lead to thermal critical behavior, a second quench from one critical state to another (i.e., double quench) results in unique critical behavior not seen in equilibrium. Our results highlight the potential of quantum simulators to explore universal scaling beyond the equilibrium paradigm. In the final part of the thesis, we investigate an analog of the paradigmatic string-breaking phenomena using a quantum spin simulator. We employ an integrated trapped-ion apparatus with $13$ spins that utilizes the individual controllability of laser beams to program a uniform spin-spin interaction profile across the chain, alongside 3-dimensional control of the local magnetic fields. We introduce two static probe charges, realized through local longitudinal magnetic fields, that create string tension. By implementing quantum quenches across the string-breaking point, we monitor non-equilibrium charge evolution with spatio-temporal resolution that elucidates the dynamical string breaking. Furthermore, by initializing the charges away from the string boundary, we generate isolated charges and observe localization effects that arise from the interplay between confinement and lattice effects.Item NONEQUILIBRIUM STATISTICAL PHYSICS OF FEEDBACK-CONTROLLED AND AUTONOMOUS INFORMATION-THERMODYNAMIC SYSTEMS(2024) Bhattacharyya, Debankur; Jarzynski, Christopher; Chemical Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This thesis investigates the nonequilibrium dynamics of a variety of systems evolving under control protocols. A control protocol can involve feedback based on measurements performed by an external agent, or it can be a predefined protocol that does not rely on explicit measurements of the system’s state. In the context of information thermodynamics, the former setup belongs to the paradigm of non-autonomous or feedback-controlled Maxwell's demons, and the latter to the paradigm of autonomous demons. The thesis begins with a framework for analyzing non-autonomous feedback control, when the control protocol is applied by an agent making continuous measurements on the system. A multiple-timescales perturbation theory, applicable when there exists an appropriate separation of timescales, is developed. This framework is applied to a classical two-state toy model of an information engine – a device that uses feedback control of thermal fluctuations to convert heat into work. Additionally, quantum trajectory simulations are used to study a feedback-controlled model of Maxwell's demon in a double quantum dot system. Next, a modeling scheme for converting feedback-controlled Maxwell's demons to autonomous (non-feedback) systems is developed. This scheme explicitly accounts for the thermodynamic costs of information processing, by incorporating an information reservoir, modeled as a sequence of bits. This modeling scheme is then applied for converting the classical analogue of the non-autonomous double quantum dot Maxwell's demon, discussed previously, to an autonomous model. Using analytical, semi-analytical and stochastic simulation-based approaches, it is shown that the obtained model can act either as an information engine, or as a “Landauer eraser”, and then the phase diagrams that identify these regimes of behavior are constructed. Finally, fast-forward shortcuts to adiabaticity for classical Floquet-Hamiltonian systems is developed, and applied to a periodically driven asymmetric double well (without feedback control). Tools from dynamical systems theory are then used to characterize the system’s angle-variable dynamics.Item Constructing an ergodic theory of quantum information dynamics(2024) Anand, Amit Vikram; Galitski, Victor; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The ergodic theory of classical dynamical systems, originating in Boltzmann's ergodic hypothesis, provides an idealized description of how the flow of information within energy surfaces of a classical phase space justifies the use of equilibrium statistical mechanics. While it is an extremely successful mathematical theory that establishes rigorous foundations for classical chaos and thermalization, its basic assumptions do not directly generalize to quantum mechanics. Consequently, previous approaches to quantum ergodicity have generally been limited to model-specific studies of thermalization, or well-motivated but imprecise general conjectures. In this Dissertation, we develop a general theoretical framework for understanding how the energy levels of a quantum system drive the flow of quantum information and constrain the applicability of statistical mechanics, guided by two prominent conjectures. The first of these, the Quantum Chaos Conjecture (QCC), aims to characterize which quantum systems may thermalize, by postulating a connection between ergodicity or chaos and the statistical properties of random matrices. The second, the Fast Scrambling Conjecture (FSC), is concerned with how fast a quantum system may thermalize, and posits a maximum speed of thermalization in a sufficiently “local” many-body system. This Dissertation is divided into three main parts. In the first part, Theory of Quantum Dynamics and the Energy Spectrum, we tackle these conjectures for a general isolated quantum system through results that may be understood as new formulations of the energy-time uncertainty principle. For QCC, we introduce precise quantum dynamical concepts of ergodicity and quantitatively establish their connections to the statistics of energy levels, deriving random matrix statistics as a special consequence of these dynamical notions. We subsequently build on one of these connections to derive an energy-time uncertainty principle that accounts for the full structure of the spectrum, introducing sufficient sensitivity for many-body systems. The resulting quantum speed limit allows us to prove a precise formulation of FSC from the mathematical properties of the energy spectrum. In doing so, we generalize QCC beyond the statistics of random matrices alone, and FSC beyond requirements of locality, establishing precise versions of these statements for the most general quantum mechanical Hamiltonian. In the second part, Quantum Systems Beyond the Chaotic-Integrable Dichotomy, we demonstrate the need for the aforementioned precise formulations of these conjectures, by showing that looser formulations can be readily violated in “maximally” chaotic or integrable systems that would be most expected to satisfy them. Finally, in the third part, Experimental Probes of Many-Body Quantum Ergodicity, we develop tools to experimentally probe the structure of energy levels associated with ergodic dynamics, and demonstrate a generalization of these probes to open systems in an experiment with trapped ions.Item ENGINEERING OPTICAL LATTICES FOR ULTRACOLD ATOMS WITH SPATIAL FEATURES AND PERIODICITY BELOW THE DIFFRACTION LIMIT and DUAL-SPECIES OPTICAL TWEEZER ARRAYS FOR RUBIDIUM AND YTTERBIUM FOR RYDBERG-INTERACTION-MEDIATED QUANTUM SIMULATIONS(2024) Subhankar, Sarthak; Rolston, Steven; Porto, Trey; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation is based on two independent projects and is therefore divided into two parts. The first half of this dissertation summarizes a series of investigations, both experimental and theoretical, that culminates in the realization of an optical lattice with a subwavelength spacing of $\lambda/4$, where $\lambda$ is the wavelength of light used to create the lattice. The second half of this thesis presents details on the design andconstruction of an apparatus for dual-species optical tweezer arrays of Rb and Yb for Rydberg-interaction-mediated quantum computation and simulation. Ultracold atoms trapped in optical lattices have proven to be a versatile, highly controllable, and pristine platform for studying quantum many-body physics. However, the characteristic single-particle energy scale in these systems is set by the recoil energy $E_R=h^2 /\left(8 m d^2\right)$. Here, $m$ is the mass of the atom, and $d$, the spatial period of the optical lattice, is limited by diffraction to ${\lambda}/{2}$, where $\lambda$ is the wavelength of light used to create the optical lattice. Although the temperatures in these systems can be exceedingly low, the energy scales relevant for investigating many-body physics phenomena, such as superexchange or magnetic dipole interactions, can be lower yet. This limitation can be overcome by raising the relevant energy scales of the system ($E_R^{\mathrm{eff}}=h^2 /\left(8 m d_{\mathrm{eff}}^2\right)$) by engineering optical lattices with spatial periodicities below the diffraction limit ($d_{\mathrm{eff}} < \lambda/2$). To realize this subwavelength-spaced lattice, we first generated a Kronig-Penney-like optical lattice using the nonlinear optical response of three-level atoms in spatially varying dark states. This conservative Kronig-Penney-like optical potential has strongly subwavelength barriers that can be less than 10 nm ($\equiv\lambda/50$) wide and are spaced $\lambda/2$ apart, where $\lambda$ is the wavelength of light used to generate the optical lattice. Using the same nonlinear optical response, we developed a microscopy technique that allowed the probability density of atoms in optical lattices to be measured with a subwavelength resolution of $\lambda/50$. We theoretically investigated the feasibility of stroboscopically pulsing spatially shifted 1D Kronig-Penney-like optical lattices to create lattices with subwavelength spacings. We applied the lattice pulsing techniques developed in this theoretical investigation to realize a $\lambda/4$-spaced optical lattice. We used the subwavelength resolution microscopy technique to confirm the existence of this $\lambda/4$-spaced optical lattice by measuring the probability density of the atoms in the ground band of the $\lambda/4$-spaced optical lattice. Single neutral atoms trapped in optical tweezer arrays with Rydberg interaction-mediated entangling gate operations have recently emerged as a promising platform for quantum computation and quantum simulation. These systems were first realized using atoms of a single species, with alkali atoms being the first to be trapped in optical tweezers, followed by alkaline-earth (like) atoms, and magnetic lanthanides. Recently, dual-species (alkali-alkali) optical tweezer arrays were also realized. Dual-species Rydberg arrays are a promising candidate for large-scale quantum computation due to their capability for multi-qubit gate operations and crosstalk-free measurements for mid-circuit readouts. However, a dual-species optical tweezer array of an alkali atom and an alkaline-earth (like) atom, which combines the beneficial properties of both types of atoms, has yet to be realized. In this half of the thesis, I present details on the design and construction of an apparatus for dual-species Rydberg tweezer arrays of Rb (alkali) and Yb (alkaline-earth like).Item TENSOR NETWORK APPROACHES IN NON-EQUILIBRIUM QUANTUM MANY-BODY DYNAMICS(2024) Yoo, Yongchan; Swingle, Brian; Sau, Jay D; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Understanding the dynamics of non-equilibrium quantum systems has been a longstanding challenge in a wide range of physical phenomena. Recent advancements in various quantum technologies have driven theoretical investigations of non-equilibrium quantum many-body dynamics. A crucial aspect of the theory is the development of computational methods, which have led to significant results and show promising directions for further development. However, simulating these complex systems using classical algorithms remains extremely difficult, primarily due to the challenge of identifying physically principled and efficient approximations capable of reducing their computational complexity.This thesis discusses theoretical and numerical studies on the non-equilibrium dynamics of quantum many-body systems, particularly focusing on the steady-state transport of conserved quantities in various one-dimensional spin systems. We study transport phenomena employing boundary-driven open quantum setups and investigate various aspects of the non-equilibrium dynamics induced by these systems. Our goal is to understand steady-state phenomena and to push the boundaries of simulation capacity using state-of-the-art technologies. In the first part, we examine the non-equilibrium steady-state (NESS) phases of an interacting Aubry-Andr´e-Harper model. This model involves a quasiperiodic potential, leading to interesting emergent collective phenomena. The observed spin transport and quantum correlation structure suggest the presence of multiple dynamical phases between the well-studied thermal and many-body-localized phases. In the second part, we study the impact of operator weight dissipation on the scaling behavior of transport in various spin models. Our findings suggest that dissipation’s effect on transport depends on the system’s conserved quantities. When dissipation preserves these symmetries, it maintains the scaling of the system’s transport properties. However, when it disrupts these conserved quantities, it leads the system towards diffusive scaling of transport. In the third part, we investigate energy transport within the non-integrable regime of the Z3 chiral clock model, utilizing Lindblad operators with adjustable size and temperature. Through scaling analysis, we extract the model’s transport coefficients at relatively high temperatures, both above its gapless and gapped low-temperature phases. Furthermore, we calculate the temperature dependence of the energy diffusion constant across various model parameters, including the regime where the model exhibits quantum critical behavior at low temperatures.Item Harnessing Quantum Systems for Sensing, Simulation, and Optimization(2024) Bringewatt, Jacob Allen; Gorshkov, Alexey V; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Quantum information science offers a remarkable promise: by thinking practically about how quantum systems can be put to work to solve computational and information processing tasks, we gain novel insights into the foundations of quantum theory and computer science. Or, conversely, by (re)considering the fundamental physical building blocks of computers and sensors, we enable new technologies, with major impacts for computational and experimental physics. In this dissertation, we explore these ideas through the lens of three different types of quantum hardware, each with a particular application primarily in mind: (1) networks of quantum sensors for measuring global properties of local field(s); (2) analog quantum computers for solving combinatorial optimization problems; and (3) digital quantum computers for simulating lattice (gauge) theories. For the setting of quantum sensor networks, we derive the fundamental performance limits for the sensing task of measuring global properties of local field(s) in a variety of physical settings (qubit sensors, Mach-Zehnder interferometers, quadrature displacements) and present explicit protocols that achieve these limits. In the process, we reveal the geometric structure of the fundamental bounds and the associated algebraic structure of the corresponding protocols. We also find limits on the resources (e.g. entanglement or number of control operations) required by such protocols. For analog quantum computers, we focus on the possible origins of quantum advantage for solving combinatorial optimization problems with an emphasis on investigating the power of adiabatic quantum computation with so-called stoquastic Hamiltonians. Such Hamiltonians do not exhibit a sign problem when classically simulated via quantum Monte Carlo algorithms, suggesting deep connections between the sign problem, the locality of interactions, and the origins of quantum advantage. We explore these connections in detail. Finally, for digital quantum computers, we consider the optimization of two tasks relevant for simulating lattice (gauge) theories. First, we investigate how to map fermionic systems to qubit systems in a hardware-aware manner that consequently enables an improved parallelization of Trotter-based time evolution algorithms on the qubitized Hamiltonian. Second, we investigate how to take advantage of known symmetries in lattice gauge theories to construct more efficient randomized measurement protocols for extracting purities and entanglement entropies from simulated states. We demonstrate how these protocols can be used to detect a phase transition between a trivial and a topologically ordered phase in $Z_2$ lattice gauge theory. Detecting this transition via these randomized methods would not otherwise be possible without relearning all symmetries.Item Quantum Advantage in Sensing and Simulation(2024) Ehrenberg, Adam; Gorshkov, Alexey V; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Since the discovery of Shor's factoring algorithm, there has been a sustained interest in finding more such examples of quantum advantage, that is, tasks where a quantum device can outperform its classical counterpart. While the universal, programmable quantum computers that can run Shor's algorithm represent one direction in which to search for quantum advantage, they are certainly not the only one. In this dissertation, we study the theory of quantum advantage along two alternative avenues: sensing and simulation. Sensing refers to the task of measuring some unknown quantity with the smallest possible error. In many cases, when the sensing apparatus is a quantum device, this ultimate achievable precision, as well as specific protocols producing estimators with this precision, are unknown. In this dissertation, we help close this gap for both qubit-based and photonic quantum sensors for the specific task of measuring a linear function of unknown parameters. We use quantum Fisher information and the quantum Cramér-Rao bound to derive limits on their ultimate precision. We further develop an algebraic framework that allows us to derive protocols saturating these bounds and better understand the quantum resources, such as entanglement, that are necessary to implement these protocols. In doing so, we help clarify how quantum resources like entanglement lead to more precise sensing. We also study a specific form of simulation called Gaussian Boson Sampling, which is a member of the broad framework of random sampling tasks that have become a popular method for demonstrating quantum advantage. While many of the theoretical underpinnings of these random sampling tasks, including Gaussian Boson Sampling, are well understood, many questions remain. Anticoncentration, which is strongly related to the moments of the output distribution, is a particularly relevant property when it comes to formally proving the existence of quantum advantage. We develop a graph-theoretic framework to calculate these moments, and we show that there is a transition in the strength of anticoncentration as a function of how many of the photonic modes are initially squeezed. We therefore demonstrate a transition in the evidence for the so-called approximate average-case hardness of Gaussian Boson Sampling, hence clarifying in what regimes we have the strongest evidence for quantum advantage. Finally, we also discuss the simulation complexity of Many-Body Localized systems. Many-Body Localization is a widely studied phase of matter that is often characterized by the appearance of a large number of quasilocal integrals of motion (operators that commute with the Hamiltonian) that interact via exponentially decaying interactions. In this dissertation, we study a phenomenological form of Many-Body Localization and show three main results. First, we demonstrate that, for polynomially long evolution times under a Hamiltonian in the Many-Body Localized phase, there is a quasipolynomial-time classical algorithm that can perform strong simulation of the output state. On the flip side, our second result is that, when the evolution time is exponentially long, weak simulation of the output state becomes formally classically hard. Finally, as a consequence of our classical results, we show the approximate quantum circuit complexity of these Hamiltonians grows sublinearly in the evolution time (in contrast with the proposed linear growth for chaotic Hamiltonians). Thus, this work helps clarify whether and how we might find quantum advantage via simulating certain types of condensed matter systems.