Search

Inspired by the hunt for new phases of matter in quantum mixed states, it has recently been proposed that the equivalence of microcanonical and canonical ensembles in statistical mechanics is a manifestation of strong-to-weak spontaneous symmetry breaking (SWSSB) in an underlying many-body quantum description. Here, we build an effective field theory for SWSSB of a global U(1) symmetry; the answer exactly reproduces the Schwinger-Keldysh effective field theory of diffusion for the conserved charge. We conclude that hydrodynamics can be understood as a theory of "superfluidity" for the broken strong symmetry: a non-vanishing susceptibility is a measurable order parameter for SWSSB, the diffusion mode is the Goldstone boson of the spontaneously broken continuous symmetry, and a generalization of Goldstone's Theorem implies that the diffusion mode is always long-lived. This perspective provides a transparent physical explanation for the unusual "reparameterization" symmetries which are a necessary ingredient of Schwinger-Keldysh effective field theories for "normal fluids".

Quantum error correction protects logical quantum information against environmental decoherence by encoding logical qubits into entangled states of physical qubits. One of the most important near-term challenges in building a scalable quantum computer is to reach the break-even point, where logical quantum circuits on error-corrected qubits achieve higher fidelity than equivalent circuits on uncorrected physical qubits. Using Quantinuum's H2 trapped-ion quantum processor, we encode the GHZ state in four logical qubits with fidelity $ 99.5 \pm 0.15 \% \le F \le 99.7 \pm 0.1\% $ (after postselecting on over 98% of outcomes). Using the same quantum processor, we can prepare an uncorrected GHZ state on four physical qubits with fidelity $97.8 \pm 0.2 \% \le F\le 98.7\pm 0.2\%$. The logical qubits are encoded in a $[\![ 25,4,3 ]\!]$ Tanner-transformed long-range-enhanced surface code. Logical entangling gates are implemented using simple swap operations. Our results are a first step towards realizing fault-tolerant quantum computation with logical qubits encoded in geometrically nonlocal quantum low-density parity check codes., Comment: 13 pages, 9 figures, 1 table. v2 changes: added classical simulation data and appendices

We prove the existence of extensive many-body Hamiltonians with few-body interactions and a many-body mobility edge: all eigenstates below a nonzero energy density are localized in an exponentially small fraction of "energetically allowed configurations" within Hilbert space. Our construction is based on quantum perturbations to a classical low-density parity check code. In principle, it is possible to detect this eigenstate localization by measuring few-body correlation functions in efficiently preparable mixed states., Comment: 5+8 pages, 1+0 figures

We provide a systematic framework for constructing generic models of nonequilibrium quantum dynamics with a target stationary (mixed) state. Our framework identifies (almost) all combinations of Hamiltonian and dissipative dynamics that relax to a steady state of interest, generalizing the Davies' generator for dissipative relaxation at finite temperature to nonequilibrium dynamics targeting arbitrary stationary states. We focus on Gibbs states of stabilizer Hamiltonians, identifying local Lindbladians compatible therewith by constraining the rates of dissipative and unitary processes. Moreover, given terms in the Lindbladian not compatible with the target state, our formalism identifies the operations -- including syndrome measurements and local feedback -- one must apply to correct these errors. Our methods also reveal new models of quantum dynamics: for example, we provide a "measurement-induced phase transition" where measurable two-point functions exhibit critical (power-law) scaling with distance at a critical ratio of the transverse field and rate of measurement and feedback. Time-reversal symmetry -- defined naturally within our formalism -- can be broken both in effectively classical, and intrinsically quantum, ways. Our framework provides a systematic starting point for exploring the landscape of quantum dynamical universality classes, as well as identifying new protocols for quantum error correction., Comment: 51 pages, 4 figures

Passive error correction protects logical information forever (in the thermodynamic limit) by updating the system based only on local information and few-body interactions. A paradigmatic example is the classical two-dimensional Ising model: a Metropolis-style Gibbs sampler retains the sign of the initial magnetization (a logical bit) for thermodynamically long times in the low-temperature phase. Known models of passive quantum error correction similarly exhibit thermodynamic phase transitions to a low-temperature phase wherein logical qubits are protected by thermally stable topological order. Here, in contrast, we show that certain families of constant-rate classical and quantum low-density parity check codes have no thermodynamic phase transitions at nonzero temperature, but nonetheless exhibit ergodicity-breaking dynamical transitions: below a critical nonzero temperature, the mixing time of local Gibbs sampling diverges in the thermodynamic limit. Slow Gibbs sampling of such codes enables fault-tolerant passive quantum error correction using finite-depth circuits. This strategy is well suited to measurement-free quantum error correction and may present a desirable experimental alternative to conventional quantum error correction based on syndrome measurements and active feedback., Comment: 32 pages, 9 figures, 1 table; v2 changes: added section on tree-codes, fixed typos

