Apparatus and methods for high fidelity quantum communication over long communication channels even in the presence of significant loss in the channels are disclosed. The invention employs laser manipulation of quantum correlated atomic ensembles using linear optic components, optical sources of low intensity pulses, beam splitters, and single-photon detectors requiring only moderate efficiencies. The invention provides fault-tolerant entanglement generation and connection, using a sequence of steps that each provide built-in entanglement purification and that are each resilient to the realistic noise. The invention relies upon collective excitation in atomic ensembles rather than single particle excitations in atomic ensembles so that communication efficiency scales polynomially with the total length of a communication channel.