Finally managed to put the finishing touches on Relaxed uncertainty relations and information processing and get it out.

The result I find most interesting is about “learnability” of states. Although quantum states seem very complicated, requiring 2^n complex coefficients to describe a state of n qubits, Aaronson showed that actually quantum states are easy to learn, that is only it takes on the order of n measurements to figure out approximately what state you have. We show that if you allow more general states with the strongest nonlocal correlations allowed that don’t violate no-signaling, then it’s hard to learn states. That is, it will take exponentially many measurements to learn the approximate identity of a state. Another way in which quantum mechanics is powerful, but not too powerful.