COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

## Hierarchies and nets for separable statesAdd to your list(s) Download to your calendar using vCal - Aram Harrow (MIT)
- Monday 20 April 2015, 16:00-17:00
- MR15, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.
If you have a question about this talk, please contact William Matthews. Given a mixed quantum state, is it entangled or separable? This basic question turns out to be closely related to a wide range of problems in quantum information and classical optimization. These include QMA with multiple provers, mean-field theory, estimating minimum output entropies of quantum channels and the unique games conjecture. The leading algorithm known for this problem is the semidefinite programming (SDP) hierarchy due to Doherty, Parrilo and Spedalieri (DPS). In this talk I will describe recent progress on finding algorithms for optimizing over separable states. 1. The DPS hierarchy is known to never converge at any finite level in any dimension where entangled states with positive partial transpose exist. I will describe an improved version which always does at least as well as DPS and converges exactly at a finite level. This yields an exponential time algorithm for exact separability testing. 2. On the negative side, I will show limitations on both DPS , the improved version, or indeed any SDP for separability testing. These limitations match the previously known bounds (Omega(log(n)) levels are required for constant error, or n^{Omega(1)} levels are needed for 1/poly(n) error) but now are proved unconditionally. Previously these were only known to hold based on the assumption that 3-SAT required exponential time. 3. Some of the strongest known results about the DPS hierarchy are due to Brandao, Christandl and Yard, and show that after O(log(n)) levels it already gives nontrivial approximations in the norm induced by 1-LOCC measurements. I will describe an alternate algorithm achieving similar performance based instead on brute-force enumeration over epsilon nets. This algorithm admits some natural generalizations and also gives some geometric intuition for why 1-LOCC measurements are especially easy to handle. 1 & 2 are joint work with Anand Natarajan and Xiaodi Wu. 3 is joint work with Fernando Brandao. This talk is part of the CQIF Seminar series. ## This talk is included in these lists:- All CMS events
- CMS Events
- CQIF Seminar
- DAMTP info aggregator
- Hanchen DaDaDash
- Interested Talks
- MR15, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
- bld31
Note that ex-directory lists are not shown. |
## Other listsArrol Adam Lectures - 'Responses to the First World War' Arrol Adam Lecture Series PLACEB-O 'In Conversation' Seminar Series Cambridge Next Generation Sequencing Bioinformatics Day II British Antarctic Survey's Natural Complexity: Data and Theory in Dialogue## Other talksTALK CANCELLED Targets for drug discovery: from target validation to the clinic Emergence in Physics: Life, the Universe and the Nature of Reality Barnum, Bache and Poe: the forging of science in the Antebellum US The Exposome in Epidemiological Practice Advanced NMR applications TODAY Adrian Seminar - "Physiological and genetic heterogeneity in hearing loss" |