Quantum Information

Given a vector in a representation, can it be distinguished from zero by an invariant polynomial? This classical question in invariant theory relates to a diverse set of problems in mathematics and computer science. In quantum information, it captures the quantum marginal problem and recent bounds on tensor ranks. We will see that the general question can be usefully thought of as an optimization problem and discuss how this perspective leads to efficient algorithms for solving it.

 

Quantum Thermal Machines

https://drive.google.com/drive/folders/1L6a1YCdB9EejAUmZ52oLDAeB6oosjwhU?usp=sharing

https://www.dropbox.com/sh/sprq2u40e3leoso/AADhyov350QS9TEDdgtErekCa?dl=0

https://github.com/gsellaroli/pi-summer-school-2020

Fluctuation Theorems and Quantum Information

https://drive.google.com/drive/folders/1L6a1YCdB9EejAUmZ52oLDAeB6oosjwhU?usp=sharing

https://www.dropbox.com/sh/sprq2u40e3leoso/AADhyov350QS9TEDdgtErekCa?dl=0

https://github.com/gsellaroli/pi-summer-school-2020

Quantum Thermal Operations

https://drive.google.com/drive/folders/1L6a1YCdB9EejAUmZ52oLDAeB6oosjwhU?usp=sharing

https://www.dropbox.com/sh/sprq2u40e3leoso/AADhyov350QS9TEDdgtErekCa?dl=0

https://github.com/gsellaroli/pi-summer-school-2020

Resource Theories and Quantum Information

https://drive.google.com/drive/folders/1L6a1YCdB9EejAUmZ52oLDAeB6oosjwhU?usp=sharing

https://www.dropbox.com/sh/sprq2u40e3leoso/AADhyov350QS9TEDdgtErekCa?dl=0

https://github.com/gsellaroli/pi-summer-school-2020

Foundations of Quantum Statistical Mechanics - Entanglement

https://drive.google.com/drive/folders/1L6a1YCdB9EejAUmZ52oLDAeB6oosjwhU?usp=sharing

https://www.dropbox.com/sh/sprq2u40e3leoso/AADhyov350QS9TEDdgtErekCa?dl=0

https://github.com/gsellaroli/pi-summer-school-2020

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.

We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating player can try to bias the output bit towards a preferred value. A weak coin-flipping protocol has a bias ϵ if neither player can force the outcome towards their preferred value with probability more than 1/2+ϵ. While it is known that classically ϵ=1/2, Mochon showed in 2007 [arXiv:0711.4114] that quantumly weak coin flipping can be achieved with arbitrarily small bias, i.e. ϵ(k)=1/(4k+2) for arbitrarily large k, and he proposed an explicit protocol approaching bias 1/6. So far, the best known explicit protocol is the one by Arora, Roland and Weis, with ϵ(2)=1/10 (corresponding to k=2) [STOC'19, p. 205-216]. In the current work, we present the construction of protocols approaching arbitrarily close to zero bias, i.e. ϵ(k) for arbitrarily large k. We connect the algebraic properties of Mochon's assignments---at the heart of his proof of existence---with the geometric properties of the unitaries whose existence he proved. It is this connection that allows us to find these unitaries analytically.