TY - GEN

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

AU - Barak, Boaz

AU - Kothari, Pravesh K.

AU - Steurer, David

N1 - Publisher Copyright:
© 2017 ACM.

PY - 2017/6/19

Y1 - 2017/6/19

N2 - 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).

AB - 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).

KW - Best separable state problem

KW - Polynomial reweighting

KW - Sum-of-squares semidefinite programming hierarchy

UR - http://www.scopus.com/inward/record.url?scp=85024385695&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85024385695&partnerID=8YFLogxK

U2 - 10.1145/3055399.3055488

DO - 10.1145/3055399.3055488

M3 - Conference contribution

AN - SCOPUS:85024385695

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 975

EP - 988

BT - STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

A2 - McKenzie, Pierre

A2 - King, Valerie

A2 - Hatami, Hamed

PB - Association for Computing Machinery

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

Y2 - 19 June 2017 through 23 June 2017

ER -