"The notion of ’quantum supremacy’ has led to a concerted effort to identify problems computable with quantum technology which are intractable with classical technology or require far fewer resources to compute. Recently, the task of randomness processing in a Bernoulli factory has been identified as an area where a quantum advantage may exist. The Bernoulli factory is an algorithm which takes, as an input, a finite sequence of independent and identically distributed Bernoulli random variables, or coin flips, with an unknown bias p and then outputs a new function given by a coin with success probability f(p). The class of functions constructible in a Bernoulli factory was first defined by Keane and O’Brien. Specifically, i) f(p) must be continuous, ii) f(p) must not approach a value of 0 or 1 exponentially quickly near p = 0 or 1, and iii) f(p) != 0 or 1, for p ∈ (0,1). These criteria disqualify f(p)=2p, which is of great interest as it may lead to the construction of other Bernoulli factories. Alternatively, truncating this function by ε enables simulation with finite classical resources. In the randomness processing task, the goal is to not only transform from one probability distribution to another, but to do so with as fewer coin flips as possible. The number of coin flips can be interpreted as the number of times a Bernoulli random variable is queried from a generator, which is proportional to the run-time of the task. Dale et al. proposed replacing the classical coins with quantum coins or quoins. This extension to quoins enables algorithmic processing of coherent superpositions and entangled states, with a classical output.

Here we report an experimental demonstration of the quantum Bernoulli factory by simulating the function f(p)=2p under two scenarios, one which utilises single-qubit measurements and the other which utilises non-classical correlations by performing joint measurements of two qubits in the Bell basis. Our experiments reveal that for the single-qubit case, our quantum Bernoulli Factory requires on average ≈ 52 quoins to construct f(p) = 2p compared to ≈ 11 quoins in the two-qubit case, demonstrating that non-classical correlations offer almost a five-fold reduction in resources over single-qubit measurements alone. Furthermore, we estimate that 50000 classical coins would be required to reproduce our data, which shows that the quantum Bernoulli factory, with a resource reduction of three orders of magnitude, offers a clear quantum advantage over the best-known classical algorithm. These concepts may provide a means for quantum-enhanced performance in the simulation of stochastic processes and sampling tasks.

"