Search Talks

MIP* denotes the class of problems that admit interactive proofs with quantum entangled provers. It has been an outstanding question to characterize the complexity of this class. Most notably, there was no known computable upper bound on MIP*.

We show that MIP* is equal to the class RE, the set of recursively enumerable languages. In particular, this shows that MIP* contains uncomputable problems. Through a series of known connections, this also yields a negative answer to Connes’ Embedding Problem from the theory of operator algebras. In this talk, I will explain the connection between Connes' Embedding Problem, quantum information theory, and complexity theory. I will then give an overview of our approach, which involves reducing the Halting Problem to the problem of approximating the entangled value of nonlocal games.

Joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John Wright.

Schur-Weyl duality is a ubiquitous tool in quantum information. At its heart is the statement that the space of operators that commute with the tensor powers of all unitaries is spanned by the permutations of the tensor factors. In this work, we describe a similar duality theory for tensor powers of Clifford unitaries. The Clifford group is a central object in many subfields of quantum information, most prominently in the theory of fault-tolerance. The duality theory has a simple and clean description in terms of finite geometries. We demonstrate its effectiveness in several applications: (1) We resolve an open problem in quantum property testing by showing that "stabilizerness" is efficiently testable: There is a protocol that, given access to six copies of an unknown state, can determine whether it is a stabilizer state, or whether it is far away from the set of stabilizer states. We give a related membership test for the Clifford group. (2) We find that tensor powers of stabilizer states have an increased symmetry group. We provide corresponding de Finetti theorems, showing that the reductions of arbitrary states with this symmetry are well-approximated by mixtures of stabilizer tensor powers (in some cases, exponentially well). (3) We show that the distance of a pure state to the set of stabilizers can be lower-bounded in terms of the sum-negativity of its Wigner function. This gives a new quantitative meaning to the sum-negativity (and the related mana) -- a measure relevant to fault-tolerant quantum computation. The result constitutes a robust generalization of the discrete Hudson theorem. (4) We show that complex projective designs of arbitrary order can be obtained from a finite number (independent of the number of qudits) of Clifford orbits. To prove this result, we give explicit formulas for arbitrary moments of random stabilizer states. (5) Lastly, we comment on the structure of the irreducible representations of the Clifford group.

A standard approach to quantifying resources is to determine which operations on the resources are freely available and to deduce the ordering relation among the resources that these operations induce. If the resource of interest is the nonclassicality of the correlations embodied in a quantum state, that is, entanglement, then it is typically presumed that the appropriate choice of free operations is local operations and classical communication (LOCC). We here argue that, in spite of the near-universal endorsement of the LOCC paradigm by the quantum information community, this is the wrong choice for one of the most prominent applications of entanglement theory, namely, the study of Bell scenarios. The nonclassicality of correlations in such scenarios, we argue, should be quantified instead by local operations and shared randomness (LOSR). We support this thesis by showing that various perverse features of the interplay between entanglement and nonlocality are merely an artifact of the use of LOCC-entanglement and that the interplay between LOSR-entanglement and nonlocality is natural and intuitive. Specifically, we show that the LOSR paradigm (i) provides a resolution of the "anomaly of nonlocality", wherein partially entangled states exhibit more nonlocality than maximally entangled states, (ii) entails a notion of genuine multipartite entanglement that is distinct from the conventional one and which is free of several of its pathological features, and (iii) makes possible a resource-theoretic account of the self-testing of entangled states which simplifies and generalizes prior results. Along the way, we derive some fundamental results concerning the necessary and sufficient conditions for convertibility between pure entangled states under LOSR and highlight some of their consequences, such as the impossibility of catalysis for bipartite pure states. 

Defining a generic quantum system requires, together with a Hilbert space and a Hamiltonian, the introduction of an algebra of observables, or equivalently a tensor product structure. Assuming a background time variable, Cotler, Penington and Ranard showed that the Hamiltonian selects an almost-unique tensor product structure. This result has been advocated by Carrol and collaborators as supporting the Everettian interpretation of quantum mechanics and providing a pivotal tool for quantum gravity. In this talk I argue against this, on the basis of the fact that the Cotler-Penington-Ranard result does not hold in the generic background-independent case where the Hamiltonian is replaced by a Hamiltonian constrain. This reinforces the understanding that entropy and entanglement, that in the quantum theory depend on the tensor product structure, are quantities that are observable dependent. To conclude, I would like to pose the question of whether clocks can be thought as a resource, and how thinking of time in terms of physical clocks can inform our interpretation of quantum mechanics

Causal reasoning is vital for effective reasoning in science and medicine. In medical diagnosis, for example, a doctor aims to explain a patient’s symptoms by determining the diseases causing them. This is because causal relations---unlike correlations---allow one to reason about the consequences of possible treatments. However, all previous approaches to machine-learning assisted diagnosis, including deep learning and model-based Bayesian approaches, learn by association and do not distinguish correlation from causation. I will show that these approaches systematically lead to incorrect diagnoses. I will outline a new diagnostic algorithm, based on counterfactual inference, which captures the causal aspect of diagnosis overlooked by previous approaches and overcomes these issues. I will additionally describe recent algorithms from my group which can discover causal relations from uncontrolled observational data and show how these can be applied to facilitate effective reasoning in medical settings such as deciding how to treat certain diseases.

Last fall, a team at Google announced the first-ever demonstration of "quantum computational supremacy"---that is, a clear quantum speedup over a classical computer for some task---using a 53-qubit programmable superconducting chip called Sycamore.  In addition to engineering, Google's accomplishment built on a decade of research in quantum computing theory.  This talk will discuss questions like: what exactly was the contrived computational problem that Google solved?  How does one verify the outputs using a classical computer?  And how confident are we that the problem really is classically hard---especially in light of subsequent counterclaims by IBM?  I'll end with a proposed application for Google's experiment---namely, the generation of certified random bits, for use (for example) in proof-of-stake cryptocurrencies---that I've been developing and that Google is now working to demonstrate.