Preparation, manipulation and detection of strongly correlated states of quantum many-body systems are among the most important goals and challenges of modern physics. Ultracold atoms offer an unprecedented playground for the realization of these goals. Here, we propose a method for detecting strongly correlated states of ultracold atoms in a quantum non-demolition scheme, that is, in the fundamentally least destructive way permitted by quantum mechanics. In our method, spatially resolved components of atomic spins couple to quantum polarization degrees of freedom of light. In this way, quantum correlations of matter are faithfully mapped on those of light; the latter can then be efficiently measured using homodyne detection. We illustrate the power of such spatially resolved quantum-noise-limited polarization measurement by applying this method to the detection of various standard and exotic types of antiferromagnetic order in lattice systems, and by indicating the feasibility of detection of superfluid order in Fermi liquids. © 2008 Nature Publishing Group.