Quantum Advantage: A Non-Local Approach

This presentation will overview several results concerning tasks, some computational and some information theoretic, at which quantum hardware can outperform classical hardware.  A common mathematical theme in the design of each of these tasks is a quantum mechanical phenomenon called non-locality.  The first result is a modification of a breakthrough work of Bravyi, Gosset, and Koenig, wherein we achieve an improved soundness scaling for the circuit separation established in that work, and also develop an application of their framework to a cryptographic task known as randomness expansion.  The second result resolves, in the affirmative, an open question about whether unbounded randomness expansion is possible.  Time permitting we may cover new results establishing efficient upper and lower bounds on the communication cost of state conversion, and complexity lower bounds for the problem of computing the entangled value of a non-local game to high precision.