Randomness processing in a Bernoulli factory has been identified as an area where a quantum advantage may exist. We report two quantum photonic implementations of a Bernoulli factory which demonstrate large reductions in resources over their classical counterpart.
There has been a concerted effort to identify problems computable with quantum technology, which are intractable with classical technology or require far fewer resources to compute. Recently, randomness processing in a Bernoulli factory has been identified as one such task. Here, we report two quantum photonic implementations of a Bernoulli factory, one using quantum coherence and single-qubit measurements and the other one using quantum coherence and entangling measurements of two qubits. We show that the former consumes three orders of magnitude fewer resources than the best-known classical method, while entanglement offers a further fivefold reduction. These concepts may provide a means for quantum-enhanced performance in the simulation of stochastic processes and sampling tasks.
Randomness processing in the Bernoulli factory framework provides a concrete setting in which quantum resources can outperform classical ones. We experimentally demonstrate quantum randomness processing based on Bell-basis measurements of two identical input quoins prepared on IBM superconducting hardware. Using only the measurement outcomes (and no external classical randomness source), we realize the classically inconstructible Bernoulli doubling primitive f(p)=2p and, as intermediate outputs from the same Bell-measurement statistics, an exact fair coin f(p)=1/2 and the classically inconstructible function f(p)=4p(1−p). We benchmark the measured output biases against ideal predictions and discuss the impact of device noise. Our results establish a simple resource-efficient experimental primitive for quantum-to-classical randomness processing and support the viability of quantum Bernoulli factories for quantum-enhanced stochastic simulation and sampling tasks.
A Bernoulli factory is a model of randomness processing. Recently, the quantum generalization of a Bernoulli factory with a quantum input and classical output offers a clear advantage over classical means in simulating classical randomness. A more ``quantum'' version of a Bernoulli factory with a quantum input and quantum output has been proposed and shows applications in simulating quantum randomness using quantum resources, the so-called quantum-to-quantum Bernoulli factory, which simulates probability amplitudes rather than probability. In this paper, we report an experimental implementation of a quantum-to-quantum Bernoulli factory with linear optics. We implement three elements of a quantum-to-quantum Bernoulli factory, including inversion, multiplication, and addition, and demonstrate how to compare quantum states via a quantum-to-quantum Bernoulli factory. Our results provide a thorough understanding of the Bernoulli factory problem in the quantum world and will stimulate the quantum advantages in simulating a wider range of classically infeasible random processes.
Generation and manipulation of randomness is a relevant task for several applications of information technology. It has been shown that quantum mechanics offers some advantages for this type of task. A promising model for randomness manipulation is provided by Bernoulli factories—protocols capable of changing the bias of Bernoulli random processes in a controlled way. At first, this framework was proposed and investigated in a fully classical regime. Recent extensions of this model to the quantum case showed the possibility of implementing a wider class of randomness manipulation functions. We propose a Bernoulli factory scheme with quantum states as the input and output, using a photonic-path-encoding approach. Our scheme is modular and universal and its functioning is truly oblivious of the input bias—characteristics that were missing in earlier work. We report on experimental implementations using an integrated and fully programmable photonic platform, thereby demonstrating the viability of our approach. These results open new paths for randomness manipulation with integrated quantum technologies. A quantum-to-quantum Bernoulli factory is demonstrated by using a reconfigurable Clements’s squared unitary circuit in an integrated quantum photonic platform. Three interferometer designs are proposed for the basic operations of a field on qubit states.
A Bernoulli factory is a model for randomness manipulation that transforms an initial Bernoulli random variable into another Bernoulli variable by applying a predetermined function relating the output bias to the input one. In literature, quantum-to-quantum Bernoulli factory schemes have been proposed, which encode both the input and output variables using qubit amplitudes. This fundamental concept can serve as a subroutine for quantum algorithms that involve Bayesian inference and Monte Carlo methods, or that require data encryption, like in blind quantum computation. In this work, we present a characterisation of the complexity of the quantum-to-quantum Bernoulli factory by providing a lower bound on the required number of qubits needed to implement the protocol, an upper bound on the success probability and the quantum circuit that saturates the bounds. We also formalise and analyse two different variants of the original problem that address the possibility of increasing the number of input biases or the number of functions implemented by the quantum-to-quantum Bernoulli factory. The obtained results can be used as a framework for randomness manipulation via such an approach.
Randomness generation and manipulation algorithms are a cornerstone of information theory and in cryptography. In this context, the inherently random nature of quantum mechanics has proved to be a useful resource, leading to the realisation of several quantum information protocols. Within this framework, there is an increasing search for new techniques for generating and manipulating quantum randomness that can be used as sub-routines for quantum protocols. In recent years, there have been various proposals for quantum generalisations of a family of classical algorithms known as Bernoulli factories [1] which, starting from extractions of a Bernoulli distribution with unknown parameterp, allow one to simulate exactly a new Bernoulli distribution with parameterf(p)for a given functionf(x):D⊆[0,1]→[0,1]. In particular, it was shown that the use of quantum resources results in an advantage in terms of implementable functions [2], [3] and the average number of samples required by the algorithm.