### Abstract

For every constant ϵ > 0, we give an exp(Õ(√n))-time algorithm for the 1 vs 1 - ϵ Best Separable State (BSS) problem of distinguishing, given an n^{2} × n^{2} matrix M corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state ρ that M accepts with probability 1, and the case that every separable state is accepted with probability at most 1 - ϵ. Equiva-lently, our algorithm takes the description of a subspace W ⊆ F^{n2} (where F can be either the real or complex feld) and distinguishes between the case that W contains a rank one matrix, and the case that every rank one matrix is at least ϵ far (in 12 distance) from W. To the best of our knowledge, this is the first improvement over the brute-force exp(n)-time algorithm for this problem. Our algorithm is based on the sum-of-squares hierarchy and its analysis is inspired by Lovett's proof (STOC '14, JACM '16) that the communication complexity of every rank-n Boolean matrix is bounded by Õ(√n).

Original language | English (US) |
---|---|

Title of host publication | STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Pierre McKenzie, Valerie King, Hamed Hatami |

Publisher | Association for Computing Machinery |

Pages | 975-988 |

Number of pages | 14 |

ISBN (Electronic) | 9781450345286 |

DOIs | |

State | Published - Jun 19 2017 |

Event | 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada Duration: Jun 19 2017 → Jun 23 2017 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | Part F128415 |

ISSN (Print) | 0737-8017 |

### Other

Other | 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 |
---|---|

Country | Canada |

City | Montreal |

Period | 6/19/17 → 6/23/17 |

### All Science Journal Classification (ASJC) codes

- Software

## Fingerprint Dive into the research topics of 'Qantum entanglement, sum of squares, and the log rank conjecture'. Together they form a unique fingerprint.

## Cite this

*STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing*(pp. 975-988). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F128415). Association for Computing Machinery. https://doi.org/10.1145/3055399.3055488