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

Boaz Barak, Pravesh K. Kothari, David Steurer

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

8 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
Country/TerritoryCanada
CityMontreal
Period6/19/176/23/17

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Best separable state problem
  • Polynomial reweighting
  • Sum-of-squares semidefinite programming hierarchy

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