# Quantum entanglement, sum of squares, and the log rank conjecture

arXiv: https://arxiv.org/abs/1701.06321 · HTML: https://mlsanity.com/paper/1701.06321/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2017.

## Built on by (most cited first, 5 of 5)

- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [List-Decodable Covariance Estimation](https://mlsanity.com/paper/2206.10942/) (2022)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)
- [Private graphon estimation via sum-of-squares](https://mlsanity.com/paper/2403.12213/) (2024)
- [Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond](https://mlsanity.com/paper/2212.03851/) (2022)

## Abstract (arXiv)

For every ε>0, we give an exp(tildeO(√n/ε2))-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-ε. Equivalently, our algorithm takes the description of a subspace W subseteq mathbbFn2 (where mathbbF can be either the real or complex field) 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 ℓ2 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 tildeO(√n).