Quantum Bilinear Optimization

Understand

We study optimization programs given by a bilinear form over non-commutative variables subject to linear inequalities.

• Problems of this form include the entangled value of two-prover games, entanglement-assisted coding for classical channels and quantum-proof randomness extractors.
• We introduce an asymptotically converging hierarchy of efficiently computable semidefinite programming (SDP) relaxations for this quantum optimization.
• This allows us to give upper bounds on the quantum advantage for all of these problems.