The Quantum Bernoulli Factory

Understanding the difference between quantum mechanics and classical probability theory amounts to understanding the difference between superposition and mixture. We take a classical sampling problem, the Bernoulli coin factory, and explore a quantum version of it. We find that the quantum factory can perform tasks which are impossible in the classical case. In some sense the Bernoulli factory can be considered as an alternate, although less applicable, kind of Turing machine. In this restricted setting results about quantum advantage become far easier to prove and the difference in capabilities between quantum and classical are much starker. By trying to identify which aspects of quantum theory are essential to this speed-up we can gain insight into what the necessary requirements for speed-up in conventional quantum computing are.