We bound the time necessary to implement the shift unitary on a one-dimensional ring, both using local Hamiltonians and those with power-law interactions. This time is constrained by the Frobenius light cone; hence we prove that shift unitaries are parametrically harder to implement than preparing long-range Bell pairs for sufficiently small power-law exponent. We note an intriguing similarity between the proof of our results, and the hardness of preparing symmetry-protected topological states with symmetry-preserving Hamiltonians., Comment: 17 pages, 1 figure

The quantum mechanics of superconducting circuits is derived by starting from a classical Hamiltonian dynamical system describing a dissipationless circuit, usually made of capacitive and inductive elements. However, standard approaches to circuit quantization treat fluxes and charges, which end up as the canonically conjugate degrees of freedom on phase space, asymmetrically. By combining intuition from topological graph theory with a recent symplectic geometry approach to circuit quantization, we present a theory of circuit quantization that treats charges and fluxes on a manifestly symmetric footing. For planar circuits, known circuit dualities are a natural canonical transformation on the classical phase space. We discuss the extent to which such circuit dualities generalize to non-planar circuits., Comment: 29 pages, 6 figures

We discuss the generic slowing down of quantum dynamics in low energy density states of spatially local Hamiltonians. Beginning with quantum walks of a single particle, we prove that for certain classes of Hamiltonians (deformations of lattice-regularized $H\propto p^{2k}$), the ``butterfly velocity" of particle motion at low energies has an upper bound that must scale as $E^{(2k-1)/2k}$, as expected from dimensional analysis. We generalize these results to obtain bounds on the typical velocities of particles in many-body systems with repulsive interactions, where for certain families of Hubbard-like models we obtain similar scaling., Comment: 12 pages, 0 figures

The surface code is a quantum error-correcting code for one logical qubit, protected by spatially localized parity checks in two dimensions. Due to fundamental constraints from spatial locality, storing more logical qubits requires either sacrificing the robustness of the surface code against errors or increasing the number of physical qubits. We bound the minimal number of spatially nonlocal parity checks necessary to add logical qubits to a surface code while maintaining, or improving, robustness to errors. We asymptotically saturate this bound using a family of hypergraph product codes, interpolating between the surface code and constant-rate low-density parity-check codes. Fault-tolerant protocols for logical gates in the quantum code can be inherited from its classical parent codes. We provide near-term practical implementations of this code for hardware based on trapped ions or neutral atoms in mobile optical tweezers. Long-range-enhanced surface codes outperform conventional surface codes using hundreds of physical qubits and represent a practical strategy to enhance the robustness of logical qubits to errors in near-term devices., Comment: 23 pages, 15 figures; v2 changes: fixed typos and added citations; v3 changes: updated numerics and new logical gadgets

We show that it is possible to perform Heisenberg-limited metrology on GHZ-like states, in the presence of generic spatially local, possibly strong interactions during the measurement process. An explicit protocol, which relies on single-qubit measurements and feedback based on polynomial-time classical computation, achieves the Heisenberg limit. In one dimension, matrix product state methods can be used to perform this classical calculation, while in higher dimensions the cluster expansion underlies the efficient calculations. The latter approach is based on an efficient classical sampling algorithm for short-time quantum dynamics, which may be of independent interest., Comment: 30+7 pages, 3+0 figures. Presented at the 27th Annual Conference on Quantum Information Processing (QIP 2024) as a talk. Accepted for publication in Quantum

The computational complexity of simulating quantum many-body systems generally scales exponentially with the number of particles. This enormous computational cost prohibits first principles simulations of many important problems throughout science, ranging from simulating quantum chemistry to discovering the thermodynamic phase diagram of quantum materials or high-density neutron stars. We present a classical algorithm that samples from a high-temperature quantum Gibbs state in a computational (product state) basis. The runtime grows polynomially with the number of particles, while error vanishes polynomially. This algorithm provides an alternative strategy to existing quantum Monte Carlo methods for overcoming the sign problem. Our result implies that measurement-based quantum computation on a Gibbs state can provide exponential speed up only at sufficiently low temperature, and further constrains what tasks can be exponentially faster on quantum computers., Comment: 4+4 pages; 0+1 figure

