Commitments are equivalent to one-way state generators

One-way state generators (OWSG) are natural quantum analogs to classical one-way functions. We show that O(n/log(n))-copy OWSGs (n represents the input length) are equivalent to $poly(n)$-copy OWSG and to quantum commitments. Since known results show that o(n/log(n))-copy OWSG cannot imply commitments, this shows that O(n/log(n))-copy OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography). Our construction follows along the lines of H{a}stad, Impagliazzo, Levin and Luby [HILL], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the construction provided by [HILL]. Since we do not argue conditioned on the output of the one-way function, our construction and analysis are arguably simpler and may be of independent interest.