Qantum entanglement, sum of squares, and the log rank conjecture

Boaz Barak, Pravesh Kumar Kothari, David Steurer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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 n2 × n2 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 ⊆ Fn2 (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 languageEnglish (US)
Title of host publicationSTOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
EditorsPierre McKenzie, Valerie King, Hamed Hatami
PublisherAssociation for Computing Machinery
Pages975-988
Number of pages14
ISBN (Electronic)9781450345286
DOIs
StatePublished - Jun 19 2017
Event49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada
Duration: Jun 19 2017Jun 23 2017

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F128415
ISSN (Print)0737-8017

Other

Other49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
CountryCanada
CityMontreal
Period6/19/176/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

    Barak, B., Kothari, P. K., & Steurer, D. (2017). Qantum entanglement, sum of squares, and the log rank conjecture. In P. McKenzie, V. King, & H. Hatami (Eds.), 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