Abstract A crucial milestone in the field of quantum simulation and computation is to demonstrate that a quantum device can perform a computation task that is classically intractable. A key question is to identify setups that can achieve such goal within current technologies. In this work, we provide formal evidence that sampling bit-strings from a periodic evolution of a unitary drawn from the circular orthogonal ensemble (COE) cannot be efficiently simulated with classical computers. As the statistical properties of COE coincide with a large class of driven analog quantum systems thanks to the Floquet eigenstate thermalization hypothesis, our results indicate the possibility that those driven systems could constitute practical candidates for a sampling quantum advantage. To further support this, we give numerical examples of driven disordered Ising chains and 1D driven Bose–Hubbard model.
Abstract A crucial milestone in the field of quantum simulation and computation is to demonstrate that a quantum device can perform a computation task that is classically intractable. A key question is to identify setups that can achieve such goal within current technologies. In this work, we provide formal evidence that sampling bit-strings from a periodic evolution of a unitary drawn from the circular orthogonal ensemble (COE) cannot be efficiently simulated with classical computers. As the statistical properties of COE coincide with a large class of driven analog quantum systems thanks to the Floquet eigenstate thermalization hypothesis, our results indicate the possibility that those driven systems could constitute practical candidates for a sampling quantum advantage. To further support this, we give numerical examples of driven disordered Ising chains and 1D driven Bose–Hubbard model.
Nonequilibrium dynamics of quantum many-body systems is challenging for classical computing, providing opportunities for demonstrating practical quantum computational advantage with analog quantum simulators. Owing to the intimate connection with a random matrix ensemble, it is proposed to be classically intractable to sample the driven thermalized many-body states of a Bose-Hubbard system and further extract multipoint correlations from the output strings for characterizing quantum systems. Here, leveraging dedicated precise manipulations and atom-number-resolved detection through a quantum gas microscope with bichromatic superlattices, we perform sampling of the driven Hubbard chains and two-leg ladders in the thermalized phase involving up to 64 sites with 20 atoms, yielding a Hilbert space dimension of 10 19 and outpacing the most powerful supercomputer in terms of sampling rate by 3 orders of magnitude. The volume law scaling of the Rényi entanglement entropy in the thermalized phase is observed, which hinders efficient classical simulation for large systems. We employ the Bayesian tests to verify that our prepared systems operate in the driven thermalized phase. Multipoint correlations of up to 14th-order extracted from the experimental samples offer clear distinctions between the thermalized and many-body-localized phases, where classical computations such as tensor network fail to give accurate and faithful predictions within a reasonable time cost. Our work demonstrates the sampling of an interacting chaotic system performed on a quantum processor of ultracold atoms and opens the door of utilizable quantum computational advantage in simulating Floquet dynamics of many-body systems.
A crucial milestone in the field of quantum simulation and computation is to demonstrate that a quantum device can compute certain tasks that are impossible to reproduce by a classical computer with any reasonable resources. Such a demonstration is referred to as quantum supremacy. One of the most important questions is to identify setups that exhibit quantum supremacy and can be implemented with current quantum technology. The two standard candidates are boson sampling and random quantum circuits. Here, we show that quantum supremacy can be obtained in generic periodically-driven quantum many-body systems. Our analysis is based on the eigenstate thermalization hypothesis and strongly-held conjectures in complexity theory. To illustrate our work, We give examples of simple disordered Ising chains driven by global magnetic fields and Bose-Hubbard chains with modulated hoppings. Our proposal opens the way for a large class of quantum platforms to demonstrate and benchmark quantum supremacy.
Demonstrating a quantum computational speed-up is a crucial milestone for near-term quantum technology. Recently, sampling protocols for quantum simulators have been proposed that have the potential to show such a quantum advantage, based on commonly made assumptions. The key challenge in the theoretical analysis of this scheme-as of other comparable schemes such as boson sampling-is to lessen the assumptions and close the theoretical loopholes, replacing them by rigorous arguments. In this work, we prove two open conjectures for a simple sampling protocol that is based on the continuous time evolution of a translation-invariant Ising Hamiltonian: anticoncentration of the generated probability distributions and average-case hardness of exactly evaluating those probabilities. The latter is proven building upon recently developed techniques for random circuit sampling. For the former, we exploit the insight that approximate 2-designs for the unitary group admit anticoncentration. We then develop new techniques to prove that the 2D time evolution of the protocol gives rise to approximate 2-designs. Our work provides the strongest theoretical evidence to date that Hamiltonian quantum simulators are classically intractable.
Despite the exponentially large amount of information required in the quantum description of many-body systems, finite size numerical simulations have paved the way for recent progress in the understanding of quantum phases of matter both in and out-of-equilibrium. \n \nIn this spirit, using exact diagonalization for a small number of spins ~ 20, first, we investigate the fate of both ergodic quantum many-body systems that thermalize at long times and systems with quenched disorder that exhibit many-body localization (MBL) and fail to thermalize (due to an extensive set of local conserved degrees of freedom) under periodic driving. Ergodic systems always delocalize in energy space and heat up to infinite temperature, for both local driving, in which the time dependence of the Hamiltonian is restricted to a few contiguous degrees of freedom, and global driving. On the other hand, MBL systems remain localized at finite energy density for local driving, while in the case of global driving these systems can either heat up to infinite temperature or remain localized depending on the parameters of the drive. Underlying the latter is the emergence of an effective time independent MBL Hamiltonian describing the long time dynamics of the system. These numerical predictions have recently been verified experimentally in a one dimensional quasi-disordered optical lattice of interacting fermions wherein unitary time evolution can be experimentally probed. \n \nSubsequently, we study the stability of MBL systems with respect to another perturbation, in this case by thermal inclusions, which remains poorly understood. We consider a simple model to address this question: a two level system interacting with 𝑁 localized bits subject to random fields. In the large 𝑁 limit, the localized bits are thermalized for any nonzero ratio of interactions to disorder strength. Moreover, at finite 𝑁, in the transition region, the single-site eigenstate entanglement entropies exhibit bimodal distributions, so that localized bits are either "on" (strongly entangled) or "off" (weakly entangled) in eigenstates. The clusters of "on" bits vary significantly between eigenstates of the same sample, which provides evidence for a heterogenous discontinuous transition out of the localized phase in single site observables. These results also imply the MBL phase is unstable in systems with short-range interactions and quenched randomness in dimensions 𝑑 that are high but finite. \n \nThe second part of this thesis is motivated by the recent breakthroughs of artificial intelligence in domains such as computer vision involving highly dimensional data of complexity not unlike the one found in the description of many-body systems. Using Monte Carlo simulations to generate synthetic data, we find that kernel methods, a class of machine learning algorithms, can learn the mathematical \nform of physical discriminators associated with phase transitions, such as order parameters and Hamiltonian constraints, for a set of two dimensional spin models: the ferromagnetic Ising model, a conserved-order-parameter Ising model, and the Ising gauge theory. \n \nOur work shows that the combination of numerical simulations with the ability of machine learning algorithms for automatic feature detection hold promise to become standard tools in the exploration and characterization of different phases of matter in condensed matter and other many-body systems.
Demonstrating the ability of existing quantum platforms to perform certain computational tasks intractable to classical computers represents a cornerstone in quantum computing. Despite the growing number of such proposed ``quantum supreme'' tasks, it remains an important challenge to identify their direct applications. In this work, we describe how the approach proposed by Tangpanitanon et al. [arXiv:2002.11946] for demonstrating quantum supremacy in generic driven analog many-body systems, such as those found in cold atom and ion setups, can be extended to explore dynamical quantum phase transitions. We show how key quantum supremacy signatures, such as the divergence between the output distribution and the Porter Thomas distribution, can be used as effective order parameters. We apply this approach to a periodically driven disordered one-dimensional Ising model and show that we can accurately capture the transition between the driven thermalized and many-body localized phases. This approach also captures the transition towards the Floquet prethermalized regime for high-frequency driving. Revisiting quantum phases of matter under the light of the recent discussions about quantum supremacy draws a link between complexity theory and analog many-body systems.
Simulating thermal-equilibrium properties at finite temperature is crucial for studying quantum many-body systems. Quantum computers are expected to enable us to simulate large systems at finite temperatures, overcoming challenges faced by classical computers, such as the sign problem of the quantum Monte Carlo technique. Conventional methods suitable for fault-tolerant quantum computing (FTQC) devices are designed for studying large-scale quantum many-body systems but require a large number of ancilla qubits and a deep quantum circuit with many basic gates, making them unsuitable for the early stage of the FTQC era, when the availability of qubits and quantum gates is limited. In this paper, we propose a method suitable for quantum devices in this early stage to calculate the thermal-equilibrium expectation value of an observable at finite temperatures. Our proposal, named the Markov chain Monte Carlo with sampled pairs of unitaries (MCMC-SPU) algorithm, involves sampling simple quantum circuits and generating the corresponding statistical ensembles. This approach addresses the issues of resource demand and the decay in probability associated with postselection of measurement outcomes on ancilla qubits. We validate our proposal with a numerical simulation of the one-dimensional transverse-field Ising model as an illustrative example.