Quantum Information

We present two classical algorithms for the simulation of universal quantum circuits on n qubits constructed from c instances of Clifford gates and t arbitrary-angle Z-rotation gates such as T gates. Our algorithms complement each other by performing best in different parameter regimes. The Estimate algorithm produces an additive precision estimate of the Born rule probability of a chosen measurement outcome with the only source of run-time inefficiency being a linear dependence on the stabilizer extent (which scales like ≈1.17^t for T gates). Our algorithm is state-of-the-art for this task:

as an example, in approximately 25 hours (on a standard desktop computer), we estimated the Born rule probability to within an additive error of 0.03, for a 50 qubit, 60 non-Clifford gate quantum circuit with more than 2000 Clifford gates. The Compute algorithm calculates the probability of a chosen measurement outcome to machine precision with run-time O(2^t−r(t−r)t) where r is an efficiently computable, circuit-specific quantity. With high probability, r is very close to min{t,n−w} for random circuits with many Clifford gates, where w is the number of measured qubits. Compute can be effective in surprisingly challenging parameter regimes, e.g., we can randomly sample Clifford+T circuits with n=55, w=5, c=105 and t=80 T-gates, and then compute the Born rule probability with a run-time consistently less than 104 seconds using a single core of a standard desktop computer. We provide a C+Python implementation of our algorithms.

It has been shown that, despite being local, a perturbation applied to a single site of the one-dimensional XXZ model is enough to bring this interacting integrable spin-1/2 system to the chaotic regime. In this talk, we show that this is not unique to the XXZ model, but happens also to the spin-1/2 Ising model in a transverse field and to the spin-1 Lai-Sutherland chain. The larger the system is, the smaller the amplitude of the local perturbation for the onset of chaos. We focus on two indicators of chaos, the correlation hole, which is a dynamical tool, and the distribution of off-diagonal elements of local observables, which is used in the eigenstate thermalization hypothesis. Both methods avoid spectrum unfolding and can detect chaos even when the eigenvalues are not separated by symmetry sectors.

Discriminating between quantum computing architectures that can provide quantum advantage from those that cannot is of crucial importance. From the fundamental point of view, establishing such a boundary is akin to pinpointing the resources for quantum advantage; from the technological point of view, it is essential for the design of non-trivial quantum computing architectures. Wigner negativity is known to be a necessary resource for computational advantage in several quantum-computing architectures, including those based on continuous variables (CVs). However, it is not a sufficient resource, and it is an open question under which conditions CV circuits displaying Wigner negativity offer the potential for quantum advantage. In this work, we identify vast families of circuits that display large Wigner negativity, and yet are classically efficiently simulatable, although they are not recognized as such by previously available theorems. These families of circuits employ bosonic codes based on either translational or rotational symmetries (e.g., Gottesman-Kitaev-Preskill or cat codes), and can include both Gaussian and non-Gaussian gates and measurements. Crucially, within these encodings, the computational basis states are described by intrinsically negative Wigner functions, even though they are stabilizer states if considered as codewords belonging to a finite-dimensional Hilbert space. We derive our results by establishing a link between the simulatability of high-dimensional discrete-variable quantum circuits and bosonic codes.

To analyze the performance of adaptive measurement protocols for the detection and quantification of state resources, we introduce the framework of quantum preparation games. A preparation game is a task whereby a player sequentially sends a number of quantum states to a referee, who probes each of them and announces the measurement result. The measurement setting at each round, as well as the final score of the game, are decided by the referee based on the past history of settings and measurement outcomes. We show how to compute the maximum average score that a player can achieve under very general constraints on their preparation devices and provide practical methods to carry out optimizations over n-round preparation games. We apply our general results to devise new adaptive protocols for entanglement detection and quantification. Given a set of experimentally available local measurement settings, we provide an algorithm to derive, via convex optimization, optimal n-shot protocols for entanglement detection using these settings. We also present families of adaptive protocols for multiple-target entanglement detection with arbitrarily many rounds. Surprisingly, we find that there exist instances of entanglement detection problems with just one target entangled state where the optimal adaptive protocol supersedes all non-adaptive alternatives.

In the last two decades the field of nonequilibrium quantum many-body physics
has seen a rapid development driven, in particular, by the remarkable progress
in quantum simulators, which today provide access to dynamics in quantum
matter with an unprecedented control. However, the efficient numerical
simulation of nonequilibrium real-time evolution in isolated quantum matter
still remains a key challenge for current computational methods especially
beyond one spatial dimension. In this talk I will present a versatile and
efficient machine learning inspired approach. I will first introduce the
general idea of encoding quantum many-body wave functions into artificial
neural networks. I will then identify and resolve key challenges for the
simulation of real-time evolution, which previously imposed significant
limitations on the accurate description of large systems and long-time
dynamics. As a concrete example, I will consider the dynamics of the
paradigmatic two-dimensional transverse field Ising model, where we observe
collapse and revival oscillations of ferromagnetic order and demonstrate that
the reached time scales are comparable to or exceed the capabilities of state-
of-the-art tensor network methods.

