Quantum Bilinear Optimization
- Creators
-
Berta, Mario
- Fawzi, Omar
- Scholz, Volkher B.
Abstract
We study optimization programs given by a bilinear form over noncommutative 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. Compared to previous work of Pironio, Navascués, and Acín [SIAM J. Optim., 20 (2010), pp. 2157-2180], our hierarchy has additional constraints. By means of examples, we illustrate the importance of these new constraints both in practice and for analytical properties. Moreover, this allows us to give a hierarchy of SDP outer approximations for the completely positive semidefinite cone introduced by Laurent and Piovesan.
Additional Information
© 2016 Society for Industrial and Applied Mathematics. Submitted 1 September 2015; accepted 12 May 2016; published online: 2 August 2016. We thank Hamza Fawzi and Thomas Vidick for helpful discussions. We would also like to thank Alhussein Fawzi and Hamza Fawzi for their help with writing and running MATLAB code. Part of this work was done while VBS was visiting the École Normale Supérieure de Lyon and part of it while visiting the Institute for Quantum Information and Matter at Caltech; we thank John Preskill and Thomas Vidick for their hospitality. VBS acknowledges partial support by the EU project Randomness and Quantum Entanglement (RAQUEL) and the NCCR QSIT.Attached Files
Published - 15m1037731.pdf
Submitted - 1506.08810v2.pdf
Files
| Name | Size | Download all |
|---|---|---|
|
md5:70906206cd183f1a5317859ee83088d6
|
384.9 kB | Preview Download |
|
md5:d939be7d375d284ea70b215499415978
|
539.0 kB | Preview Download |
Additional details
- Eprint ID
- 61144
- Resolver ID
- CaltechAUTHORS:20151015-102844005
- European Union
- Swiss National Science Foundation (SNSF)
- Created
-
2015-10-15Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field
- Caltech groups
- Institute for Quantum Information and Matter