Quantum Information

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.

Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs (where graph symmetry is manifested differently), we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013). Based on: arxiv:2006.12760

In this talk, I will discuss two problems: quantum data compression
and quantum causal order discovery, both for multipartite quantum
systems. For data compression, we model finitely correlated states as
tensor networks, and design quantum compression algorithms. We first
establish an upper bound on the amount of memory needed to store an
arbitrary state from a given state family. The bound is determined by
the minimum cut of a suitable flow network, and is related to the flow
of information from the manifold of parameters that specify the states
to the physical systems in which the states are embodied. We then
provide a compression algorithm for general state families, and show
that the algorithm runs in polynomial time for matrix product states.

For quantum causal order discovery, we develop the first efficient
quantum causal order discovery algorithm with polynomial black-box
queries with respect to the number of systems. We model the causal
order with quantum combs, and our algorithm outputs the order of
inputs and outputs that the given process is compatible with. Our
method guarantees a polynomial running time for quantum combs with a
low Kraus rank, namely processes with low noise and little information
loss. For special cases where the causal order can be inferred from
local observations, we also propose algorithms that have lower query
complexity and only require local state preparation and local
measurements. Our results will provide efficient ways to detect and
optimize available transmission paths in quantum communication
networks, as well as methods to verify quantum circuits and to
discover the latent structure of multipartite quantum systems.

There is a deep relation between classical error-correcting codes, Euclidean lattices, and chiral 2d CFTs. We show this relation
extends to include quantum codes, Lorentzian lattices, and non-chiral CFTs. The relation to quantum codes provides a simple way to solve
modular bootstrap constraints and identify interesting examples of conformal theories. In particular we construct many examples of physically distinct isospectral theories, examples of "would-be" CFT partition function -- non-holomorphic functions satisfying all constraints of the modular bootstrap, yet not associated with any

known CFT, and find theory with the maximal spectral gap among all Narain CFTs with the central charge c=4. At the level of code theories the problem of finding maximal spectral gap reduces to the problem of finding optimal code, leading to "baby bootstrap" program. We also discuss averaging over the ensemble of all CFTs associated with quantum codes, and its possible holographic interpretation. The talk is based on arXiv:2009.01236 and arXiv:2009.01244.

In a quantum measurement process, classical information about the measured system spreads through the environment. In contrast, quantum information about the system becomes inaccessible to local observers. In this talk, I will present a result about quantum channels indicating that an aspect of this phenomenon is completely general. We show that for any evolution of the system and environment, for everywhere in the environment excluding an O(1)-sized region we call the "quantum Markov blanket," any locally accessible information about the system must be approximately classical, i.e. obtainable from some fixed measurement. The result strengthens the earlier result of arXiv:1310.8640 in which the excluded region was allowed to grow with total environment size.  I will also discuss applications to many-body physics.

"Analogue" Hamiltonian simulation involves engineering a Hamiltonian of
interest in the laboratory and studying its properties experimentally.
Large-scale Hamiltonian simulation experiments have been carried out in
optical lattices, ion traps and other systems for two decades. Despite
this, the theoretical basis for Hamiltonian simulation is surprisingly
sparse. Even a precise definition of what it means to simulate a
Hamiltonian was lacking.

AdS/CFT duality postulates that quantum gravity in a d-dimensional
anti-de-Sitter bulk space is equivalent to a strongly interacting field
theory on its d-1 dimensional boundary. Recently, connections between
AdS/CFT duality and quantum error-correcting codes have led (amongst
other things) to tensor network toy models that capture important aspects
of this holographic duality. However, these toy models struggle to
encompass dualities between bulk and boundary energy scales and dynamics.

On the face of it, these two topics seem to have nothing whatsoever to do
with one another.

In my talk, I will explain how we put analogue Hamiltonian simulation on
a rigorous theoretical footing, by drawing on techniques from Hamiltonian
complexity theory and Jordan algebras. I will show how this proved far
more fruitful than a mere mathematical tidying-up exercise, leading to
the discovery of universal quantum Hamiltonians [Science, 351:6 278,
p.1180, 2016], [Proc. Natl. Acad. Sci. 115:38 p.9497, 2018]. And I will
explain how this new Hamiltonian simulation formalism, together with
hyperbolic Coxeter groups, allowed us to extend the toy models of AdS/CFT
to encompass energy scales, dynamics, and even (toy models of) black hole
formation [arXiv:1810.08992].

The Fermi-Hubbard model is of fundamental importance in condensed-matter physics, yet is extremely challenging to solve numerically. Finding the ground state of the Hubbard model using variational methods has been predicted to be one of the first applications of near-term quantum computers. In this talk, I will discuss recent work which carried out a detailed analysis and optimisation of the complexity of variational quantum algorithms for finding the ground state of the Hubbard model, including extensive numerical experiments for systems with up to 12 sites. The depth complexities we find are substantially lower than previous work. If our numerical results on small lattice sizes are representative of the somewhat larger lattices accessible to near-term quantum hardware, they suggest that optimising over quantum circuits with a gate depth less than a thousand could be sufficient to solve instances of the Hubbard model beyond the capacity of classical exact diagonalisation. I will also discuss a proof-of-principle implementation on Rigetti quantum computing hardware.

The talk is based on joint work with Chris Cade, Lana Mineh and Stasja Stanisic ( arXiv:1912.06007 , arXiv:2006.01179 ).

I will review work by myself and others in recent years on the use of randomization in quantum circuit optimization.  I will present general results showing that any deterministic compiler for an approximate synthesis problem can be lifted to a better random compiler.  I will discuss the subtle issue of what "better" means and how it is sensitive to the metric and computation task at hand.  I will then review specific randomized algorithms for quantum simulations, including randomized Trotter (Su & Childs) and my group's work on the qDRIFT and SPARSTO algorithms.  The qDRIFT algorithm is of particular interest as it gave the first proof that Hamiltonian simulation is possible with a gate complexity that is independent of the number of terms in the Hamiltonian.  Since quantum chemistry Hamiltonians have a very large ( ~N^4) number of terms, randomization is especially useful in that setting. I will conclude by commenting on a recent Caltech paper with interesting results on the derandomization of random algorithms!  Some of the relevant preprints include:

https://arxiv.org/abs/1910.06255

https://arxiv.org/abs/1811.08017

https://arxiv.org/abs/1612.02689

Discriminating between unknown objects in a given set is a fundamental task in experimental science. Suppose you are given a quantum system which is in one of two given states with equal probability. Determining the actual state of the system amounts to doing a measurement on it which would allow you to discriminate between the two possible states. It is known that unless the two states are mutually orthogonal, perfect discrimination is possible only if you are given arbitrarily many identical copies of the state.

In this talk we consider the task of discriminating between quantum channels, instead of quantum states. In particular, we discriminate between a pair of unitary channels acting on a quantum system whose underlying Hilbert space is infinite-dimensional. We prove that in contrast to state discrimination, one only needs a finite number of uses of these channels in order to discriminate perfectly between them. Furthermore, no entanglement is needed in the discrimination task. The measure of discrimination is given in terms of the energy-constrained diamond norm, and a key ingredient of the proofs of these results is a generalization of the Toeplitz-Hausdorff Theorem of convex analysis . Moreover, we employ our results to study a novel type of quantum speed limits which apply to pairs of quantum evolutions. This work was done jointly with Simon Becker (Cambridge), Ludovico Lami (Ulm) and Cambyse Rouze (Munich).