Experimental observation of curved light-cones in a quantum field simulator.

We investigate signal propagation in a quantum field simulator of the Klein-Gordon model realized by two strongly coupled parallel one-dimensional quasi-condensates. By measuring local phononic fields after a quench, we observe the propagation of correlations along sharp light-cone fronts. If the local atomic density is inhomogeneous, these propagation fronts are curved. For sharp edges, the propagation fronts are reflected at the system's boundaries. By extracting the space-dependent variation of the front velocity from the data, we find agreement with theoretical predictions based on curved geodesics of an inhomogeneous metric. This work extends the range of quantum simulations of nonequilibrium field dynamics in general space-time metrics.

Semi-Device-Independently Characterizing Quantum Temporal Correlations.

We develop a framework for characterizing quantum temporal correlations in a general temporal scenario, in which an initial quantum state is measured, sent through a quantum channel, and finally measured again. This framework does not make any assumptions on the system nor on the measurements, namely, it is device independent. It is versatile enough, however, to allow for the addition of further constraints in a semi-device-independent setting. Our framework serves as a natural tool for quantum certification in a temporal scenario when the quantum devices involved are uncharacterized or partially characterized. It can hence also be used for characterizing quantum temporal correlations when one assumes an additional constraint of no-signalling in time, there are upper bounds on the involved systems' dimensions, rank constraints-for which we prove genuine quantum separations over local hidden variable models-or further linear constraints. We present a number of applications, including bounding the maximal violation of temporal Bell inequalities, quantifying temporal steerability, and bounding the maximum successful probability in quantum randomness access codes.

Pseudomagic Quantum States.

Notions of nonstabilizerness, or "magic," quantify how nonclassical quantum states are in a precise sense: states exhibiting low nonstabilizerness preclude quantum advantage. We introduce "pseudomagic" ensembles of quantum states that, despite low nonstabilizerness, are computationally indistinguishable from those with high nonstabilizerness. Previously, such computational indistinguishability has been studied with respect to entanglement, introducing the concept of pseudoentanglement. However, we demonstrate that pseudomagic neither follows from pseudoentanglement nor implies it. In terms of applications, the study of pseudomagic offers fresh insights into the theory of quantum scrambling: it uncovers states that, even though they originate from nonscrambling unitaries, remain indistinguishable from scrambled states to any physical observer. Additional applications include new lower bounds on state synthesis problems, property testing protocols, and implications for quantum cryptography. Our Letter is driven by the observation that only quantities measurable by a computationally bounded observer-intrinsically limited by finite-time computational constraints-hold physical significance. Ultimately, our findings suggest that nonstabilizerness is a "hide-able" characteristic of quantum states: some states are much more magical than is apparent to a computationally bounded observer.

Classical Surrogates for Quantum Learning Models.

The advent of noisy intermediate-scale quantum computers has put the search for possible applications to the forefront of quantum information science. One area where hopes for an advantage through near-term quantum computers are high is quantum machine learning, where variational quantum learning models based on parametrized quantum circuits are discussed. In this work, we introduce the concept of a classical surrogate, a classical model which can be efficiently obtained from a trained quantum learning model and reproduces its input-output relations. As inference can be performed classically, the existence of a classical surrogate greatly enhances the applicability of a quantum learning strategy. However, the classical surrogate also challenges possible advantages of quantum schemes. As it is possible to directly optimize the Ansatz of the classical surrogate, they create a natural benchmark the quantum model has to outperform. We show that large classes of well-analyzed reuploading models have a classical surrogate. We conducted numerical experiments and found that these quantum models show no advantage in performance or trainability in the problems we analyze. This leaves only generalization capability as a possible point of quantum advantage and emphasizes the dire need for a better understanding of inductive biases of quantum learning models.

Dynamical structure factors of dynamical quantum simulators.

The dynamical structure factor is one of the experimental quantities crucial in scrutinizing the validity of the microscopic description of strongly correlated systems. However, despite its long-standing importance, it is exceedingly difficult in generic cases to numerically calculate it, ensuring that the necessary approximations involved yield a correct result. Acknowledging this practical difficulty, we discuss in what way results on the hardness of classically tracking time evolution under local Hamiltonians are precisely inherited by dynamical structure factors and, hence, offer in the same way the potential computational capabilities that dynamical quantum simulators do: We argue that practically accessible variants of the dynamical structure factors are bounded-error quantum polynomial time ([Formula: see text])-hard for general local Hamiltonians. Complementing these conceptual insights, we improve upon a novel, readily available measurement setup allowing for the determination of the dynamical structure factor in different architectures, including arrays of ultra-cold atoms, trapped ions, Rydberg atoms, and superconducting qubits. Our results suggest that quantum simulations employing near-term noisy intermediate-scale quantum devices should allow for the observation of features of dynamical structure factors of correlated quantum matter in the presence of experimental imperfections, for larger system sizes than what is achievable by classical simulation.

