Testing multipartite productness is easier than testing bipartite productness

We prove a lower bound on the number of copies needed to test the property of a multipartite quantum state being product across some bipartition (i.e., not genuinely multipartite entangled), given the promise that the input state either has this property or is ϵ-far in trace distance from any state with this property. We show that Ω(n/log n) copies are required (for fixed ϵ≤12), complementing a previous result that O(n/ϵ2) copies are sufficient. Our proof technique proceeds by considering uniformly random ensembles over such states, and showing that the trace distance between these ensembles becomes arbitrarily small for sufficiently large n unless the number of copies is at least Ω(n/log n). We discuss implications for testing graph states and computing the generalized geometric measure of entanglement.