Search

In this work we give an efficient construction of unitary $k$-designs using $\tilde{O}(k\cdot poly(n))$ quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over $S(N)$ to random unitaries over $U(N)$ for $N=2^n$. In particular, we show that products of exponentiated sums of $S(N)$ permutations with random phases approximately match the first $2^{\Omega(n)}$ moments of the Haar measure. By substituting either $\tilde{O}(k)$-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-$N$ by interpolating from the much simpler large-$N$ limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-$N$ expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension $N$., Comment: 70 pages, 11 figures

The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered., Comment: Survey document with wiki-like modular structure. 337 pages, including bibliography and sub-bibliographies. Comments welcome

Quantum error correction with erasure qubits promises significant advantages over standard error correction due to favorable thresholds for erasure errors. To realize this advantage in practice requires a qubit for which nearly all errors are such erasure errors, and the ability to check for erasure errors without dephasing the qubit. We demonstrate that a "dual-rail qubit" consisting of a pair of resonantly coupled transmons can form a highly coherent erasure qubit, where transmon $T_1$ errors are converted into erasure errors and residual dephasing is strongly suppressed, leading to millisecond-scale coherence within the qubit subspace. We show that single-qubit gates are limited primarily by erasure errors, with erasure probability $p_\text{erasure} = 2.19(2)\times 10^{-3}$ per gate while the residual errors are $\sim 40$ times lower. We further demonstrate mid-circuit detection of erasure errors while introducing $< 0.1\%$ dephasing error per check. Finally, we show that the suppression of transmon noise allows this dual-rail qubit to preserve high coherence over a broad tunable operating range, offering an improved capacity to avoid frequency collisions. This work establishes transmon-based dual-rail qubits as an attractive building block for hardware-efficient quantum error correction., Comment: 9+13 pages, 16 figures

Preparing ground states and thermal states is essential for simulating quantum systems on quantum computers. Despite the hope for practical quantum advantage in quantum simulation, popular state preparation approaches have been challenged. Monte Carlo-style quantum Gibbs samplers have emerged as an alternative, but prior proposals have been unsatisfactory due to technical obstacles rooted in energy-time uncertainty. We introduce simple continuous-time quantum Gibbs samplers that overcome these obstacles by efficiently simulating Nature-inspired quantum master equations (Lindbladians). In addition, we construct the first provably accurate and efficient algorithm for preparing certain purified Gibbs states (called thermal field double states in high-energy physics) of rapidly thermalizing systems; this algorithm also benefits from a quantum walk speedup. Our algorithms' costs have a provable dependence on temperature, accuracy, and the mixing time (or spectral gap) of the relevant Lindbladian. We complete the first rigorous proof of finite-time thermalization for physically derived Lindbladians by developing a general analytic framework for nonasymptotic secular approximation and approximate detailed balance. Given the success of classical Markov chain Monte Carlo (MCMC) algorithms and the ubiquity of thermodynamics, we anticipate that quantum Gibbs sampling will become indispensable in quantum computing., Comment: 79 pages, 12 figures; v2 modified table 1 and improved presentation and bounds

A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. For this task, there is a well-studied quantum algorithm that performs quantum phase estimation on an initial trial state that has a nonnegligible overlap with a low-energy state. However, it is notoriously hard to give theoretical guarantees that such a trial state can be prepared efficiently. Moreover, the heuristic proposals that are currently available, such as with adiabatic state preparation, appear insufficient in practical cases. This paper shows that, for most random sparse Hamiltonians, the maximally mixed state is a sufficiently good trial state, and phase estimation efficiently prepares states with energy arbitrarily close to the ground energy. Furthermore, any low-energy state must have nonnegligible quantum circuit complexity, suggesting that low-energy states are classically nontrivial and phase estimation is the optimal method for preparing such states (up to polynomial factors). These statements hold for two models of random Hamiltonians: (i) a sum of random signed Pauli strings and (ii) a random signed $d$-sparse Hamiltonian. The main technical argument is based on some new results in nonasymptotic random matrix theory. In particular, a refined concentration bound for the spectral density is required to obtain complexity guarantees for these random Hamiltonians., Comment: 33 pages, 4 figures

We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems, including Quadratic Unconstrained Binary Optimization (QUBO), Ising spin glasses ($p$-spin model), and $k$-local constraint satisfaction problems ($k$-CSP). We show that either (a) the algorithm finds the optimal solution in time $O^*(2^{(0.5-c)n})$ for an $n$-independent constant $c$, a $2^{cn}$ advantage over Grover's algorithm; or (b) there are sufficiently many low-cost solutions such that classical random guessing produces a $(1-\eta)$ approximation to the optimal cost value in sub-exponential time for arbitrarily small choice of $\eta$. Additionally, we show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case. The algorithm and its analysis is largely inspired by Hastings' short-path algorithm [$\textit{Quantum}$ $\textbf{2}$ (2018) 78]., Comment: 49 pages, 3 figures

