What property of the simple W state makes it violate the validity of the approximation? Note that for each qubit, the GHZ and balanced generalized W states have an equal number of zeros and ones across all the basis states. The simple W state obviously does not have this property. To understand why this is important, let us reconsider the maximization problem of finding the nearest product state | ϕ 〉 . We can explore the possible product states by taking a small variation around some basis state | k$_{0}$ 〉 . For two binary numbers k$_{1}$ and k$_{2}$ , let us denote the Hamming distance between them, which is the number of bits they differ on, as d ( k$_{1}$, k$_{2}$ ) . We can then divide the set S to disjoint subsets according to the Hamming distance from k$_{0}$ : Without loss of generality we can fix k$_{0}$ = 0 (this can be arranged by applying local NOT gates which do not affect the entanglement nor the Hamming distances). The Hamming distance d ( k, k$_{0}$ ) is then equal to the number of ones in k , and a small variation around k$_{0}$ means that the x$_{m}$ ’s are small. The terms in Eq. (13) can then be grouped according to the subsets of S : The n th term in this expansion has n multiplicands of the form √ x$_{m}$ , so it is dominant in respect to the ( n +1) th term. Through this expansion we see that the nearest product state is in the close surrounding of | k$_{0}$ 〉 only if S contains a lot of terms within a small Hamming distance from k$_{0}$ . In the case of the simple W state, all the terms in S have a Hamming distance of 1 from k$_{0}$ = 0 , thus maximizing the term n = 1 in the expansion. This shows that a large value of the function f q S can be obtained in the proximity of the state | 0 〉 , and indeed this is the case. The case of the balanced generalized W state | φ ( n, 2 n ) 〉 is different. In this case, for each basis state, there are n 2 basis states at a Hamming distance of 2, and one basis state at 11 f q $_{S}$( x$_{1}$, . . . , x$_{q}$ ) = 1 √ | S | q ∑ n =0 ∑ j$_{1}$...j q ∈ S n j$_{m}$$_{1}$,...,j$_{m}$$_{n}$ =1 √ x$_{m}$$_{1}$ · · · · · √ x$_{m}$$_{n}$ ∏ m = m$_{i}$ √$_{1}$ − x$_{m}$. (24) S = S$_{0}$ · ∪ . . . · ∪ S$_{q}$ S$_{m}$ = { k ∈ S : d ( k, k$_{0}$ ) = m } . (23) P q S − −− → q →∞ 0 P$_{max}$ ( W ) − −− → q →∞ 1 e . (22)