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 - https://www.scopus.com/pages/publications/85024385695
UR - https://www.scopus.com/pages/publications/85024385695#tab=citedBy
U2 - 10.1145/3055399.3055488
DO - 10.1145/3055399.3055488
M3 - Conference contribution
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 -