One T Gate Makes Distribution Learning Hard.

The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits are of central importance in both quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we extensively characterize the learnability of output distributions of local quantum circuits. Firstly, we contrast learnability with simulatability by showing that Clifford circuit output distributions are efficiently learnable, while the injection of a single T gate renders the density modeling task hard for any depth d=n^{Ω(1)}. We further show that the task of generative modeling universal quantum circuits at any depth d=n^{Ω(1)} is hard for any learning algorithm, classical or quantum, and that for statistical query algorithms, even depth d=ω[log(n)] Clifford circuits are hard to learn. Our results show that one cannot use the output distributions of local quantum circuits to provide a separation between the power of quantum and classical generative modeling algorithms, and therefore provide evidence against quantum advantages for practically relevant probabilistic modeling tasks.

Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates.

Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full n-qubit group, one often resorts to t-designs. Unitary t-designs mimic the Haar-measure up to t-th moments. It is known that Clifford operations can implement at most 3-designs. In this work, we quantify the non-Clifford resources required to break this barrier. We find that it suffices to inject O ( t 4 log 2 ( t ) log ( 1 / ε ) ) many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an ε -approximate t-design. Strikingly, the number of non-Clifford gates required is independent of the system size - asymptotically, the density of non-Clifford gates is allowed to tend to zero. We also derive novel bounds on the convergence time of random Clifford circuits to the t-th moment of the uniform distribution on the Clifford group. Our proofs exploit a recently developed variant of Schur-Weyl duality for the Clifford group, as well as bounds on restricted spectral gaps of averaging operators.

Entangling Power and Quantum Circuit Complexity.

Notions of circuit complexity and cost play a key role in quantum computing and simulation where they capture the (weighted) minimal number of gates that is required to implement a unitary. Similar notions also become increasingly prominent in high energy physics in the study of holography. While notions of entanglement have in general little implications for the quantum circuit complexity and the cost of a unitary, in this work, we discuss a simple such relationship when both the entanglement of a state and the cost of a unitary take small values, building on ideas on how values of entangling power of quantum gates add up. This bound implies that if entanglement entropies grow linearly in time, so does the cost. The implications are twofold: It provides insights into complexity growth for short times. In the context of quantum simulation, it allows us to compare digital and analog quantum simulators. The main technical contribution is a continuous-variable small incremental entangling bound.

Rates of Multipartite Entanglement Transformations.

The theory of the asymptotic manipulation of pure bipartite quantum systems can be considered completely understood: the rates at which bipartite entangled states can be asymptotically transformed into each other are fully determined by a single number each, the respective entanglement entropy. In the multipartite setting, similar questions of the optimally achievable rates of transforming one pure state into another are notoriously open. This seems particularly unfortunate in the light of the revived interest in such questions due to the perspective of experimentally realizing multipartite quantum networks. In this Letter, we report substantial progress by deriving simple upper and lower bounds on the rates that can be achieved in asymptotic multipartite entanglement transformations. These bounds are based on ideas of entanglement combing and state merging. We identify cases where the bounds coincide and hence provide the exact rates. As an example, we bound rates at which resource states for the cryptographic scheme of quantum secret sharing can be distilled from arbitrary pure tripartite quantum states. This result provides further scope for quantum internet applications, supplying tools to study the implementation of multipartite protocols over quantum networks.

Floquet Engineering Topological Many-Body Localized Systems.

We show how second-order Floquet engineering can be employed to realize systems in which many-body localization coexists with topological properties in a driven system. This allows one to implement and dynamically control a symmetry protected topologically ordered qubit even at high energies, overcoming the roadblock that the respective states cannot be prepared as ground states of nearest-neighbor Hamiltonians. Floquet engineering-the idea that a periodically driven nonequilibrium system can effectively emulate the physics of a different Hamiltonian-is exploited to approximate an effective three-body interaction among spins in one dimension, using time-dependent two-body interactions only. In the effective system, emulated topology and disorder coexist, which provides an intriguing insight into the interplay of many-body localization that defies our standard understanding of thermodynamics and into the topological phases of matter, which are of fundamental and technological importance. We demonstrate explicitly how combining Floquet engineering, topology, and many-body localization allows one to harvest the advantages (time-dependent control, topological protection, and reduction of heating, respectively) of each of these subfields while protecting them from their disadvantages (heating, static control parameters, and strong disorder).

Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics.

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.

