  Galaxies in the early Universe were more compact and contained more molecular
gas than today. In this paper, we revisit the relation between these empirical
findings, and we quantitatively predict the cosmic evolution of the surface
densities of atomic (HI) and molecular (H2) hydrogen in regular galaxies. Our
method uses a pressure-based model for the H2/HI-ratio of the Interstellar
Medium, applied to ~3*10^7 virtual galaxies in the Millennium Simulation. We
predict that, on average, the HI-surface density of these galaxies saturates at
Sigma_HI<10 Msun/pc^2 at all redshifts (z), while H2-surface densities evolve
dramatically as Sigma_H2(1+z)^2.4. This scaling is dominated by a (1+z)^2
surface brightness scaling originating from the (1+z)^-1 size scaling of
galaxies at high z. Current measurements of Sigma_H2 at high z, derived from
CO-observations, tend to have even higher values, which can be quantitatively
explained by a selection bias towards merging systems. However, despite the
consistency between our high-z predictions and the sparse empirical data, we
emphasize that the empirical data potentially suffer from serious selection
biases and that the semi-analytic models remain in many regards uncertain. As a
case study, we investigate the cosmic evolution of simulated galaxies, which
resemble the Milky Way at z=0. We explicitly predict their HI- and
H2-distribution at z=1.5, corresponding to the CO-detected galaxy BzK-21000,
and at z=3, corresponding to the primary science goal of the Atacama Large
Millimeter/submillimeter Array (ALMA).
