We report CO detections in 17 out of 19 infrared ultraluminous QSO (IR QSO) hosts observed with the IRAM 30 m telescope. The cold molecular gas reservoir in these objects is in a range of (0.2-2.1) x 10(10) M-circle dot (adopting a CO-to-H-2 conversion factor alpha CO = 0.8 M-circle dot (K km s(-1) pc(2))(-1)). We find that the molecular gas properties of IR QSOs, such as the molecular gas mass, star formation efficiency (L-FIR/L'(CO)), and CO (1-0) line widths, are indistinguishable from those of local ultraluminous infrared galaxies (ULIRGs). A comparison of low-and high-redshift CO-detected QSOs reveals a tight correlation between L-FIR and L'(CO(1-0)) for all QSOs. This suggests that, similar to ULIRGs, the far-infrared emissions of all QSOs are mainly from dust heated by star formation rather than by active galactic nuclei (AGNs), confirming similar findings from mid-infrared spectroscopic observations by Spitzer. A correlation between the AGN-associated bolometric luminosities and the CO line luminosities suggests that star formation and AGNs draw from the same reservoir of gas and there is a link between star formation on similar to kpc scale and the central black hole accretion process on much smaller scales.