High-quality InP/ZnS core-shell nanocrystal quantum dots (NQDs) were synthesized as a heavy-metal-free alternative to the gain media of cadmium-based colloidal nanoparticles. Upon UV excitation, amplified spontaneous emission (ASE) and optical gain were observed, for the first time, in close-packed InP/ZnS core-shell NQDs. The ASE wavelength can be selected by tailoring the nanocrystal size over a broad range of the spectrum. Moreover, the optical gain profile of InP/ZnS NQDs was matched to the second order feedback of holographic polymer-dispersed liquid crystal gratings, leading to the very first demonstration of an optically-pumped, nanocrystal laser based on InP/ZnS core-shell NQDs.