Berta, Mario and Fawzi, Omar and Scholz, Volkher B. (2016) Quantum Bilinear Optimization. SIAM Journal of Optimization, 26 (3). pp. 1529-1564. ISSN 1052-6234. doi:10.1137/15M1037731. https://resolver.caltech.edu/CaltechAUTHORS:20151015-102844005
![]() |
PDF
- Published Version
See Usage Policy. 539kB |
![]() |
PDF
- Submitted Version
See Usage Policy. 384kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20151015-102844005
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.
Item Type: | Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||
ORCID: |
| ||||||||||||
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. | ||||||||||||
Group: | Institute for Quantum Information and Matter | ||||||||||||
Funders: |
| ||||||||||||
Subject Keywords: | Noncommutative Optimization; Bilinear Optimization; Semidefinite Hierarchies; Completely Positive Semidefinite Cone; Randomness Extractor; Noisy Channel Coding | ||||||||||||
Issue or Number: | 3 | ||||||||||||
Classification Code: | 81R15; 94A15; 81P45; 81P94; 90C22; 47N10 | ||||||||||||
DOI: | 10.1137/15M1037731 | ||||||||||||
Record Number: | CaltechAUTHORS:20151015-102844005 | ||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20151015-102844005 | ||||||||||||
Official Citation: | Berta, M., Fawzi, O., & Scholz, V. B. (2016). Quantum Bilinear Optimization. SIAM Journal on Optimization, 26(3), 1529-1564. doi:10.1137/15m1037731 | ||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
ID Code: | 61144 | ||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||
Deposited By: | Tony Diaz | ||||||||||||
Deposited On: | 15 Oct 2015 20:11 | ||||||||||||
Last Modified: | 10 Nov 2021 22:44 |
Repository Staff Only: item control page