We study quantum interior point methods (QIPMs) for second-order cone programming (SOCP), guided by the example use case of portfolio optimization (PO). We provide a complete quantum circuit-level description of the algorithm from problem input to problem output, making several improvements to the implementation of the QIPM. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm, including constant factors. The resource counts we find depend on instance-specific parameters, such as the condition number of certain linear systems within the problem. To determine the size of these parameters, we perform numerical simulations of small PO instances, which lead to concrete resource estimates for the PO use case. Our numerical results do not probe large enough instance sizes to make conclusive statements about the asymptotic scaling of the algorithm. However, already at small instance sizes, our analysis suggests that, due primarily to large constant pre-factors, poorly conditioned linear systems, and a fundamental reliance on costly quantum state tomography, fundamental improvements to the QIPM are required for it to lead to practical quantum advantage., Comment: 40 pages, 15 figures. v2: minor corrections and updates to match journal version

We show that the proof of the generalised quantum Stein's lemma [Brand\~ao & Plenio, Commun. Math. Phys. 295, 791 (2010)] is not correct due to a gap in the argument leading to Lemma III.9. Hence, the main achievability result of Brand\~ao & Plenio is not known to hold. This puts into question a number of established results in the literature, in particular the reversibility of quantum entanglement [Brand\~ao & Plenio, Commun. Math. Phys. 295, 829 (2010); Nat. Phys. 4, 873 (2008)] and of general quantum resources [Brand\~ao & Gour, Phys. Rev. Lett. 115, 070503 (2015)] under asymptotically resource non-generating operations. We discuss potential ways to recover variants of the newly unsettled results using other approaches., Comment: 28 pages; in v2 we added Section V.D and Section VI, and corrected several small typos; v3 is close to the published version

The Eigenstate Thermalization Hypothesis (ETH) has played a major role in understanding thermodynamic phenomena in closed quantum systems. However, its connection to the timescale of thermalization for open system dynamics has remained elusive. This paper establishes a rigorous link between ETH and fast thermalization to the global Gibbs state. Specifically, we demonstrate fast thermalization for a system coupled weakly to a bath of quasi-free Fermions that we refresh periodically. To describe the joint evolution, we derive a finite-time version of Davies' generator with explicit error bounds and resource estimates. Our approach exploits a critical feature of ETH: operators in the energy basis can be modeled by independent random matrices in a near-diagonal band. This gives quantum expanders at nearby eigenstates of the Hamiltonian and reduces the problem to a one-dimensional classical random walk on the energy eigenstates. Our results explain finite-time thermalization in chaotic open quantum systems., Comment: 62 pages, 13 figures. Corrections in v2 for the system-bath joint evolution; dropped discussion on Quantum Metropolis Sampling due to impossible phase estimation assumption in v3

We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. We show that, for local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_{\text{noisy}}$ of a generic noisy circuit instance and the output distribution $p_{\text{ideal}}$ of the corresponding noiseless instance shrink exponentially with the expected number of gate-level errors, as $F=\text{exp}(-2s\epsilon \pm O(s\epsilon^2))$, where $\epsilon$ is the probability of error per circuit location and $s$ is the number of two-qubit gates. Furthermore, if the noise is incoherent, the output distribution approaches the uniform distribution $p_{\text{unif}}$ at precisely the same rate and can be approximated as $p_{\text{noisy}} \approx Fp_{\text{ideal}} + (1-F)p_{\text{unif}}$, that is, local errors are scrambled by the random quantum circuit and contribute only white noise (uniform output). Importantly, we upper bound the total variation error (averaged over random circuit instance) in this approximation as $O(F\epsilon \sqrt{s})$, so the "white-noise approximation" is meaningful when $\epsilon \sqrt{s} \ll 1$, a quadratically weaker condition than the $\epsilon s\ll 1$ requirement to maintain high fidelity. The bound applies when the circuit size satisfies $s \geq \Omega(n\log(n))$ and the inverse error rate satisfies $\epsilon^{-1} \geq \tilde{\Omega}(n)$. The white-noise approximation is useful for salvaging the signal from a noisy quantum computation; it was an underlying assumption in complexity-theoretic arguments that low-fidelity random quantum circuits cannot be efficiently sampled classically. Our method is based on a map from second-moment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds., Comment: 76 pages, 6 figures

Quantum simulation is a promising application of future quantum computers. Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. For an accurate product formula approximation, the state-of-the-art gate complexity depends on the number of terms in the Hamiltonian and a local energy estimate. In this work, we give evidence that product formulas, in practice, may work much better than expected. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states, while the existing estimate is for the worst states. For general $k$-local Hamiltonians and higher-order product formulas, we obtain gate count estimates for input states drawn from any orthogonal basis. The gate complexity significantly improves over the worst case for systems with large connectivity. Our typical-case results generalize to Hamiltonians with Fermionic terms, with input states drawn from a fixed-particle number subspace, and with Gaussian coefficients (e.g., the SYK models). Technically, we employ a family of simple but versatile inequalities from non-commutative martingales called $\textit{uniform smoothness}$, which leads to $\textit{Hypercontractivity}$, namely $p$-norm estimates for $k$-local operators. This delivers concentration bounds via Markov's inequality. For optimality, we give analytic and numerical examples that simultaneously match our typical-case estimates and the existing worst-case estimates. Therefore, our improvement is due to asking a qualitatively different question, and our results open doors to the study of quantum algorithms in the average case., Comment: 51 pages, 10 figures; v2 improved presentation and included numerical simulation

