Southwest Quantum Information and Technology

Quantum-proof randomness extractors via hierarchies of semidefinite programs

Mario Berta, Institute for Quantum Information and Matter Caltech

view abstract +

Randomness extractors are an important building block for classical and quantum cryptography as well as for device independent randomness amplification and expansion. However, for these applications it is often crucial that the extractors are quantum-proof, i.e., that they work even in the presence of quantum adversaries. In general, quantum-proof extractors are poorly understood: we only know that some standard constructions of extractors are quantum-proof and there is one example of an extractor (with quite bad parameters) that is not quantum-proof. We argue that in the same way as communication complexity and Bell inequalities (multi prover games), the setting of randomness extractors provides a operationally useful framework for studying the power and limitations of a quantum memory compared to a classical one. We start by recalling how to phrase the extractor property as a quadratic program with linear constraint, and show that this quadratic program can be approximated by a converging Lasserre type hierarchy of semidefinite programs (sdp). We then show that allowing non-commuting variables in the quadratic program naturally characterises quantum-proof extractors, and again give a converging (non-commutative) hierarchy of sdp relaxations. By construction, the first level of the commutative and the non-commutative hierarchy are the same whereas higher level relaxations are generally different. This gives a unifying approach to understand the stability properties of extractors against quantum adversaries. By studying the integrality gap of the first level sdp approximation we recover all known results about quantum-proof extractors and derive new dimension dependent stability and instability bounds. This submission is joint work with Omar Fawzi and Volkher Scholz (not online yet, but partly based on arXiv:1409.3563).