Recovering Quantum Correlations in Optical Lattices from Interaction Quenches.

Quantum simulations with ultracold atoms in optical lattices open up an exciting path toward understanding strongly interacting quantum systems. Atom gas microscopes are crucial for this as they offer single-site density resolution, unparalleled in other quantum many-body systems. However, currently a direct measurement of local coherent currents is out of reach. In this Letter, we show how to achieve that by measuring densities that are altered in response to quenches to noninteracting dynamics, e.g., after tilting the optical lattice. For this, we establish a data analysis method solving the closed set of equations relating tunneling currents and atom number dynamics, allowing us to reliably recover the full covariance matrix, including off-diagonal terms representing coherent currents. The signal processing builds upon semidefinite optimization, providing bona fide covariance matrices optimally matching the observed data. We demonstrate how the obtained information about noncommuting observables allows one to quantify entanglement at finite temperature, which opens up the possibility to study quantum correlations in quantum simulations going beyond classical capabilities.

Von Neumann Entropy from Unitarity.

The von Neumann entropy is a key quantity in quantum information theory and, roughly speaking, quantifies the amount of quantum information contained in a state when many identical and independent (i.i.d.) copies of the state are available, in a regime that is often referred to as being asymptotic. In this Letter, we provide a new operational characterization of the von Neumann entropy which neither requires an i.i.d. limit nor any explicit randomness. We do so by showing that the von Neumann entropy fully characterizes single-shot state transitions in unitary quantum mechanics, as long as one has access to a catalyst-an ancillary system that can be reused after the transition-and an environment which has the effect of dephasing in a preferred basis. Building upon these insights, we formulate and provide evidence for the catalytic entropy conjecture, which states that the above result holds true even in the absence of decoherence. If true, this would prove an intimate connection between single-shot state transitions in unitary quantum mechanics and the von Neumann entropy. Our results add significant support to recent insights that, contrary to common wisdom, the standard von Neumann entropy also characterizes single-shot situations and opens up the possibility for operational single-shot interpretations of other standard entropic quantities. We discuss implications of these insights to readings of the third law of quantum thermodynamics and hint at potentially profound implications to holography.

Sample Complexity of Device-Independently Certified "Quantum Supremacy".

Results on the hardness of approximate sampling are seen as important stepping stones toward a convincing demonstration of the superior computational power of quantum devices. The most prominent suggestions for such experiments include boson sampling, instantaneous quantum polynomial time (IQP) circuit sampling, and universal random circuit sampling. A key challenge for any such demonstration is to certify the correct implementation. For all these examples, and in fact for all sufficiently flat distributions, we show that any noninteractive certification from classical samples and a description of the target distribution requires exponentially many uses of the device. Our proofs rely on the same property that is a central ingredient for the approximate hardness results, namely, that the sampling distributions, as random variables depending on the random unitaries defining the problem instances, have small second moments.

Emergence of coherence and the dynamics of quantum phase transitions.

The dynamics of quantum phase transitions pose one of the most challenging problems in modern many-body physics. Here, we study a prototypical example in a clean and well-controlled ultracold atom setup by observing the emergence of coherence when crossing the Mott insulator to superfluid quantum phase transition. In the 1D Bose-Hubbard model, we find perfect agreement between experimental observations and numerical simulations for the resulting coherence length. We, thereby, perform a largely certified analog quantum simulation of this strongly correlated system reaching beyond the regime of free quasiparticles. Experimentally, we additionally explore the emergence of coherence in higher dimensions, where no classical simulations are available, as well as for negative temperatures. For intermediate quench velocities, we observe a power-law behavior of the coherence length, reminiscent of the Kibble-Zurek mechanism. However, we find nonuniversal exponents that cannot be captured by this mechanism or any other known model.

Towards Holography via Quantum Source-Channel Codes.