Protected qubits such as the 0-$\pi$ qubit, and bosonic qubits including cat qubits and GKP qubits offer advantages for fault-tolerance. Some of these protected qubits (e.g., 0-$\pi$ qubit and Kerr cat qubit) are stabilized by Hamiltonians which have (near-)degenerate ground state manifolds with large energy-gaps to the excited state manifolds. Without dissipative stabilization mechanisms the performance of such energy-gap-protected qubits can be limited by leakage to excited states. Here, we propose a scheme for dissipatively stabilizing an energy-gap-protected qubit using colored (i.e., frequency-selective) dissipation without inducing errors in the ground state manifold. Concretely we apply our colored dissipation technique to Kerr cat qubits and propose colored Kerr cat qubits which are protected by an engineered colored single-photon loss. When applied to the Kerr cat qubits our scheme significantly suppresses leakage-induced bit-flip errors (which we show are a limiting error mechanism) while only using linear interactions. Beyond the benefits to the Kerr cat qubit we also show that our frequency-selective loss technique can be applied to a broader class of protected qubits., Comment: 19 pages, 10 figures, comments welcome!

Stabilized cat codes can provide a biased noise channel with a set of bias-preserving (BP) gates, which can significantly reduce the resource overhead for fault-tolerant quantum computing. All existing schemes of BP gates, however, require adiabatic quantum evolution, with performance limited by excitation loss and non-adiabatic errors during the adiabatic gates. In this work, we apply a derivative-based leakage suppression technique to overcome non-adiabatic errors, so that we can implement fast BP gates on Kerr-cat qubits with improved gate fidelity while maintaining high noise bias. When applied to concatenated quantum error correction, the fast BP gates can not only improve the logical error rate but also reduce resource overhead, which enables more efficient implementation of fault-tolerant quantum computing.

Fault-tolerant quantum error correction is essential for implementing quantum algorithms of significant practical importance. In this work, we propose a highly effective use of the surface-GKP code, i.e., the surface code consisting of bosonic GKP qubits instead of bare two-dimensional qubits. In our proposal, we use error-corrected two-qubit gates between GKP qubits and introduce a maximum likelihood decoding strategy for correcting shift errors in the two-GKP-qubit gates. Our proposed decoding reduces the total CNOT failure rate of the GKP qubits, e.g., from $0.87\%$ to $0.36\%$ at a GKP squeezing of $12$dB, compared to the case where the simple closest-integer decoding is used. Then, by concatenating the GKP code with the surface code, we find that the threshold GKP squeezing is given by $9.9$dB under the the assumption that finite-squeezing of the GKP states is the dominant noise source. More importantly, we show that a low logical failure rate $p_{L} < 10^{-7}$ can be achieved with moderate hardware requirements, e.g., $291$ modes and $97$ qubits at a GKP squeezing of $12$dB as opposed to $1457$ bare qubits for the standard rotated surface code at an equivalent noise level (i.e., $p=0.36\%$). Such a low failure rate of our surface-GKP code is possible through the use of space-time correlated edges in the matching graphs of the surface code decoder. Further, all edge weights in the matching graphs are computed dynamically based on analog information from the GKP error correction using the full history of all syndrome measurement rounds. We also show that a highly-squeezed GKP state of GKP squeezing $\gtrsim 12$dB can be experimentally realized by using a dissipative stabilization method, namely, the Big-small-Big method, with fairly conservative experimental parameters. Lastly, we introduce a three-level ancilla scheme to mitigate ancilla decay errors during a GKP state preparation., Comment: 41 pages, 14 figures, 3 tables

Producing quantum states at random has become increasingly important in modern quantum science, with applications both theoretical and practical. In particular, ensembles of such randomly-distributed, but pure, quantum states underly our understanding of complexity in quantum circuits and black holes, and have been used for benchmarking quantum devices in tests of quantum advantage. However, creating random ensembles has necessitated a high degree of spatio-temporal control, placing such studies out of reach for a wide class of quantum systems. Here we solve this problem by predicting and experimentally observing the emergence of random state ensembles naturally under time-independent Hamiltonian dynamics, which we use to implement an efficient, widely applicable benchmarking protocol. The observed random ensembles emerge from projective measurements and are intimately linked to universal correlations built up between subsystems of a larger quantum system, offering new insights into quantum thermalization. Predicated on this discovery, we develop a fidelity estimation scheme, which we demonstrate for a Rydberg quantum simulator with up to 25 atoms using fewer than 10^4 experimental samples. This method has broad applicability, as we show for Hamiltonian parameter estimation, target-state generation benchmarking, and comparison of analog and digital quantum devices. Our work has implications for understanding randomness in quantum dynamics, and enables applications of this concept in a much wider context., Comment: JC and ALS contributed equally to this work

We present a comprehensive architectural analysis for a proposed fault-tolerant quantum computer based on cat codes concatenated with outer quantum error-correcting codes. For the physical hardware, we propose a system of acoustic resonators coupled to superconducting circuits with a two-dimensional layout. Using estimated physical parameters for the hardware, we perform a detailed error analysis of measurements and gates, including CNOT and Toffoli gates. Having built a realistic noise model, we numerically simulate quantum error correction when the outer code is either a repetition code or a thin rectangular surface code. Our next step toward universal fault-tolerant quantum computation is a protocol for fault-tolerant Toffoli magic state preparation that significantly improves upon the fidelity of physical Toffoli gates at very low qubit cost. To achieve even lower overheads, we devise a new magic-state distillation protocol for Toffoli states. Combining these results together, we obtain realistic full-resource estimates of the physical error rates and overheads needed to run useful fault-tolerant quantum algorithms. We find that with around 1,000 superconducting circuit components, one could construct a fault-tolerant quantum computer that can run circuits which are currently intractable for classical computers. Hardware with 18,000 superconducting circuit components, in turn, could simulate the Hubbard model in a regime beyond the reach of classical computing., Comment: 117 pages (main text 32 pages), 62 figures, 15 tables. Comments welcome! V2 adds additional appendices and conforms to journal specifications