Many physical states of interest, such as ground states of gapped quantum many-body systems, are expected to obey an area law of entanglement entropy. I will report on a series of recent results that suggest a deep connection between area law and two seemingly unrelated subjects: topological quantum field theory and quantum marginal problem. Recently, we deduced --- only using area law and quantum information-theoretic tools --- the existence of new topological charges and invariants associated with the domain walls between topologically ordered systems in two spatial dimensions. Moreover, the same set of tools were also used in finding a solution to the quantum marginal problem. This is the problem in which one asks whether a set of reduced density matrices on bounded subsystems are compatible with some globally well-defined many-body quantum state. Since this problem was first posed in 1959, a solution that goes beyond the mean-field ansatz has remained elusive until now. These results suggest that area law is not just a qualitative statement about entanglement; it is an important equation that lets us "solve" quantum many-body systems that appear in nature.

Based on arXiv:2008.11793 and arXiv:2010.07424

Information theory offers mathematically precise theory of communication and data storage that guided and fueled the information age.  Initially, quantum effects were thought to be an annoying source of noise, but we have since learned that they offer new capabilities and vast opportunities. Quantum information theory seeks to identify, quantify, and ultimately harness these capabilities. A basic resource in this context is a noisy quantum communication channel, and a central goal is to figure out its capacities---what can you do with it?  I’ll highlight the new and fundamentally quantum aspects that arise here, such as the role of entanglement, ways to quantify it, and bizarre new kinds of synergies between resources.  These ideas elucidate the nature of communication in a quantum context, as well as revealing new facets of quantum theory itself.

A central challenge in quantum many-body physics is a characterization of properties of `natural' quantum states, such as the ground states and Gibbs states of a local hamiltonian. The area-law conjecture, which postulates a remarkably simple structure of entanglement in gapped ground states, has resisted a resolution based on information-theoretic methods. We discuss how the right set of insights may come, quite unexpectedly, from polynomial approximations to boolean functions. Towards this, we describe a 2D sub-volume law for frustration-free locally-gapped ground states and highlight a pathway that could lead to an area law. Similar polynomial approximations have consequences for entanglement in Gibbs states and lead to the first provably linear time algorithm to simulate Gibbs states in 1D. Next, we consider the task of learning a Hamiltonian from a Gibbs state, where many-body entanglement obstructs rigorous algorithms. Here, we find that the effects of entanglement can again be controlled using tools from computer science, namely, strong convexity and sufficient statistics. 

We study the real-time dynamics of a small bubble of "false vacuum'' in a quantum spin chain near criticality, where the low-energy physics is described by a relativistic (1+1)-dimensional quantum field theory. Such a bubble can be thought of as a confined kink-antikink pair (a meson). We carefully construct bubbles so that particle production does not occur until the walls collide. To achieve this in the presence of strong correlations, we extend a Matrix Product State (MPS) ansatz for quasiparticle wavepackets [Van Damme et al., arXiv:1907.02474 (2019)] to the case of confined, topological quasiparticles. By choosing the wavepacket width and the bubble size appropriately, we avoid strong lattice effects and observe relativistic kink-antikink collisions. We use the MPS quasiparticle ansatz to identify scattering outcomes: In the Ising model, with transverse and longitudinal fields, we do not observe particle production despite nonintegrability (supporting recent numerical observations of nonthermalizing mesonic states). With additional interactions, we see production of confined and unconfined particle pairs. Although we simulated these low-energy, few-particle events with moderate resources, we observe significant growth of entanglement with energy and with the number of collisions, suggesting that increasing either will ultimately exhaust our methods. Quantum devices, in contrast, are not limited by entanglement production, and promise to allow us to go far beyond classical methods. We anticipate that kink-antikink scattering in 1+1 dimensions will be an instructive benchmark problem for relatively near-term quantum devices.

Walgate and Scott have determined the maximum number of generic pure quantum states in multipartite space that can be unambiguously discriminated by an LOCC measurement [Journal of Physics A: Mathematical and Theoretical, 41:375305, 08 2008]. In this work, we determine this number in a more general setting in which the local parties have access to pre-shared entanglement in the form of a resource state. We find that, for an arbitrary pure resource state, this number is equal to the Krull dimension of (the closure of) the set of pure states obtainable from the resource state by SLOCC. This dimension is known for several resource states, for example the GHZ state.

Local state discrimination is closely related to the topic of entangled subspaces, which we study in its own right. We introduce r-entangled subspaces, which naturally generalize previously studied spaces to higher multipartite entanglement. We use algebraic geometric methods to determine the maximum dimension of an r-entangled subspace, and present novel explicit constructions of such spaces. We obtain similar results for symmetric and antisymmetric r-entangled subspaces, which correspond to entangled subspaces of bosonic and fermionic systems, respectively.

In this talk, I argue that the question of whether a physical system can be simulated on a computer is important not just from a practical perspective but also a fundamental one. We consider the complexity of simulating Hamiltonians with respect to both dynamics and equilibrium properties. This gives us a classification and a phase diagram of the complexity.  I will cover recent results in this topic, such as a dynamical complexity phase diagram for a long-range bosonic Hamiltonian and a complexity classification of the local Hamiltonian problem in the presence of a spectral gap. I will talk about the physical implications of these results and cover some of the basic proof ideas if time permits.

Relativistic quantum tasks are quantum computations which have inputs and outputs that occur at designated spacetime locations.

Understanding which tasks are possible to complete, and what resources are required to complete them, captures spacetime-specific aspects of quantum information. In this talk we explore the connections between such tasks and quantum gravity, specifically in the context of the AdS/CFT correspondence. We find that tasks reveal a novel connection between causal features of bulk geometry and boundary entanglement.

Further, we find that AdS/CFT suggests quantum non-local computations, a specific task with relevance to position-based cryptography, can be performed with linear entanglement. This would be an exponential improvement on existing protocols.