Quantum Bilinear Optimization

Abstract

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. Compared to previous work of Pironio, Navascues and Acin, 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.

v3: published version

References in corpus (7)

• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• Bounding the set of quantum correlations
• Leftover Hashing Against Quantum Side Information
• Connes' embedding problem and Tsirelson's problem
• Entanglement-Enhanced Classical Communication over a Noisy Classical Channel
• Closed sets of correlations: answers from the zoo
• Quantum-proof randomness extractors via operator space theory

Cited by in corpus (19)

• Characterising the correlations of prepare-and-measure quantum networks
• Semidefinite programming relaxations for quantum correlations
• Non-asymptotic entanglement distillation
• Nonadditivity of Rains' bound for distillable entanglement
• Semidefinite programming hierarchies for constrained bilinear optimization
• Indistinguishability of bipartite states by positive-partial-transpose operations in the many-copy scenario
• Limitations of semidefinite programs for separable states and entangled games
• Quantum-proof randomness extractors via operator space theory
• Naturally restricted subsets of nonsignaling correlations: typicality and convergence
• Connector tensor networks: a renormalization-type approach to quantum certification
• Semi-device-independently characterizing quantum temporal correlations
• Jointly constrained semidefinite bilinear programming with an application to Dobrushin curves
• Optimality of meta-converse for channel simulation
• Five Starter Pieces: Quantum Information Science via Semi-definite Programs
• Privacy Amplification Against Active Quantum Adversaries
• Quantum Decomposition Algorithm For Master Equations of Stochastic Processes: The Damped Spin Case
• Quantum channel coding: Approximation algorithms and strong converse exponents
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• A Semidefinite Hierarchy for Disjointly Constrained Multilinear Programming