  \textit{Ab initio} random structure searching based on density functional
theory is used to determine the ground-state structures of ice at high
pressures. Including estimates of lattice zero-point energies, ice is found to
adopt three novel crystal phases. The underlying sub-lattice of O atoms remains
similar among them, and the transitions can be characterized by reorganizations
of the hydrogen bonds. The symmetric hydrogen bonds of ice X and $Pbcm$ are
initially lost as ice transforms to structures with symmetries $Pmc2_1$ (800 -
950 GPa) and $P2_1$ (1.17 TPa), but they are eventually regained at 5.62 TPa in
a layered structure $C2/m$. The $P2_1 \rightarrow C2/m$ transformation also
marks the insulator-to-metal transition in ice, which occurs at a significantly
higher pressure than recently predicted.