Single-Shot Holographic Compression from the Area Law.

The area law conjecture states that the entanglement entropy of a region of space in the ground state of a gapped, local Hamiltonian only grows like the surface area of the region. We show that, for any state that fulfills an area law, the reduced quantum state of a region of space can be unitarily compressed into a thickened boundary of the region. If the interior of the region is lost after this compression, the full quantum state can be recovered to high precision by a quantum channel only acting on the thickened boundary. The thickness of the boundary scales inversely proportional to the error for arbitrary spin systems and logarithmically with the error for quasifree bosonic systems. Our results can be interpreted as a single-shot operational interpretation of the area law. The result for spin systems follows from a simple inequality showing that any probability distribution with entropy S can be approximated to error ϵ by a distribution with support of size exp(S/ϵ), which we believe to be of independent interest. We also discuss an emergent approximate correspondence between bulk and boundary operators and the relation of our results to tensor network states.

Randomized Benchmarking for Individual Quantum Gates.

Any technology requires precise benchmarking of its components, and the quantum technologies are no exception. Randomized benchmarking allows for the relatively resource economical estimation of the average gate fidelity of quantum gates from the Clifford group, assuming identical noise levels for all gates, making use of suitable sequences of randomly chosen gates. In this work, we report significant progress on randomized benchmarking, by showing that it can be applied individually on a broad class of quantum gates outside the Clifford group, even for varying noise levels per quantum gate. This is possible at little overhead of quantum resources, but at the expense of a significant classical computational cost. At the heart of our analysis is a representation-theoretic framework which we bring into contact with classical estimation techniques based on bootstrapping and matrix pencils. We demonstrate the functioning of the scheme at hand of benchmarking tensor powers of T gates. Apart from its practical relevance, we expect this insight to be relevant as it highlights the role of assumptions made on unknown noise processes when characterizing quantum gates at high precision.

Tensor Network Annealing Algorithm for Two-Dimensional Thermal States.

Tensor network methods have become a powerful class of tools to capture strongly correlated matter, but methods to capture the experimentally ubiquitous family of models at finite temperature beyond one spatial dimension are largely lacking. We introduce a tensor network algorithm able to simulate thermal states of two-dimensional quantum lattice systems in the thermodynamic limit. The method develops instances of projected entangled pair states and projected entangled pair operators for this purpose. It is the key feature of this algorithm to resemble the cooling down of the system from an infinite temperature state until it reaches the desired finite-temperature regime. As a benchmark, we study the finite-temperature phase transition of the Ising model on an infinite square lattice, for which we obtain remarkable agreement with the exact solution. We then turn to study the finite-temperature Bose-Hubbard model in the limits of two (hard-core) and three bosonic modes per site. Our technique can be used to support the experimental study of actual effectively two-dimensional materials in the laboratory, as well as to benchmark optical lattice quantum simulators with ultracold atoms.

Entanglement-Ergodic Quantum Systems Equilibrate Exponentially Well.

One of the outstanding problems in nonequilibrium physics is to precisely understand when and how physically relevant observables in many-body systems equilibrate under unitary time evolution. General equilibration results show that equilibration is generic provided that the initial state has overlap with sufficiently many energy levels. But results not referring to typicality which show that natural initial states actually fulfill this condition are lacking. In this work, we present stringent results for equilibration for systems in which Rényi entanglement entropies in energy eigenstates with finite energy density are extensive for at least some, not necessarily connected, subsystems. Our results reverse the logic of common arguments, in that we derive equilibration from a weak condition akin to the eigenstate thermalization hypothesis, which is usually attributed to thermalization in systems that are assumed to equilibrate in the first place. We put the findings into the context of studies of many-body localization and many-body scars.

Strong Coupling Corrections in Quantum Thermodynamics.

