  Graph states are an important class of multipartite entangled states.
Previous experimental generation of graph states and in particular the
Greenberger-Horne-Zeilinger (GHZ) states in linear optics quantum information
schemes is subjected to an exponential decay in efficiency versus the system
size, which limits its large-scale applications in quantum networks. Here we
demonstrate an efficient scheme to prepare graph states with only a polynomial
overhead using long-lived atomic quantum memories. We generate atom-photon
entangled states in two atomic ensembles asynchronously, retrieve the stored
atomic excitations only when both sides succeed, and further project them into
a four-photon GHZ state. We measure the fidelity of this GHZ state and further
demonstrate its applications in the violation of Bell-type inequalities and in
quantum cryptography. Our work demonstrates the prospect of efficient
generation of multipartite entangled states in large-scale distributed systems
with applications in quantum information processing and metrology.