We consider quantum circuits consisting of randomly chosen two-local gates and study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated, roughly meaning that the probability mass is not too concentrated on a small number of measurement outcomes. Understanding the conditions for anti-concentration is important for determining which quantum circuits are difficult to simulate classically, as anti-concentration has been in some cases an ingredient of mathematical arguments that simulation is hard and in other cases a necessary condition for easy simulation. Our definition of anti-concentration is that the expected collision probability, that is, the probability that two independently drawn outcomes will agree, is only a constant factor larger than if the distribution were uniform. We show that when the 2-local gates are each drawn from the Haar measure (or any two-design), at least $\Omega(n \log(n))$ gates (and thus $\Omega(\log(n))$ circuit depth) are needed for this condition to be met on an $n$ qudit circuit. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n \log(n))$ gates are also sufficient, and we precisely compute the optimal constant prefactor for the $n \log(n)$. The technique we employ relies upon a mapping from the expected collision probability to the partition function of an Ising-like classical statistical mechanical model, which we manage to bound using stochastic and combinatorial techniques., Comment: 46 pages, 7 figures. v2: Reformatted, fixed typos, added figure 3

We study whether one can write a Matrix Product Density Operator (MPDO) as the Gibbs state of a quasi-local parent Hamiltonian. We conjecture this is the case for generic MPDO and give supporting evidences. To investigate the locality of the parent Hamiltonian, we take the approach of checking whether the quantum conditional mutual information decays exponentially. The MPDO we consider are constructed from a chain of 1-input/2-output (`Y-shaped') completely-positive maps, i.e., the MPDO have a local purification. We derive an upper bound on the conditional mutual information for bistochastic channels and strictly positive channels and show that it decays exponentially if the correctable algebra of the channel is trivial. We also introduce a conjecture on a quantum data processing inequality that implies the exponential decay of the conditional mutual information for every Y-shaped channel with trivial correctable algebra. We additionally investigate a close but nonequivalent cousin: MPDO measured in a local basis. We provide sufficient conditions for the exponential decay of the conditional mutual information of the measured states and numerically confirm they are generically true for certain random MPDO., Comment: added Github code for Propostion III.6 in v2; improved presentation in v3

Quantum state tomography is a powerful, but resource-intensive, general solution for numerous quantum information processing tasks. This motivates the design of robust tomography procedures that use relevant resources as sparingly as possible. Important cost factors include the number of state copies and measurement settings, as well as classical postprocessing time and memory. In this work, we present and analyze an online tomography algorithm designed to optimize all the aforementioned resources at the cost of a worse dependence on accuracy. The protocol is the first to give provably optimal performance in terms of rank and dimension for state copies, measurement settings and memory. Classical runtime is also reduced substantially and numerical experiments demonstrate a favorable comparison with other state-of-the-art techniques. Further improvements are possible by executing the algorithm on a quantum computer, giving a quantum speedup for quantum state tomography., Comment: Corrected typos and added numerical examples

Random quantum circuits are commonly viewed as hard to simulate classically. In some regimes this has been formally conjectured, and there had been no evidence against the more general possibility that for circuits with uniformly random gates, approximate simulation of typical instances is almost as hard as exact simulation. We prove that this is not the case by exhibiting a shallow circuit family with uniformly random gates that cannot be efficiently classically simulated near-exactly under standard hardness assumptions, but can be simulated approximately for all but a superpolynomially small fraction of circuit instances in time linear in the number of qubits and gates. We furthermore conjecture that sufficiently shallow random circuits are efficiently simulable more generally. To this end, we propose and analyze two simulation algorithms. Implementing one of our algorithms numerically, we give strong evidence that it is efficient both asymptotically and, in some cases, in practice. To argue analytically for efficiency, we reduce the simulation of 2D shallow random circuits to the simulation of a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements -- a type of process that has generally been observed to undergo a phase transition from an efficient-to-simulate regime to an inefficient-to-simulate regime as measurement strength is varied. Using a mapping from quantum circuits to statistical mechanical models, we give evidence that a similar computational phase transition occurs for our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied., Comment: 83 pages, 17 figures. v2: minor fixes and clarifications, added a reference

The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high energy physics. The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state. It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a short-cut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions. To go further, one may study more generic models of complexity growth. We provide a rigorous connection between complexity growth and unitary $k$-designs, ensembles which capture the randomness of the unitary group. This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity. We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind. Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements., Comment: 64 pages, 4 figures, many diagrams

Topological entanglement entropy has been extensively used as an indicator of topologically ordered phases. We study the conditions needed for two-dimensional topologically trivial states to exhibit spurious contributions that contaminates topological entanglement entropy. We show that if the state at the boundary of a subregion is a stabilizer state, then it has a non-zero spurious contribution to the region if and only if, the state is in a non-trivial one-dimensional $G_1\times G_2$ symmetry-protected-topological (SPT) phase. However, we provide a candidate of a boundary state that has a non-zero spurious contribution but does not belong to any such SPT phase., Comment: 5+7 pages, 4 figures v2:published in PRResearch: Rapid Communication. Title is modified. Minor errors are fixed

Recent understanding of the thermodynamics of small-scale systems have enabled the characterization of the thermodynamic requirements of implementing quantum processes for fixed input states. Here, we extend these results to construct optimal universal implementations of a given process, that is, implementations that are accurate for any possible input state even after many independent and identically distributed (i.i.d.) repetitions of the process. We find that the optimal work cost rate of such an implementation is given by the thermodynamic capacity of the process, which is a single-letter and additive quantity defined as the maximal difference in relative entropy to the thermal state between the input and the output of the channel. As related results we find a new single-shot implementation of time-covariant processes and conditional erasure with nontrivial Hamiltonians, a new proof of the asymptotic equipartition property of the coherent relative entropy, and an optimal implementation of any i.i.d. process with thermal operations for a fixed i.i.d. input state. Beyond being a thermodynamic analogue of the reverse Shannon theorem for quantum channels, our results introduce a new notion of quantum typicality and present a thermodynamic application of convex-split methods., Comment: 46+15 pages, 2 figures. The appendix of arXiv:1807.05610 was split off and reworked into this technical companion paper. Version v2 reflects the journal accepted version but is extended with some additional related results (Section 8) that are not included in the published work

This is an updated version of supplementary information to accompany "Quantum supremacy using a programmable superconducting processor", an article published in the October 24, 2019 issue of Nature. The main article is freely available at https://www.nature.com/articles/s41586-019-1666-5. Summary of changes since arXiv:1910.11333v1 (submitted 23 Oct 2019): added URL for qFlex source code; added Erratum section; added Figure S41 comparing statistical and total uncertainty for log and linear XEB; new References [1,65]; miscellaneous updates for clarity and style consistency; miscellaneous typographical and formatting corrections., Comment: 67 pages, 51 figures

We prove that the quantum Gibbs states of spin systems above a certain threshold temperature are approximate quantum Markov networks, meaning that the conditional mutual information decays rapidly with distance. We demonstrate the exponential decay for short-ranged interacting systems and power-law decay for long-ranged interacting systems. Consequently, we establish the efficiency of quantum Gibbs sampling algorithms, a strong version of the area law, the quasi-locality of effective Hamiltonians on subsystems, a clustering theorem for mutual information, and a polynomial-time algorithm for classical Gibbs state simulations., Comment: 7 pages + 17 pages, 10 figures

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erd\"{o}s-R\'enyi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem., Comment: 42 pages, one figure. Corrected several typos and added a more thorough discussion on speedups for random instances. Accepted for publication in Quantum

For quantum spin systems in any spatial dimension with a local, translation-invariant Hamiltonian, we prove that asymptotic state convertibility from a quantum state to another one by a thermodynamically feasible class of quantum dynamics, called thermal operations, is completely characterized by the Kullback-Leibler (KL) divergence rate, if the state is translation-invariant and spatially ergodic. Our proof consists of two parts and is phrased in terms of a branch of the quantum information theory called the resource theory. First, we prove that any states, for which the min and max R\'enyi divergences collapse approximately to a single value, can be approximately reversibly converted into one another by thermal operations with the aid of a small source of quantum coherence. Second, we prove that these divergences collapse asymptotically to the KL divergence rate for any translation-invariant ergodic state. We show this via a generalization of the quantum Stein's lemma for quantum hypothesis testing beyond independent and identically distributed (i.i.d.) situations. Our result implies that the KL divergence rate serves as a thermodynamic potential that provides a complete characterization of thermodynamic convertibility of ergodic states of quantum many-body systems in the thermodynamic limit, including out-of-equilibrium and fully quantum situations., Comment: 59 pages. See short companion paper Phys. Rev. Lett. 123, 250601

The resource theory of thermal operations, an established model for small-scale thermodynamics, provides an extension of equilibrium thermodynamics to nonequilibrium situations. On a lattice of any dimension with any translation-invariant local Hamiltonian, we identify a large set of translation-invariant states that can be reversibly converted to and from the thermal state with thermal operations and a small amount of coherence. These are the spatially ergodic states, i.e., states that have sharp statistics for any translation-invariant observable, and mixtures of such states with the same thermodynamic potential. As an intermediate result, we show for a general state that if the min- and the max-relative entropy to the thermal state coincide approximately, this implies the approximately reversible interconvertibility to and from the thermal state with thermal operations and a small source of coherence. Our results provide a strong link between the abstract resource theory of thermodynamics and more realistic physical systems, as we achieve a robust and operational characterization of the emergence of a thermodynamic potential in translation-invariant lattice systems., Comment: 5 pages + references, 2 figures. Short companion paper to our technical paper published today on the arXiv

We consider the scaling of entanglement entropy in random Projected Entangled Pairs States (PEPS) with an internal symmetry given by a finite group G. We systematically demonstrate a correspondence between this entanglement entropy and the difference of free energies of a classical Ising model with an addition non-local term. This non-local term counts the number of domain walls in a particular configuration of the classical spin model. We argue that for that overwhelming majority of such states, this gives rise to an area law scaling with well-defined topological entanglement entropy. The topological entanglement entropy is shown to be log|G| for a simply connected region A and which manifests as a difference in the number of domain walls of ground state energies for the two spin models.

A key feature of ground states of gapped local 1D Hamiltonians is their relatively low entanglement --- they are well approximated by matrix product states (MPS) with bond dimension scaling polynomially in the length $N$ of the chain, while general states require a bond dimension scaling exponentially. We show that the bond dimension of these MPS approximations can be improved to a constant, independent of the chain length, if we relax our notion of approximation to be more local: for all length-$k$ segments of the chain, the reduced density matrices of our approximations are $\epsilon$-close to those of the exact state. If the state is a ground state of a gapped local Hamiltonian, the bond dimension of the approximation scales like $(k/\epsilon)^{1+o(1)}$, and at the expense of worse but still $\text{poly}(k,1/\epsilon)$ scaling of the bond dimension, we give an alternate construction with the additional features that it can be generated by a constant-depth quantum circuit with nearest-neighbor gates, and that it applies generally for any state with exponentially decaying correlations. For a completely general state, we give an approximation with bond dimension $\exp(O(k/\epsilon))$, which is exponentially worse, but still independent of $N$. Then, we consider the prospect of designing an algorithm to find a local approximation for ground states of gapped local 1D Hamiltonians. When the Hamiltonian is translationally invariant, we show that the ability to find $O(1)$-accurate local approximations to the ground state in $T(N)$ time implies the ability to estimate the ground state energy to $O(1)$ precision in $O(T(N)\log(N))$ time., Comment: 24 pages, 3 figures. v2: Theorem 1 extended to include construction for general states; Lemma 7 & Theorem 2 slightly improved; figures added; lemmas rearranged for clarity; typos fixed. v3: Reformatted & additional references inserted

The accurate computation of Hamiltonian ground, excited, and thermal states on quantum computers stands to impact many problems in the physical and computer sciences, from quantum simulation to machine learning. Given the challenges posed in constructing large-scale quantum computers, these tasks should be carried out in a resource-efficient way. In this regard, existing techniques based on phase estimation or variational algorithms display potential disadvantages; phase estimation requires deep circuits with ancillae, that are hard to execute reliably without error correction, while variational algorithms, while flexible with respect to circuit depth, entail additional high-dimensional classical optimization. Here, we introduce the quantum imaginary time evolution and quantum Lanczos algorithms, which are analogues of classical algorithms for finding ground and excited states. Compared to their classical counterparts, they require exponentially less space and time per iteration, and can be implemented without deep circuits and ancillae, or high-dimensional optimization. We furthermore discuss quantum imaginary time evolution as a subroutine to generate Gibbs averages through an analog of minimally entangled typical thermal states. Finally, we demonstrate the potential of these algorithms via an implementation using exact classical emulation as well as through prototype circuits on the Rigetti quantum virtual machine and Aspen-1 quantum processing unit., Comment: 18 pages, 7 figures; improved figures and text

The Quantum Approximate Optimization Algorithm, QAOA, uses a shallow depth quantum circuit to produce a parameter dependent state. For a given combinatorial optimization problem instance, the quantum expectation of the associated cost function is the parameter dependent objective function of the QAOA. We demonstrate that if the parameters are fixed and the instance comes from a reasonable distribution then the objective function value is concentrated in the sense that typical instances have (nearly) the same value of the objective function. This applies not just for optimal parameters as the whole landscape is instance independent. We can prove this is true for low depth quantum circuits for instances of MaxCut on large 3-regular graphs. Our results generalize beyond this example. We support the arguments with numerical examples that show remarkable concentration. For higher depth circuits the numerics also show concentration and we argue for this using the Law of Large Numbers. We also observe by simulation that if we find parameters which result in good performance at say 10 bits these same parameters result in good performance at say 24 bits. These findings suggest ways to run the QAOA that reduce or eliminate the use of the outer loop optimization and may allow us to find good solutions with fewer calls to the quantum computer., Comment: 16 pages, 1 figure

Insights from quantum information theory show that correlation measures based on quantum entropy are fundamental tools that reveal the entanglement structure of multipartite states. In that spirit, Groisman, Popescu, and Winter [Physical Review A 72, 032317 (2005)] showed that the quantum mutual information $I(A;B)$ quantifies the minimal rate of noise needed to erase the correlations in a bipartite state of quantum systems $AB$. Here, we investigate correlations in tripartite systems $ABE$. In particular, we are interested in the minimal rate of noise needed to apply to the systems $AE$ in order to erase the correlations between $A$ and $B$ given the information in system $E$, in such a way that there is only negligible disturbance on the marginal $BE$. We present two such models of conditional decoupling, called deconstruction and conditional erasure cost of tripartite states $ABE$. Our main result is that both are equal to the conditional quantum mutual information $I(A;B|E)$ -- establishing it as an operational measure for tripartite quantum correlations., Comment: 6 pages, 1 figure, see companion paper at arXiv:1609.06994

We consider two-dimensional states of matter satisfying an uniform area law for entanglement. We show that the topological entanglement entropy is equal to the minimum relative entropy distance from the reduced state to the set of thermal states of local models. The argument is based on strong subadditivity of quantum entropy. For states with zero topological entanglement entropy, in particular, the formula gives locality of the states at the boundary of a region as thermal states of local Hamiltonians. It also implies that the entanglement spectrum of a two-dimensional region is equal to the spectrum of a one-dimensional local thermal state on the boundary of the region., Comment: v1; 5+4 pages, 5 figures. v2; 5+5 pages, 5 figures. Presentation has been improved. Accepted for publication in Physical Review B

Quantum error correction was invented to allow for fault-tolerant quantum computation. Systems with topological order turned out to give a natural physical realization of quantum error correcting codes (QECC) in their groundspaces. More recently, in the context of the AdS/CFT correspondence, it has been argued that eigenstates of CFTs with a holographic dual should also form QECCs. These two examples raise the question of how generally eigenstates of many-body models form quantum codes. In this work we establish new connections between quantum chaos and translation-invariance in many-body spin systems, on one hand, and approximate quantum error correcting codes (AQECC), on the other hand. We first observe that quantum chaotic systems exhibiting the Eigenstate Thermalization Hypothesis (ETH) have eigenstates forming approximate quantum error-correcting codes. Then we show that AQECC can be obtained probabilistically from translation-invariant energy eigenstates of every translation-invariant spin chain, including integrable models. Applying this result to 1D classical systems, we describe a method for using local symmetries to construct parent Hamiltonians that embed these codes into the low-energy subspace of gapless 1D quantum spin chains. As explicit examples we obtain local AQECC in the ground space of the 1D ferromagnetic Heisenberg model and the Motzkin spin chain model with periodic boundary conditions, thereby yielding non-stabilizer codes in the ground space and low energy subspace of physically plausible 1D gapless models., Comment: 13 pages, no figures. v2: added references, corrected typos

We construct a Hamiltonian whose dynamics simulate the dynamics of every other Hamiltonian up to exponentially long times in the system size. The Hamiltonian is time-independent, local, one-dimensional, and translation invariant. As a consequence, we show (under plausible computational complexity assumptions) that the circuit complexity of the unitary dynamics under this Hamiltonian grows steadily with time up to an exponential value in system size. This result makes progress on a recent conjecture by Susskind, in the context of the AdS/CFT correspondence, that the time evolution of the thermofield double state of two conformal fields theories with a holographic dual has a circuit complexity increasing linearly in time, up to exponential time., Comment: 33 pages, typos and errors in transition rules corrected from v1, more references and acknowledgements added, more comments are welcome!

We give two quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with $m$ constraint matrices, each of dimension $n$, rank at most $r$, and sparsity $s$. The first algorithm assumes access to an oracle to the matrices at unit cost. We show that it has run time $\tilde{O}(s^2(\sqrt{m}\epsilon^{-10}+\sqrt{n}\epsilon^{-12}))$, with $\epsilon$ the error of the solution. This gives an optimal dependence in terms of $m, n$ and quadratic improvement over previous quantum algorithms when $m\approx n$. The second algorithm assumes a fully quantum input model in which the matrices are given as quantum states. We show that its run time is $\tilde{O}(\sqrt{m}+\text{poly}(r))\cdot\text{poly}(\log m,\log n,B,\epsilon^{-1})$, with $B$ an upper bound on the trace-norm of all input matrices. In particular the complexity depends only poly-logarithmically in $n$ and polynomially in $r$. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given $m$ measurements and a supply of copies of an unknown state $\rho$ with rank at most $r$, we show we can find in time $\sqrt{m}\cdot\text{poly}(\log m,\log n,r,\epsilon^{-1})$ a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as $\rho$ on the $m$ measurements, up to error $\epsilon$. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians with a poly-logarithmic dependence on its dimension, which could be of independent interest., Comment: 40 pages. To appear at the 46th International Colloquium on Automata, Languages and Programming (ICALP 2019)

We study thermal states of strongly interacting quantum spin chains and prove that those can be represented in terms of convex combinations of matrix product states. Apart from revealing new features of the entanglement structure of Gibbs states our results provide a theoretical justification for the use of White's algorithm of minimally entangled typical thermal states. Furthermore, we shed new light on time dependent matrix product state algorithms which yield hydrodynamical descriptions of the underlying dynamics., Comment: v3: 10 pages, 2 figures, final published version

We extend quantum Stein's lemma in asymmetric quantum hypothesis testing to composite null and alternative hypotheses. As our main result, we show that the asymptotic error exponent for testing convex combinations of quantum states $\rho^{\otimes n}$ against convex combinations of quantum states $\sigma^{\otimes n}$ can be written as a regularized quantum relative entropy formula. We prove that in general such a regularization is needed but also discuss various settings where our formula as well as extensions thereof become single-letter. This includes an operational interpretation of the relative entropy of coherence in terms of hypothesis testing. For our proof, we start from the composite Stein's lemma for classical probability distributions and lift the result to the non-commutative setting by using elementary properties of quantum entropy. Finally, our findings also imply an improved recoverability lower bound on the conditional quantum mutual information in terms of the regularized quantum relative entropy -- featuring an explicit and universal recovery map., Comment: 14 pages, v2: matches published version, includes several corrections

Chaotic dynamics in quantum many-body systems scrambles local information so that at late times it can no longer be accessed locally. This is reflected quantitatively in the out-of-time-ordered correlator of local operators, which is expected to decay to zero with time. However, for systems of finite size, out-of-time-ordered correlators do not decay exactly to zero and in this paper we show that the residual value can provide useful insights into the chaotic dynamics. When energy is conserved, the late-time saturation value of the out-of-time-ordered correlator of generic traceless local operators scales as an inverse polynomial in the system size. This is in contrast to the inverse exponential scaling expected for chaotic dynamics without energy conservation. We provide both analytical arguments and numerical simulations to support this conclusion., Comment: improved presentation

We prove that the entanglement entropy of any state evolved under an arbitrary $1/r^{\alpha}$ long-range-interacting D-dimensional lattice spin Hamiltonian cannot change faster than a rate proportional to the boundary area for any $\alpha>D+1$. We also prove that for any $\alpha>2D+2$, the ground state of such a Hamiltonian satisfies the entanglement area law if it can be transformed along a gapped adiabatic path into a ground state known to satisfy the area law. These results significantly generalize their existing counterparts for short-range interacting systems, and are useful for identifying dynamical phase transitions and quantum phase transitions in the presence of long-range interactions., Comment: 7 pages, 1 figure

Thermal states are the bedrock of statistical physics. Nevertheless, when and how they actually arise in closed quantum systems is not fully understood. We consider this question for systems with local Hamiltonians on finite quantum lattices. In a first step, we show that states with exponentially decaying correlations equilibrate after a quantum quench. Then we show that the equilibrium state is locally equivalent to a thermal state, provided that the free energy of the equilibrium state is sufficiently small and the thermal state has exponentially decaying correlations. As an application, we look at a related important question: When are thermal states stable against noise? In other words, if we locally disturb a closed quantum system in a thermal state, will it return to thermal equilibrium? We rigorously show that this occurs when the correlations in the thermal state are exponentially decaying. All our results come with finite-size bounds, which are crucial for the growing field of quantum thermodynamics and other physical applications., Comment: 8 pages (5 for main text and 3 for appendices); v2 is essentially the published version

Preparing quantum thermal states on a quantum computer is in general a difficult task. We provide a procedure to prepare a thermal state on a quantum computer with a logarithmic depth circuit of local quantum channels assuming that the thermal state correlations satisfy the following two properties: (i) the correlations between two regions are exponentially decaying in the distance between the regions, and (ii) the thermal state is an approximate Markov state for shielded regions. We require both properties to hold for the thermal state of the Hamiltonian on any induced subgraph of the original lattice. Assumption (ii) is satisfied for all commuting Gibbs states, while assumption (i) is satisfied for every model above a critical temperature. Both assumptions are satisfied in one spatial dimension. Moreover, both assumptions are expected to hold above the thermal phase transition for models without any topological order at finite temperature. As a building block, we show that exponential decay of correlation (for thermal states of Hamiltonians on all induced subgraph) is sufficient to efficiently estimate the expectation value of a local observable. Our proof uses quantum belief propagation, a recent strengthening of strong sub-additivity, and naturally breaks down for states with topological order., Comment: 16 pages, 4 figures

We define the deconstruction cost of a tripartite quantum state on systems $ABE$ as the minimum rate of noise needed to apply to the $AE$ systems, such that there is negligible disturbance to the marginal state on the $BE$ systems, while the system $A$ of the resulting state is locally recoverable from the $E$ system alone. We refer to such actions as deconstruction operations and protocols implementing them as state deconstruction protocols. State deconstruction generalizes Landauer erasure of a single-party quantum state as well the erasure of correlations of a two-party quantum state. We find that the deconstruction cost of a tripartite quantum state on systems $ABE$ is equal to its conditional quantum mutual information (CQMI) $I(A;B|E)$, thus giving the CQMI an operational interpretation in terms of a state deconstruction protocol. We also define a related task called conditional erasure, in which the goal is to apply noise to systems $AE$ in order to decouple system $A$ from systems $BE$, while causing negligible disturbance to the marginal state of systems $BE$. We find that the optimal rate of noise for conditional erasure is also equal to the CQMI $I(A;B|E)$. State deconstruction and conditional erasure lead to operational interpretations of the quantum discord and squashed entanglement, which are quantum correlation measures based on the CQMI. We find that the quantum discord is equal to the cost of simulating einselection, the process by which a quantum system interacts with an environment, resulting in selective loss of information in the system. The squashed entanglement is equal to half the minimum rate of noise needed for deconstruction/conditional erasure if Alice has available the best possible system $E$ to help in the deconstruction/conditional erasure task., Comment: 21 pages, 3 figures, accepted for publication in Physical Review A

We prove that any one-dimensional (1D) quantum state with small quantum conditional mutual information in all certain tripartite splits of the system, which we call a quantum approximate Markov chain, can be well-approximated by a Gibbs state of a short-range quantum Hamiltonian. Conversely, we also derive an upper bound on the (quantum) conditional mutual information of Gibbs states of 1D short-range quantum Hamiltonians. We show that the conditional mutual information between two regions A and C conditioned on the middle region B decays exponentially with the square root of the length of B. These two results constitute a variant of the Hammersley-Clifford theorem (which characterizes Markov networks, i.e. probability distributions which have vanishing conditional mutual information, as Gibbs states of classical short-range Hamiltonians) for 1D quantum systems. The result can be seen as a strengthening - for 1D systems - of the mutual information area law for thermal states. It directly implies an efficient preparation of any 1D Gibbs state at finite temperature by a constant-depth quantum circuit., Comment: v1 22 pages, 3 figures; v2 31 pages, 5 figures. Presentations improved and new result (Theorem 3) is added v3; 32 pages, 5 figures. Accepted for publication in Communications in Mathematical Physics