Graph-connectivity-based strong quantum nonlocality with genuine entanglement

Strong nonlocality based on local distinguishability is a stronger form of quantum nonlocality recently introduced in multipartite quantum systems: an orthogonal set of multipartite quantum states is said to have the property of strong nonlocality if it is locally irreducible for every bipartition of the subsystems. Most of the known results are limited to sets with product states. Shi et al. presented the first result of strongly nonlocal sets with entanglement, and they questioned the existence of a strongly nonlocal set with genuine entanglement. In this work, we relate the strong nonlocality of some special set of genuine entanglement to the connectivities of some graphs. Using this relation, we successfully construct sets of genuinely entangled states with strong nonlocality. As a consequence, our constructions give a negative answer to Shi et al.'s question and also provide an answer to the open problem raised by Halder et al. This work associates a physical quantity named strong nonlocality with a mathematical quantity called graph connectivity.