  Linear optics quantum computing (LOQC) is a leading candidate for the
implementation of large scale quantum computers. Here quantum information is
encoded into the quantum states of light and computation proceeds via a linear
optics network. It is well known that in such schemes there are stringent
requirements on the spatio-temporal structure of photons -- they must be
completely indistinguishable and of very high purity. We show that in the
Boson-sampling model for LOQC these conditions may be significantly relaxed. We
present evidence that by increasing the size of the system we can implement a
computationally hard algorithm even if our photons have arbitrarily low
fidelity and purity. These relaxed conditions make Boson-sampling LOQC within
reach of present-day technology.
