Dr Terry Rudolph
Building a quantum computer is a notoriously difficult task; a universal quantum computer may still be decades away. We can, however, create non-universal quantum computers which may still have capabilities beyond those of classical computers. The most promising route for such systems is via linear optical networks, which have already been shown to be hard to simulate efficiently on a classical computer.
At the moment the challenge is making these optical circuits scalable as in their present form, using probabilistic single photon sources, the chance of obtaining a sample decreases exponentially with the size of the system. We hope to remedy this by finding other classes of input states, such as Gaussian states, and showing that they too would be hard to simulate efficiently.
All models which have evidence for their non-simulability produce samples from distributions, rather than solving decision problems. This leads us to consider that we might make more progress in quantum algorithms if we consider sampling problems instead of the traditional decision problems of classical computation, taking advantage of the inherently probabilistic nature of quantum mechanics.