Although we strongly believe that quantum computers will be more powerful than their classical counterparts, proving this is out of reach of current techniques. For communication tasks (eg cryptographic key distribution) there is a provable quantum advantage. In this talk I will discuss a new task for which we can prove a quantum advantage, a task much closer to computation than communication. This task revolves around determining what randomness can you produce given access to a coin with an unknown bias. I will discuss how quantum coins with unknown bias can generate randomness that is impossible to generate with classical coins, and then give an overview of why we believe this can be a route to finding new quantum algorithms.