Quantum Bilinear Optimization
arXiv:1506.08810 · doi:10.1137/15M1037731
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.
arXiv commentv3: published version
References in corpus (20)
- Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels
- Bell nonlocality
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Non-locality and Communication Complexity
- Entanglement-Assisted Classical Capacity of Noisy Quantum Channels
- Bounding the set of quantum correlations
- Leftover Hashing Against Quantum Side Information
- Connes' embedding problem and Tsirelson's problem
- Improving zero-error classical communication with entanglement
- Large violation of Bell inequalities with low entanglement
- Tsirelson's problem and Kirchberg's conjecture
- Convergent relaxations of polynomial optimization problems with non-commuting variables
- Quantum Bounds on Bell inequalities
- Graph Homomorphisms for Quantum Players
- The Smooth Entropy Formalism for von Neumann Algebras
- Entanglement-Enhanced Classical Communication over a Noisy Classical Channel
- Can you compute the operator norm?
- Closed sets of correlations: answers from the zoo
- Quantum-proof randomness extractors via operator space theory
- On optimal entanglement assisted one-shot classical communication
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