Limitations of monogamy, Tsirelson-type bounds, and other semidefinite programs in quantum information
We introduce a new method for proving limitations on the ability of semidefinite programs (SDPs) to approximately solve optimization problems. We use this to show specifically that SDPs have limited ability to approximate two particularly important sets in quantum information theory:
1. The set of separable (i.e. unentangled) states.
2. The set of quantum correlations; i.e. conditional probability distributions achievable with local measurements on a shared entangled state.
In both cases no-go theorems were previously known based on computational assumptions such as the Exponential Time Hypothesis (ETH) which asserts that 3-SAT requires exponential time to solve. Our unconditional results achieve the same parameters as all of these previous results (for separable states) or as some of the previous results (for quantum correlations) and show that any SDPs which approximately solve either of these problems must have a number of variables which grows very quickly with problem size.
These results can be viewed as limitations on the monogamy principle, the PPT test, the ability of Tsirelson-type bounds to restrict quantum correlations, as well as the SDP hierarchies of Doherty-Parrilo-Spedalieri, Navascues-Pironio-Acin and Berta-Fawzi-Scholz. Indeed a wide range of past work in quantum information can be described as using an SDP on one of the above two problems and our results put broad limits on these lines of argument.
This is joint work with Anand Natarajan and Xiaodi Wu.
Subscribe to A Quantum Bit
Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...
Sign Up Now
Sign up to receive A Quantum Bit in your email!