We report on the first demonstration of a quaternary-logical resonatorless optical memory element with information encoded in the structural phase of a single 80 nm gallium nanoparticle. The size of the memory element is comparable with bits in next-generation hard disks, and radically smaller than previously suggested memories exploiting optical resonators. Furthermore, the energy required for switching the nanoparticle is an order of magnitude less than needed in DVD, DVR, or hard disk technologies.