Circuit quantization is an extraordinarily successful theory that describes the behavior of quantum circuits with high precision. The most widely used approach of circuit quantization relies on introducing a classical Lagrangian whose degrees of freedom are either magnetic fluxes or electric charges in the circuit. By combining nonlinear circuit elements (such as Josephson junctions or quantum phase slips), it is possible to build circuits where a standard Lagrangian description (and thus the standard quantization method) does not exist. Inspired by the mathematics of symplectic geometry and graph theory, we address this challenge, and present a Hamiltonian formulation of non-dissipative electrodynamic circuits. The resulting procedure for circuit quantization is independent of whether circuit elements are linear or nonlinear, or if the circuit is driven by external biases. We explain how to re-derive known results from our formalism, and provide an efficient algorithm for quantizing circuits, including those that cannot be quantized using existing methods., Comment: 30 pages, 8 figures

We examine the hydrodynamics of systems with spontaneously broken multipolar symmetries using a systematic effective field theory. We focus on the simplest non-trivial setting: a system with charge and dipole symmetry, but without momentum conservation. When no symmetries are broken, our formalism reproduces the quartic subdiffusion ($\omega \sim -i k^4$) characteristic of `fracton hydrodynamics' with conserved dipole moment. Our formalism also captures spontaneous breaking of charge and/or dipole symmetry. When charge symmetry is spontaneously broken, the hydrodynamic modes are quadratically propagating and quartically relaxing ($\omega \sim \pm k^2 - ik^4$). When the dipole symmetry is spontaneously broken but the charge symmetry is preserved, then we find quadratically relaxing (diffusive) transverse modes, plus another mode which depending on parameters may be either purely diffusive ($\omega \sim -i k^2$) or quadratically propagating and quadratically relaxing ($\omega \sim \pm k^2 -i k^2$). Our work provides concrete predictions that may be tested in near-term cold atom experiments, and also lays out a general framework that may be applied to study systems with spontaneously broken multipolar symmetries., Comment: 4+2+epsilon pages, 3 figures

We review the mathematical speed limits on quantum information processing in many-body systems. After the proof of the Lieb-Robinson Theorem in 1972, the past two decades have seen substantial developments in its application to other questions, such as the simulatability of quantum systems on classical or quantum computers, the generation of entanglement, and even the properties of ground states of gapped systems. Moreover, Lieb-Robinson bounds have been extended in non-trivial ways, to demonstrate speed limits in systems with power-law interactions or interacting bosons, and even to prove notions of locality that arise in cartoon models for quantum gravity with all-to-all interactions. We overview the progress which has occurred, highlight the most promising results and techniques, and discuss some central outstanding questions which remain open. To help bring newcomers to the field up to speed, we provide self-contained proofs of the field's most essential results., Comment: review article. 93 pages, 10 figures, 1 table. v2: minor changes

We prove that prethermalization is a generic property of gapped local many-body quantum systems, subjected to small perturbations, in any spatial dimension. More precisely, let $H_0$ be a Hamiltonian, spatially local in $d$ spatial dimensions, with a gap $\Delta$ in the many-body spectrum; let $V$ be a spatially local Hamiltonian consisting of a sum of local terms, each of which is bounded by $\epsilon \ll \Delta$. Then, the approximation that quantum dynamics is restricted to the low-energy subspace of $H_0$ is accurate, in the correlation functions of local operators, for stretched exponential time scale $\tau \sim \exp[(\Delta/\epsilon)^a]$ for any $a<1/(2d-1)$. This result does not depend on whether the perturbation closes the gap. It significantly extends previous rigorous results on prethermalization in models where $H_0$ was frustration-free. We infer the robustness of quantum simulation in low-energy subspaces, the existence of athermal ``scarred" correlation functions in gapped systems subject to generic perturbations, the long lifetime of false vacua in symmetry broken systems, and the robustness of quantum information in non-frustration-free gapped phases with topological order., Comment: 5+35 pages; 1+4 figures, 1+0 tables. v2: added some results, improved presentation

The speed of light $c$ sets a strict upper bound on the speed of information transfer in both classical and quantum systems. In nonrelativistic quantum systems, the Lieb-Robinson Theorem imposes an emergent speed limit $v \hspace{-0.2mm} \ll \hspace{-0.2mm} c$, establishing locality under unitary evolution and constraining the time needed to perform useful quantum tasks. We extend the Lieb-Robinson Theorem to quantum dynamics with measurements. In contrast to the expectation that measurements can arbitrarily violate spatial locality, we find at most an $(M \hspace{-0.5mm} +\hspace{-0.5mm} 1)$-fold enhancement to the speed $v$ of quantum information, provided the outcomes of measurements in $M$ local regions are known. This holds even when classical communication is instantaneous, and extends beyond projective measurements to weak measurements and other nonunitary channels. Our bound is asymptotically optimal, and saturated by existing measurement-based protocols. We tightly constrain the resource requirements for quantum computation, error correction, teleportation, and generating entangled resource states (Bell, GHZ, quantum-critical, Dicke, W, and spin-squeezed states) from short-range-entangled initial states. Our results impose limits on the use of measurements and active feedback to speed up quantum information processing, resolve fundamental questions about the nature of measurements in quantum dynamics, and constrain the scalability of a wide range of proposed quantum technologies., Comment: 24 pages main text + 61 pages SM; main text significantly expanded, includes new Lieb-Robinson bounds, additional discussion, more clarity on main results

We describe a simple quantum error correcting code built out of a time-dependent transverse field Ising model. The code is similar to a repetition code, but has two advantages: an $N$-qubit code can be implemented with a finite-depth spatially local unitary circuit, and it can subsequently protect against both $X$ and $Z$ errors if $N\ge 10$ is even. We propose an implementation of this code with 10 ultracold Rydberg atoms in optical tweezers, along with further generalizations of the code., Comment: 15 pages, 7 figures

During the last two decades many new insights into the dynamics of strongly coupled quantum many-body systems have been obtained using gauge/gravity duality, with black holes often playing a universal role. In this white paper we summarize the results obtained and offer some outlook for future developments, including the ongoing mutually beneficial feedback loop with the study of more general, not necessarily holographic, quantum many-body systems., Comment: 18+24 pages

We prove that quantum information propagates with a finite velocity in any model of interacting bosons whose (possibly time-dependent) Hamiltonian contains spatially local single-boson hopping terms along with arbitrary local density-dependent interactions. More precisely, with density matrix $\rho \propto \exp[-\mu N]$ (with $N$ the total boson number), ensemble averaged correlators of the form $\langle [A_0,B_r(t)]\rangle $, along with out-of-time-ordered correlators, must vanish as the distance $r$ between two local operators grows, unless $t \ge r/v$ for some finite speed $v$. In one dimensional models, we give a useful extension of this result that demonstrates the smallness of all matrix elements of the commutator $[A_0,B_r(t)]$ between finite density states if $t/r$ is sufficiently small. Our bounds are relevant for physically realistic initial conditions in experimentally realized models of interacting bosons. In particular, we prove that $v$ can scale no faster than linear in number density in the Bose-Hubbard model: this scaling matches previous results in the high density limit. The quantum walk formalism underlying our proof provides an alternative method for bounding quantum dynamics in models with unbounded operators and infinite-dimensional Hilbert spaces, where Lieb-Robinson bounds have been notoriously challenging to prove., Comment: 35 pages, 1 figure. v2: substantially extended and published version

In many-body quantum systems with spatially local interactions, quantum information propagates with a finite velocity, reminiscent of the ``light cone" of relativity. In systems with long-range interactions which decay with distance $r$ as $1/r^\alpha$, however, there are multiple light cones which control different information theoretic tasks. We show an optimal (up to logarithms) ``Frobenius light cone" obeying $t\sim r^{\min(\alpha-1,1)}$ for $\alpha>1$ in one-dimensional power-law interacting systems with finite local dimension: this controls, among other physical properties, the butterfly velocity characterizing many-body chaos and operator growth. We construct an explicit random Hamiltonian protocol that saturates the bound and settles the optimal Frobenius light cone in one dimension. We partially extend our constraints on the Frobenius light cone to a several operator $p$-norms, and show that Lieb-Robinson bounds can be saturated in at most an exponentially small $e^{-\Omega(r)}$ fraction of the many-body Hilbert space., Comment: 17+20 pages, 3+1 figures. v2: expanded and published version

The Lieb-Robinson theorem states that information propagates with a finite velocity in quantum systems on a lattice with nearest-neighbor interactions. What are the speed limits on information propagation in quantum systems with power-law interactions, which decay as $1/r^\alpha$ at distance $r$? Here, we present a definitive answer to this question for all exponents $\alpha>2d$ and all spatial dimensions $d$. Schematically, information takes time at least $r^{\min\{1, \alpha-2d\}}$ to propagate a distance~$r$. As recent state transfer protocols saturate this bound, our work closes a decades-long hunt for optimal Lieb-Robinson bounds on quantum information dynamics with power-law interactions.

We present a framework for understanding the dynamics of operator size, and bounding the growth of out-of-time-ordered correlators, in models of large-$S$ spins. Focusing on the dynamics of a single spin, we show the finiteness of the Lyapunov exponent in the large-$S$ limit; our bounds are tighter than the best known Lieb-Robinson-type bounds on these systems. We numerically find our upper bound on Lyapunov exponents is within an order of magnitude of numerically computed values in classical and quantum kicked top models. Generalizing our results to coupled large-$S$ spins on lattices, we show that the butterfly velocity, which characterizes the spatial speed of quantum information scrambling, is finite as $S\rightarrow\infty$. We emphasize qualitative differences between operator growth in semiclassical large-spin models, and quantum holographic systems including the Sachdev-Ye-Kitaev model., Comment: 7+3 pages, 2 figures. v2: modified/improved Lieb-Robinson and quantum walk bounds. v3: published version

We present an optimal protocol for encoding an unknown qubit state into a multiqubit Greenberger-Horne-Zeilinger-like state and, consequently, transferring quantum information in large systems exhibiting power-law ($1/r^\alpha$) interactions. For all power-law exponents $\alpha$ between $d$ and $2d+1$, where $d$ is the dimension of the system, the protocol yields a polynomial speedup for $\alpha>2d$ and a superpolynomial speedup for $\alpha\leq 2d$, compared to the state of the art. For all $\alpha>d$, the protocol saturates the Lieb-Robinson bounds (up to subpolynomial corrections), thereby establishing the optimality of the protocol and the tightness of the bounds in this regime. The protocol has a wide range of applications, including in quantum sensing, quantum computing, and preparation of topologically ordered states. In addition, the protocol provides a lower bound on the gate count in digital simulations of power-law interacting systems., Comment: Updated Table I, Additional discussion on a lower bound for the gate count in digital quantum simulation

We study the entanglement dynamics in a generic quantum automaton circuit subjected to projective measurements. We design an efficient algorithm which not only allows us to perform large scale simulation for the R\'enyi entropy but also provides a physical picture for the entanglement dynamics, which can be interpreted in terms of a classical bit-string model which belongs to the directed percolation universality class. We study the purification dynamics of a state formed by EPR pairs, and the growth of entanglement starting from a product state. In both cases, we verify numerically that the dynamics is in the universality class of classical directed percolation., Comment: 16 pages, 16 figures

We describe an efficient protocol to perform quantum state transfer using Hamiltonian dynamics with long-range interactions. The time to transfer $n$ qubits a sufficiently large distance is proportional to $\sqrt{n}$. Even without error correction, the fidelity of this multi-qubit state transfer process remains finite for arbitrarily well-separated qubits in the presence of uncorrelated random errors in coupling constants., Comment: 14 pages, 6 figures

We study quantum many-body systems with a global U(1) conservation law, focusing on a theory of $N$ interacting fermions with charge conservation, or $N$ interacting spins with one conserved component of total spin. We define an effective operator size at finite chemical potential through suitably regularized out-of-time-ordered correlation functions. The growth rate of this density-dependent operator size vanishes algebraically with charge density; hence we obtain new bounds on Lyapunov exponents and butterfly velocities in charged systems at a given density, which are parametrically stronger than any Lieb-Robinson bound. We argue that the density dependence of our bound on the Lyapunov exponent is saturated in the charged Sachdev-Ye-Kitaev model. We also study random automaton quantum circuits and Brownian Sachdev-Ye-Kitaev models, each of which exhibit a different density dependence for the Lyapunov exponent, and explain the discrepancy. We propose that our results are a cartoon for understanding Planckian-limited energy-conserving dynamics at finite temperature., Comment: 17+3 pages; 3+1 figures; v2, v3: minor changes

We study operator growth in a model of $N(N-1)/2$ interacting Majorana fermions, which live on the edges of a complete graph of $N$ vertices. Terms in the Hamiltonian are proportional to the product of $q$ fermions which live on the edges of cycles of length $q$. This model is a cartoon "matrix model": the interaction graph mimics that of a single-trace matrix model, which can be holographically dual to quantum gravity. We prove (non-perturbatively in $1/N$, and without averaging over any ensemble) that the scrambling time of this model is at least of order $\log N$, consistent with the fast scrambling conjecture. We comment on apparent similarities and differences between operator growth in our "matrix model" and in the melonic models., Comment: 17 pages, 1 figure

We prove bounds on operator growth and infinite temperature out-of-time-ordered correlators in many-body systems with $N$ spin-$\frac{1}{2}$ degrees of freedom which interact via two-body all-to-all interactions. Our results parametrically improve previous bounds, and sharply constrain when and how quantum simulators, including trapped ion crystals and cavity quantum electrodynamics, can study quantum gravity., Comment: 8 pages. v2: added result on tightness. v3: published version

We present random quantum circuit models for non-unitary quantum dynamics of free fermions in one spatial dimension. Numerical simulations reveal that the dynamics tends towards steady states with logarithmic violations of the entanglement area law and power law correlation functions. Moreover, starting with a short-range entangled many-body state, the dynamical evolution of entanglement and correlations quantitatively agrees with the predictions of two-dimensional conformal field theory with a space-like time direction. We argue that this behavior is generic in non-unitary free quantum dynamics with time-dependent randomness, and show that the emergent conformal dynamics of two-point functions arises out of a simple "nonlinear master equation".

We introduce new classes of hydrodynamic theories inspired by the recently discovered fracton phases of quantum matter. Fracton phases are characterized by elementary excitations (fractons) with restricted mobility. The hydrodynamic theories we introduce describe thermalization in systems with fracton-like mobility constraints, including fluids where charge and dipole moment are both locally conserved, and fluids where charge is conserved along every line or plane of a lattice. Each of these fluids is subdiffusive, and constitutes a new universality class of hydrodynamic behavior. There are infinitely many such classes, each with distinct subdiffusive exponents, all of which are captured by our formalism. Our framework naturally explains recent results on dynamics with constrained quantum circuits, as well as recent experiments with ultracold atoms in tilted optical lattices. We identify crisp experimental signatures of these novel hydrodynamics, and explain how they may be realized in near term ultracold atom experiments., Comment: 5 + 10 pages. v2: minor revisions; references added. v3: published version, with a few additional results

In quantum many-body systems with local interactions, quantum information and entanglement cannot spread outside of a linear light cone, which expands at an emergent velocity analogous to the speed of light. Local operations at sufficiently separated spacetime points approximately commute -- given a many-body state, $\mathcal{O}_x(t) \mathcal{O}_y |\psi\rangle \approx \mathcal{O}_y\mathcal{O}_x(t) |\psi\rangle$ with arbitrarily small errors -- so long as $|x-y|\gtrsim vt$, where $v$ is finite. Yet most non-relativistic physical systems realized in nature have long-range interactions: two degrees of freedom separated by a distance $r$ interact with potential energy $V(r) \propto 1/r^{\alpha}$. In systems with long-range interactions, we rigorously establish a hierarchy of linear light cones: at the same $\alpha$, some quantum information processing tasks are constrained by a linear light cone while others are not. In one spatial dimension, this linear light cone exists for every many-body state when $\alpha>3$ (Lieb-Robinson light cone); for a typical state chosen uniformly at random from the Hilbert space when $\alpha>\frac{5}{2}$ (Frobenius light cone); for every state of a non-interacting system when $\alpha>2$ (free light cone). These bounds apply to time-dependent systems and are optimal up to subalgebraic improvements. Our theorems regarding the Lieb-Robinson and free light cones -- and their tightness -- also generalize to arbitrary dimensions. We discuss the implications of our bounds on the growth of connected correlators and of topological order, the clustering of correlations in gapped systems, and the digital simulation of systems with long-range interactions. In addition, we show that universal quantum state transfer, as well as many-body quantum chaos, are bounded by the Frobenius light cone, and therefore are poorly constrained by all Lieb-Robinson bounds., Comment: 36 pages; 6 figures; v2: revised and expanded introduction, a few extra results; v3: minor revisions. v4: corrections in Section 7

We explore quantum dynamics in Floquet many-body systems with local conservation laws in one spatial dimension, focusing on sectors of the Hilbert space which are highly polarized. We numerically compare the predicted charge diffusion constants and quantum butterfly velocity of operator growth between models of chaotic Floquet dynamics (with discrete spacetime translation invariance) and random unitary circuits which vary both in space and time. We find that for small but finite polarization per length (in the thermodynamic limit), the random unitary circuit correctly predicts the scaling of the butterfly velocity but incorrectly predicts the scaling of the diffusion constant. We argue that this is a consequence of quantum coherence on short time scales. Our work clarifies the settings in which random unitary circuits provide correct physical predictions for non-random chaotic systems, and sheds light into the origin of the slow down of the butterfly effect in highly polarized systems or at low temperature., Comment: 9 + 4 pages; 7 figures; v2: published version

We prove non-perturbative bounds on the time evolution of the probability distribution of operator size in the $q$-local Sachdev-Ye-Kitaev model with $N$ fermions, for any even integer $q>2$ and any positive even integer $N>2q$. If the couplings in the Hamiltonian are independent and identically distributed Rademacher random variables, the infinite temperature many-body Lyapunov exponent is almost surely finite as $N\rightarrow\infty$. In the limit $q \rightarrow \infty$, $N\rightarrow \infty$, $q^{6+\delta}/N \rightarrow 0$, the shape of the size distribution of a growing fermion, obtained by leading order perturbation calculations in $1/N$ and $1/q$, is similar to a distribution that locally saturates our constraints. Our proof is not based on Feynman diagram resummation; instead, we note that the operator size distribution obeys a continuous time quantum walk with bounded transition rates, to which we apply concentration bounds from classical probability theory., Comment: 23 pages. v2: published version

In a locally interacting many-body system, two isolated qubits, separated by a large distance $r$, become correlated and entangled with each other at a time $t \ge r/v$. This finite speed $v$ of quantum information scrambling limits quantum information processing, thermalization and even equilibrium correlations. Yet most experimental systems contain long range power law interactions -- qubits separated by $r$ have potential energy $V(r)\propto r^{-\alpha}$. Examples include the long range Coulomb interactions in plasma ($\alpha=1$) and dipolar interactions between spins ($\alpha=3$). In one spatial dimension, we prove that the speed of quantum scrambling remains finite for sufficiently large $\alpha$. This result parametrically improves previous bounds, compares favorably with recent numerical simulations, and can be realized in quantum simulators with dipolar interactions. Our new mathematical methods lead to improved algorithms for classically simulating quantum systems, and improve bounds on environmental decoherence in experimental quantum information processors., Comment: 4+10 pages; 1+1 figures; v2: corrected an error; v3: published version

Let $A$ and $B$ be local operators in Hamiltonian quantum systems with $N $ degrees of freedom and finite-dimensional Hilbert space. We prove that the commutator norm $\lVert [A(t),B]\rVert$ is upper bounded by a topological combinatorial problem: counting irreducible weighted paths between two points on the Hamiltonian's factor graph. Our bounds sharpen existing Lieb-Robinson bounds by removing extraneous growth. In quantum systems drawn from zero-mean random ensembles with few-body interactions, we prove stronger bounds on the ensemble-averaged out-of-time-ordered correlator $\mathbb{E}\left[ \lVert [A(t),B]\rVert_F^2\right]$. In such quantum systems on Erd\"os-R\'enyi factor graphs, we prove that the scrambling time $t_{\mathrm{s}}$, at which $\lvert [A(t),B]\rVert_F=\mathrm{\Theta}(1)$, is almost surely $t_{\mathrm{s}}=\mathrm{\Omega}(\sqrt{\log N})$; we further prove $t_{\mathrm{s}}=\mathrm{\Omega}(\log N) $ to high order in perturbation theory in $1/N$. We constrain infinite temperature quantum chaos in the $q$-local Sachdev-Ye-Kitaev model at any order in $1/N$; at leading order, our upper bound on the Lyapunov exponent is within a factor of 2 of the known result at any $q>2$. We also speculate on the implications of our theorems for conjectured holographic descriptions of quantum gravity., Comment: 49 pages, 14 figures. v2: published version with errors fixed

We study 2-local Hamiltonian quantum systems, consisting of qubits interacting on the star graph of N vertices. We numerically demonstrate that these models are generically non-integrable at infinite temperature, and find evidence for a finite temperature phase transition to a glassy phase in generic models. Operators can become complicated in constant time: we explicitly find that there is no bound on out-of-time-ordered correlators, even at finite temperature. Operator growth is not correctly modeled by stochastic quantum dynamics, including Brownian Hamiltonian dynamics or random unitary circuits. The star graph (and similar constructions) may serve as a useful testing ground for conjectures about universality, quantum chaos and Planckian dissipation in k-local systems, including in experimental quantum simulators., Comment: 30 pages, 14 figures; v2: minor changes

Today, hardware constraints are an important limitation on quantum adiabatic optimization algorithms. Firstly, computational problems must be formulated as quadratic unconstrained binary optimization (QUBO) in the presence of noisy coupling constants. Secondly, the interaction graph of the QUBO must have an effective minor embedding into a two-dimensional nonplanar lattice graph. We describe new strategies for constructing QUBOs for NP-complete/hard combinatorial problems that address both of these challenges. Our results include asymptotically improved embeddings for number partitioning, filling knapsacks, graph coloring, and finding Hamiltonian cycles. These embeddings can be also be found with reduced computational effort. Our new embedding for number partitioning may be more effective on next-generation hardware., Comment: 26+7 pages; 9+1 figures

We study dynamics of a locally conserved energy in ergodic, local many-body quantum systems on a lattice with no additional symmetry. The resulting dynamics is well approximated by a coarse grained, classical linear functional diffusion equation for the probability of all spatial configurations of energy. This is equivalent to nonlinear stochastic hydrodynamics, describing the diffusion of energy in physical spacetime. We find the absence of non-hydrodynamic slow degrees of freedom, a nonlinear fluctuation-dissipation theorem, and the emergence of a (weakly interacting) kinetic theory for hydrodynamic modes near thermal equilibrium. The observable part of the microscopic entropy obeys the local second law of thermodynamics, and quantitatively agrees with the phenomenological predictions of hydrodynamics. Our approach naturally generalizes to ergodic systems with additional symmetries, may lead to numerical algorithms to calculate diffusion constants for lattice models, and implies sufficiency conditions for a rigorous derivation of hydrodynamics in quantum systems., Comment: 28 pages, 2 figures. v2: published version

It has long been believed that dissipative time scales $\tau$ obey a "Planckian" bound $\tau \gtrsim \frac{\hbar}{k_{\mathrm{B}}T}$ in strongly coupled quantum systems. Despite much circumstantial evidence, however, there is no known $\tau$ for which this bound is universal. Here we define operator size at finite temperature, and conjecture such a $\tau$: the time scale over which small operators become large. All known many-body theories are consistent with this conjecture. This proposed bound explains why previously conjectured Planckian bounds do not always apply to weakly coupled theories, and how Planckian time scales can be relevant to both transport and chaos., Comment: 8+14 pages; 1+0 figures; v2: major revisions, published version

Given a quantum many-body system with few-body interactions, how rapidly can quantum information be hidden during time evolution? The fast scrambling conjecture is that the time to thoroughly mix information among N degrees of freedom grows at least logarithmically in N. We derive this inequality for generic quantum systems at infinite temperature, bounding the scrambling time by a finite decay time of local quantum correlations at late times. Using Lieb-Robinson bounds, generalized Sachdev-Ye-Kitaev models, and random unitary circuits, we propose that a logarithmic scrambling time can be achieved in most quantum systems with sparse connectivity. These models also elucidate how quantum chaos is not universally related to scrambling: we construct random few-body circuits with infinite Lyapunov exponent but logarithmic scrambling time. We discuss analogies between quantum models on graphs and quantum black holes, and suggest methods to experimentally study scrambling with as many as 100 sparsely-connected quantum degrees of freedom., Comment: 11+24 pages; 1+3 figures. v2: minor revisions, added references. v3: many revisions to improve presentation

We provide Ising formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems. This collects and extends mappings to the Ising model from partitioning, covering and satisfiability. In each case, the required number of spins is at most cubic in the size of the problem. This work may be useful in designing adiabatic quantum optimization algorithms., Comment: 27 pages; v2: substantial revision to intro/conclusion, many more references; v3: substantial revision and extension, to-be-published version