  Quantum advantage is notoriously hard to find and even harder to prove. For
example the class of functions computable with classical physics actually
exactly coincides with the class computable quantum-mechanically. It is
strongly believed, but not proven, that quantum computing provides exponential
speed-up for a range of problems, such as factoring. Here we address a
computational scenario of "randomness processing" in which quantum theory
provably yields, not only resource reduction over classical stochastic physics,
but a strictly larger class of problems which can be solved. Beyond new
foundational insights into the nature and malleability of randomness, and the
distinction between quantum and classical information, these results also offer
the potential of developing classically intractable simulations with currently
accessible quantum technologies.