While originally motivated by quantum computation, quantum error correction (QEC) is currently providing valuable insights into many-body quantum physics, such as topological phases of matter. Furthermore, mounting evidence originating from holography research (AdS/CFT) indicates that QEC should also be pertinent for conformal field theories. With this motivation in mind, we introduce quantum source-channel codes, which combine features of lossy compression and approximate quantum error correction, both of which are predicted in holography. Through a recent construction for approximate recovery maps, we derive guarantees on its erasure decoding performance from calculations of an entropic quantity called conditional mutual information. As an example, we consider Gibbs states of the transverse field Ising model at criticality and provide evidence that they exhibit nontrivial protection from local erasure. This gives rise to the first concrete interpretation of a bona fide conformal field theory as a quantum error correcting code. We argue that quantum source-channel codes are of independent interest beyond holography.

Structure of the Resource Theory of Quantum Coherence.

Quantum coherence is an essential feature of quantum mechanics which is responsible for the departure between the classical and quantum world. The recently established resource theory of quantum coherence studies possible quantum technological applications of quantum coherence, and limitations that arise if one is lacking the ability to establish superpositions. An important open problem in this context is a simple characterization for incoherent operations, constituted by all possible transformations allowed within the resource theory of coherence. In this Letter, we contribute to such a characterization by proving several upper bounds on the maximum number of incoherent Kraus operators in a general incoherent operation. For a single qubit, we show that the number of incoherent Kraus operators is not more than 5, and it remains an open question if this number can be reduced to 4. The presented results are also relevant for quantum thermodynamics, as we demonstrate by introducing the class of Gibbs-preserving strictly incoherent operations, and solving the corresponding mixed-state conversion problem for a single qubit.

Equilibration, thermalisation, and the emergence of statistical mechanics in closed quantum systems.

We review selected advances in the theoretical understanding of complex quantum many-body systems with regard to emergent notions of quantum statistical mechanics. We cover topics such as equilibration and thermalisation in pure state statistical mechanics, the eigenstate thermalisation hypothesis, the equivalence of ensembles, non-equilibration dynamics following global and local quenches as well as ramps. We also address initial state independence, absence of thermalisation, and many-body localisation. We elucidate the role played by key concepts for these phenomena, such as Lieb-Robinson bounds, entanglement growth, typicality arguments, quantum maximum entropy principles and the generalised Gibbs ensembles, and quantum (non-)integrability. We put emphasis on rigorous approaches and present the most important results in a unified language.

Renormalizing Entanglement Distillation.

Entanglement distillation refers to the task of transforming a collection of weakly entangled pairs into fewer highly entangled ones. It is a core ingredient in quantum repeater protocols, which are needed to transmit entanglement over arbitrary distances in order to realize quantum key distribution schemes. Usually, it is assumed that the initial entangled pairs are identically and independently distributed and are uncorrelated with each other, an assumption that might not be reasonable at all in any entanglement generation process involving memory channels. Here, we introduce a framework that captures entanglement distillation in the presence of natural correlations arising from memory channels. Conceptually, we bring together ideas from condensed-matter physics-ideas from renormalization and matrix-product states and operators-with those of local entanglement manipulation, Markov chain mixing, and quantum error correction. We identify meaningful parameter regions for which we prove convergence to maximally entangled states, arising as the fixed points of a matrix-product operator renormalization flow.

Understanding quantum machine learning also requires rethinking generalization.

Quantum machine learning models have shown successful generalization performance even when trained with few data. In this work, through systematic randomization experiments, we show that traditional approaches to understanding generalization fail to explain the behavior of such quantum models. Our experiments reveal that state-of-the-art quantum neural networks accurately fit random states and random labeling of training data. This ability to memorize random data defies current notions of small generalization error, problematizing approaches that build on complexity measures such as the VC dimension, the Rademacher complexity, and all their uniform relatives. We complement our empirical results with a theoretical construction showing that quantum neural networks can fit arbitrary labels to quantum states, hinting at their memorization ability. Our results do not preclude the possibility of good generalization with few training data but rather rule out any possible guarantees based only on the properties of the model family. These findings expose a fundamental challenge in the conventional understanding of generalization in quantum machine learning and highlight the need for a paradigm shift in the study of quantum models for machine learning tasks.

An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory.

