Quantum Information

Adiabatic quantum computation (AQC) is a method for performing quantum computation in the ground state of a slowly evolving local Hamiltonian, and in an ideal setting AQC is known to capture all of the computational power of the quantum circuit model. However, despite having an inherent robustness to noise as a result of the adiabatic theorem and the spectral gap of the Hamiltonian, it remains a longstanding theoretical challenge to show that fault-tolerant AQC can in principle be performed below some fixed noise threshold. There are many aspects to this challenge, including the difficulty of adapting known ideas from circuit model fault-tolerance as well as the need to develop an error model that is appropriately tailored for open system AQC. In this talk I will introduce a scheme for combining Feynman-Kitaev history state Hamiltonians with topological quantum error correction, in order to show that universal quantum computation can be encoded not only in the ground state but also in the finite temperature metastable Gibbs state of a local Hamiltonian. Using only local interactions with bounded strength and a polynomial overhead in the number of qubits, the scheme is designed to serve as a proof of principle that universal AQC can be performed at non-zero temperature, and also to further our understanding of the complexity of highly entangled quantum systems in thermal equilibrium.

Many quantum information measures can be written as an optimization of a quantum relative entropy between sets of states. Examples include the relative entropy of entanglement (an important entanglement measure) and the relative entropy of recovery (providing operational lower bounds on the conditional mutual information). In this talk, I will discuss applications of such measures, different techniques for expressing them, and algorithms to compute them efficiently. Based mainly on arXiv:1512.02615 and arXiv:1705.06671.

A quantum impurity model describes a bath of free fermions coupled to a small interacting subsystem called an impurity. Such models were famously studied in the 1960s and 1970s to investigate the physics of a magnetic impurity embedded in a metal. More recently, they have been used to study strongly correlated materials within an approximation known as dynamical mean field theory. In this work we establish a structure theorem for ground states of quantum impurity models. As a consequence we obtain a classical algorithm for approximating the ground energy and computing low energy states. The runtime of the algorithm is polynomial in the total number of fermi modes and quasipolynomial in the desired approximation error. Based on joint work with Sergey Bravyi.

Two observers performing binary outcome measurements on subsystems of a global system may obtain more strongly correlated results when they have a shared entangled quantum state than when they only have shared randomness. This well-known phenomenon of Bell inequality violation can be precisely characterized mathematically. Indeed, being a classical or a quantum correlation matrix exactly corresponds to being in the unit ball of some tensor norms. In the talk, I will start with explaining all this in details. I will then look at the following problem: given a random matrix of size n, can one estimate the typical value of its "classical" and "quantum" norms, as n becomes large? For a wide class of random matrices, the answer is yes, and shows a gap between the two values. This result may be interpreted as follows: correlations sampled at random close enough to the border of the quantum set are typically intrinsically quantum (i.e. outside the classical set). On the technical side, the ingredients needed to establish such result include: tensor norms on Banach spaces, random matrix theory, concentration of measure in high dimension... But no prerequisite on any of these topics will be necessary to understand the talk. (Based on joint work with C. Gonzalez-Guillen, C. Palazuelos, I. Villanueva.)

Two profound ideas, quantum error correction and holography have recently been found to be deeply connected. Quantum error correction shows that reliable quantum information storage can be achieved from imperfect physical components. Holography is a duality between two distinct description of a quantum systems with the exact same predictions. The first is the prevailing description of our universe which includes gravity and quantum theory. The second description allows a solid mathematical foundation through a quantum field theory at lower spatial dimension. Quantum information tools such as entanglement, quantum error correction and compression have proven useful tools to gain high level understanding of this duality. Conversely, the holographic duality is suggesting directions in quantum information requiring further exploration. In this talk, I will introduce some of these connections, describe explicit toy models which exhibit some properties expected in holography and explore the implications of holographic predictions from a code-theoretic perspective.

Non-local games are an operational interpretation of Bell scenarios in which the players, who are unable to communicate while the game is in progress, try to maximize the probability that they win at a simple cooperative game. Let $E(\epsilon)$ be the amount of entanglement required by the players to play a non-local game $\epsilon$-optimally. Can we find non-local games where $E(\epsilon)$ grows very fast as $\epsilon \rightarrow 0$? So far, the best examples are games where $E(\epsilon)$ grows sub-exponentially, i.e. like $2^{Cn}$ for some constant $C$. I'll explain how to get a two-player game of this type by constructing a group with (at least) sub-exponential hyperlinear profile.