We demonstrate theoretically a parallelized C-NOT gate which allows to entangle a mesoscopic ensemble of atoms with a single control atom in a single step, with high fidelity and on a microsecond timescale. Our scheme relies on the strong and long-ranged interaction between Rydberg atoms triggering Electromagnetically Induced Transparency (EIT). By this we can robustly implement a conditional transfer of all ensemble atoms among two logical states, depending on the state of the control atom. We outline a many body interferometer which allows a comparison of two many-body quantum states by performing a measurement of the control atom.