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.
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.
Quantum computing is rapidly becoming one of the largest research areas in quantum physics and yet we are still unable to prove the superiority of quantum computing over classical with the exception of a few contrived and unrealistic scenarios. Understanding the areas in which quantum computing provides an advantage and, more importantly, where that advantage comes from is the key to making progress in the field. We certainly do not solve this mystery in this thesis but do explore some unconventional routes through which answers may be found in the future. To this end we explore quantum advantage in a different computational setting. Rather than working with Turing Machines as most research does, we focus on the Bernoulli Factory: a randomness processing scheme studied in the fields of statistics and computer science. The Bernoulli Factory takes an infinite string of random bits generated with a fixed unknown bias as input and outputs a single random bit, the bias of which is a function of the input bias. This can be seen more intuitively as generating one biased coin from another, given a desired relationship between the two biases. The Bernoulli Factory is inherently probabilistic, like quantum mechanics, and so, it leads us to questions about the fundamental nature of quantum randomness and quantum sampling. We find, as we hoped, that the Bernoulli Factory is more tractable than the Turing Machine and that we are able to prove quantum superiority in both resource efficiency and classes of computable functions. We first give the quantum analogue of the classical Keane-O'’Brien theorem which establishes the increased class of computable functions for the quantum case. We then adjust the problem in a variety of ways, such as introducing multiple coins, errors in state preparation, phases and restriction on the bias or operations allowed. These lead to additional results which lend insight into the problems faced in quantum computing as well as the nature of quantum randomness.
Coherently manipulating multipartite quantum correlations leads to remarkable advantages in quantum information processing. A fundamental question is whether such quantum advantages persist only by exploiting multipartite correlations, such as entanglement. Recently, Dale, Jennings, and Rudolph negated the question by showing that a randomness processing, quantum Bernoulli factory, using quantum coherence, is strictly more powerful than the one with classical mechanics. In this Letter, focusing on the same scenario, we propose a theoretical protocol that is classically impossible but can be implemented solely using quantum coherence without entanglement. We demonstrate the protocol by exploiting the high-fidelity quantum state preparation and measurement with a superconducting qubit in the circuit quantum electrodynamics architecture and a nearly quantum-limited parametric amplifier. Our experiment shows the advantage of using quantum coherence of a single qubit for information processing even when multipartite correlation is not present.
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.
Quantum advantage is notoriously hard to find and even harder to prove. For example the class of functions computable with classical physics 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. Although quantum alternatives of various classical tasks are considered advantageous, this is typically extremely difficult to concretely prove. Here, the authors show that a quantum approach to randomness processing provides a reduction in resources and a larger class of solvable problems.