Quantum systems strongly coupled to many-body systems equilibrate to the reduced state of a global thermal state, deviating from the local thermal state of the system as it occurs in the weak-coupling limit. Taking this insight as a starting point, we study the thermodynamics of systems strongly coupled to thermal baths. First, we provide strong-coupling corrections to the second law applicable to general systems in three of its different readings: As a statement of maximal extractable work, on heat dissipation, and bound to the Carnot efficiency. These corrections become relevant for small quantum systems and vanish in first order in the interaction strength. We then move to the question of power of heat engines, obtaining a bound on the power enhancement due to strong coupling. Our results are exemplified on the paradigmatic non-Markovian quantum Brownian motion.

Fidelity Witnesses for Fermionic Quantum Simulations.

The experimental interest and developments in quantum spin-1/2 chains has increased uninterruptedly over the past decade. In many instances, the target quantum simulation belongs to the broader class of noninteracting fermionic models, constituting an important benchmark. In spite of this class being analytically efficiently tractable, no direct certification tool has yet been reported for it. In fact, in experiments, certification has almost exclusively relied on notions of quantum state tomography scaling very unfavorably with the system size. Here, we develop experimentally friendly fidelity witnesses for all pure fermionic Gaussian target states. Their expectation value yields a tight lower bound to the fidelity and can be measured efficiently. We derive witnesses in full generality in the Majorana-fermion representation and apply them to experimentally relevant spin-1/2 chains. Among others, we show how to efficiently certify strongly out-of-equilibrium dynamics in critical Ising chains. At the heart of the measurement scheme is a variant of importance sampling specially tailored to overlaps between covariance matrices. The method is shown to be robust against finite experimental-state infidelities.

Recovering Quantum Gates from Few Average Gate Fidelities.

Characterizing quantum processes is a key task in the development of quantum technologies, especially at the noisy intermediate scale of today's devices. One method for characterizing processes is randomized benchmarking, which is robust against state preparation and measurement errors and can be used to benchmark Clifford gates. Compressed sensing techniques achieve full tomography of quantum channels essentially at optimal resource efficiency. In this Letter, we show that the favorable features of both approaches can be combined. For characterizing multiqubit unitary gates, we provide a rigorously guaranteed and practical reconstruction method that works with an essentially optimal number of average gate fidelities measured with respect to random Clifford unitaries. Moreover, for general unital quantum channels, we provide an explicit expansion into a unitary 2-design, allowing for a practical and guaranteed reconstruction also in that case. As a side result, we obtain a new statistical interpretation of the unitarity-a figure of merit characterizing the coherence of a process.

Equilibration via Gaussification in Fermionic Lattice Systems.

In this Letter, we present a result on the nonequilibrium dynamics causing equilibration and Gaussification of quadratic noninteracting fermionic Hamiltonians. Specifically, based on two basic assumptions-clustering of correlations in the initial state and the Hamiltonian exhibiting delocalizing transport-we prove that non-Gaussian initial states become locally indistinguishable from fermionic Gaussian states after a short and well controlled time. This relaxation dynamics is governed by a power-law independent of the system size. Our argument is general enough to allow for pure and mixed initial states, including thermal and ground states of interacting Hamiltonians on large classes of lattices as well as certain spin systems. The argument gives rise to rigorously proven instances of a convergence to a generalized Gibbs ensemble. Our results allow us to develop an intuition of equilibration that is expected to be more generally valid and relates to current experiments of cold atoms in optical lattices.

Fermionic Orbital Optimization in Tensor Network States.

Tensor network states and specifically matrix-product states have proven to be a powerful tool for simulating ground states of strongly correlated spin models. Recently, they have also been applied to interacting fermionic problems, specifically in the context of quantum chemistry. A new freedom arising in such nonlocal fermionic systems is the choice of orbitals, it being far from clear what choice of fermionic orbitals to make. In this Letter, we propose a way to overcome this challenge. We suggest a method intertwining the optimization over matrix product states with suitable fermionic Gaussian mode transformations. The described algorithm generalizes basis changes in the spirit of the Hartree-Fock method to matrix-product states, and provides a black box tool for basis optimization in tensor network methods.

