A Caltech Library Service

Quantum Bilinear Optimization

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.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper
Berta, Mario0000-0002-0428-3429
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
Funding AgencyGrant Number
Swiss National Science Foundation (SNSF)UNSPECIFIED
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
Record Number:CaltechAUTHORS:20151015-102844005
Persistent URL:
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
Deposited By: Tony Diaz
Deposited On:15 Oct 2015 20:11
Last Modified:10 Nov 2021 22:44

Repository Staff Only: item control page