It is unclear to what extent quantum algorithms can outperform classical algorithms for problems of combinatorial optimization. In this work, by resorting to computational learning theory and cryptographic notions, we give a fully constructive proof that quantum computers feature a super-polynomial advantage over classical computers in approximating combinatorial optimization problems. Specifically, by building on seminal work by Kearns and Valiant, we provide special instances that are hard for classical computers to approximate up to polynomial factors. Simultaneously, we give a quantum algorithm that can efficiently approximate the optimal solution within a polynomial factor. The quantum advantage in this work is ultimately borrowed from Shor's quantum algorithm for factoring. We introduce an explicit and comprehensive end-to-end construction for the advantage bearing instances. For these instances, quantum computers have, in principle, the power to approximate combinatorial optimization solutions beyond the reach of classical efficient algorithms.

Towards provably efficient quantum algorithms for large-scale machine-learning models.

Large machine learning models are revolutionary technologies of artificial intelligence whose bottlenecks include huge computational expenses, power, and time used both in the pre-training and fine-tuning process. In this work, we show that fault-tolerant quantum computing could possibly provide provably efficient resolutions for generic (stochastic) gradient descent algorithms, scaling as [Formula: see text], where n is the size of the models and T is the number of iterations in the training, as long as the models are both sufficiently dissipative and sparse, with small learning rates. Based on earlier efficient quantum algorithms for dissipative differential equations, we find and prove that similar algorithms work for (stochastic) gradient descent, the primary algorithm for machine learning. In practice, we benchmark instances of large machine learning models from 7 million to 103 million parameters. We find that, in the context of sparse training, a quantum enhancement is possible at the early stage of learning after model pruning, motivating a sparse parameter download and re-upload scheme. Our work shows solidly that fault-tolerant quantum algorithms could potentially contribute to most state-of-the-art, large-scale machine-learning problems.

Breakdown of quasilocality in long-range quantum lattice models.

We study the nonequilibrium dynamics of correlations in quantum lattice models in the presence of long-range interactions decaying asymptotically as a power law. For exponents larger than the lattice dimensionality, a Lieb-Robinson-type bound effectively restricts the spreading of correlations to a causal region, but allows supersonic propagation. We show that this decay is not only sufficient but also necessary. Using tools of quantum metrology, for any exponents smaller than the lattice dimension, we construct Hamiltonians giving rise to quantum channels with capacities not restricted to a causal region. An analytical analysis of long-range Ising models illustrates the disappearance of the causal region and the creation of correlations becoming distance independent. Numerical results obtained using matrix product state methods for the XXZ spin chain reveal the presence of a sound cone for large exponents and supersonic propagation for small ones. In all models we analyzed, the fast spreading of correlations follows a power law, but not the exponential increase of the long-range Lieb-Robinson bound.

Gaussification and entanglement distillation of continuous-variable systems: a unifying picture.

Distillation of entanglement using only Gaussian operations is an important primitive in quantum communication, quantum repeater architectures, and distributed quantum computing. Existing distillation protocols for continuous degrees of freedom are only known to converge to a Gaussian state when measurements yield precisely the vacuum outcome. In sharp contrast, non-Gaussian states can be deterministically converted into Gaussian states while preserving their second moments, albeit by usually reducing their degree of entanglement. In this work-based on a novel instance of a noncommutative central limit theorem-we introduce a picture general enough to encompass the known protocols leading to Gaussian states, and new classes of protocols including multipartite distillation. This gives the experimental option of balancing the merits of success probability against entanglement produced.

Extracting dynamical equations from experimental data is NP hard.

The behavior of any physical system is governed by its underlying dynamical equations. Much of physics is concerned with discovering these dynamical equations and understanding their consequences. In this Letter, we show that, remarkably, identifying the underlying dynamical equation from any amount of experimental data, however precise, is a provably computationally hard problem (it is NP hard), both for classical and quantum mechanical systems. As a by-product of this work, we give complexity-theoretic answers to both the quantum and classical embedding problems, two long-standing open problems in mathematics (the classical problem, in particular, dating back over 70 years).

Thermalization in nature and on a quantum computer.

In this work, we show how Gibbs or thermal states appear dynamically in closed quantum many-body systems, building on the program of dynamical typicality. We introduce a novel perturbation theorem for physically relevant weak system-bath couplings that is applicable even in the thermodynamic limit. We identify conditions under which thermalization happens and discuss the underlying physics. Based on these results, we also present a fully general quantum algorithm for preparing Gibbs states on a quantum computer with a certified runtime and error bound. This complements quantum Metropolis algorithms, which are expected to be efficient but have no known runtime estimates and only work for local Hamiltonians.