Diagnosing Topological Edge States via Entanglement Monogamy.

Topological phases of matter possess intricate correlation patterns typically probed by entanglement entropies or entanglement spectra. In this Letter, we propose an alternative approach to assessing topologically induced edge states in free and interacting fermionic systems. We do so by focussing on the fermionic covariance matrix. This matrix is often tractable either analytically or numerically, and it precisely captures the relevant correlations of the system. By invoking the concept of monogamy of entanglement, we show that highly entangled states supported across a system bipartition are largely disentangled from the rest of the system, thus, usually appearing as gapless edge states. We then define an entanglement qualifier that identifies the presence of topological edge states based purely on correlations present in the ground states. We demonstrate the versatility of this qualifier by applying it to various free and interacting fermionic topological systems.

Positive Tensor Network Approach for Simulating Open Quantum Many-Body Systems.

Open quantum many-body systems play an important role in quantum optics and condensed matter physics, and capture phenomena like transport, the interplay between Hamiltonian and incoherent dynamics, and topological order generated by dissipation. We introduce a versatile and practical method to numerically simulate one-dimensional open quantum many-body dynamics using tensor networks. It is based on representing mixed quantum states in a locally purified form, which guarantees that positivity is preserved at all times. Moreover, the approximation error is controlled with respect to the trace norm. Hence, this scheme overcomes various obstacles of the known numerical open-system evolution schemes. To exemplify the functioning of the approach, we study both stationary states and transient dissipative behavior, for various open quantum systems ranging from few to many bodies.

Many-Body Localization Implies that Eigenvectors are Matrix-Product States.

The phenomenon of many-body localization has received a lot of attention recently, both for its implications in condensed-matter physics of allowing systems to be an insulator even at nonzero temperature as well as in the context of the foundations of quantum statistical mechanics, providing examples of systems showing the absence of thermalization following out-of-equilibrium dynamics. In this work, we establish a novel link between dynamical properties--a vanishing group velocity and the absence of transport--with entanglement properties of individual eigenvectors. For systems with a generic spectrum, we prove that strong dynamical localization implies that all of its many-body eigenvectors have clustering correlations. The same is true for parts of the spectrum, thus allowing for the existence of a mobility edge above which transport is possible. In one dimension these results directly imply an entanglement area law; hence, the eigenvectors can be efficiently approximated by matrix-product states.

Matrix-product operators and states: NP-hardness and undecidability.

Tensor network states constitute an important variational set of quantum states for numerical studies of strongly correlated systems in condensed-matter physics, as well as in mathematical physics. This is specifically true for finitely correlated states or matrix-product operators, designed to capture mixed states of one-dimensional quantum systems. It is a well-known open problem to find an efficient algorithm that decides whether a given matrix-product operator actually represents a physical state that in particular has no negative eigenvalues. We address and answer this question by showing that the problem is provably undecidable in the thermodynamic limit and that the bounded version of the problem is NP-hard (nondeterministic-polynomial-time hard) in the system size. Furthermore, we discuss numerous connections between tensor network methods and (seemingly) different concepts treated before in the literature, such as hidden Markov models and tensor trains.

Probing coherent quantum thermodynamics using a trapped ion.

Quantum thermodynamics is aimed at grasping thermodynamic laws as they apply to thermal machines operating in the deep quantum regime, where coherence and entanglement are expected to matter. Despite substantial progress, however, it has remained difficult to develop thermal machines in which such quantum effects are observed to be of pivotal importance. In this work, we demonstrate the possibility to experimentally measure and benchmark a genuine quantum correction, induced by quantum friction, to the classical work fluctuation-dissipation relation. This is achieved by combining laser-induced coherent Hamiltonian rotations and energy measurements on a trapped ion. Our results demonstrate that recent developments in stochastic quantum thermodynamics can be used to benchmark and unambiguously distinguish genuine quantum coherent signatures generated along driving protocols, even in presence of experimental SPAM errors and, most importantly, beyond the regimes for which theoretical predictions are available (e.g., in slow driving).