Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum coins and quantum sampling

Howard Dale

Published Sep 1, 2016• 0 citations
Publisher

Abstract

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.

DOI
10.25560/49203

Related papers

Experimental demonstration of quantum-to-quantum Bernoulli factory

Xiang Zhan, Kunkun Wang, Lei Xiao +2 more

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.

Physical Review A•Jul 6, 2020•7 citations

Experimental Quantum Bernoulli Factories via Bell-Basis Measurements

Tanay Roy

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.

quant-pharXiv:2602.06193•Applied Physics Letters•Feb 9, 2026•0 citations

Quantum-to-quantum Bernoulli factory problem

Jiaqing Jiang, Jialin Zhang, Xiaoming Sun

Given a coin with unknown bias $p\ensuremath{\in}[0,1]$, can we exactly simulate another coin with bias $f(p)$? The exact set of simulable functions has been well characterized 20 years ago. In this paper, we ask the quantum counterpart of this question: Given the quantum coin $|p\ensuremath{\rangle}=\sqrt{p}|0\ensuremath{\rangle}+\sqrt{1\ensuremath{-}p}|1\ensuremath{\rangle}$, can we exactly simulate another quantum coin $|f(p)\ensuremath{\rangle}=\sqrt{f(p)}|0\ensuremath{\rangle}+\sqrt{1\ensuremath{-}f(p)}|1\ensuremath{\rangle}$? We give the full characterization of simulable quantum state ${k}_{0}(p)|0\ensuremath{\rangle}+{k}_{1}(p)|1\ensuremath{\rangle}$ from quantum coin $|p\ensuremath{\rangle}=\sqrt{p}|0\ensuremath{\rangle}+\sqrt{1\ensuremath{-}p}|1\ensuremath{\rangle}$, and present an algorithm to transform it. Surprisingly, we show that simulable sets in the quantum-to-quantum case and classical-to-classical case have no inclusion relationship with each other.

arXiv:1712.09817•Physical Review A•Mar 7, 2018•14 citations

Complexity and multi-functional variants of the Quantum-to-Quantum Bernoulli Factories

Francesco Hoch, Taira Giordani, Gonzalo Carvacho +2 more

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.

quant-pharXiv:2512.10810•Physical Review Research•Dec 12, 2025•0 citations

Photonic Quantum-to-Quantum Bernoulli facotry

Francesco Hoch, Giovanni Rodari, Taira Giordani +12 more

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 parameter$p$, allow one to simulate exactly a new Bernoulli distribution with parameter$f(p)$for a given function$f(x):\mathscr{D}\subseteq[0,1]\rightarrow[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.

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)•Jun 23, 2025•0 citations

Interplay between Quantumness, Randomness, and Selftesting

Xiao Yuan

Quantum information processing shows advantages in many tasks, including quantum communication and computation, comparing to its classical counterpart. The essence of quantum processing lies on the fundamental difference between classical and quantum states. For a physical system, the coherent superposition on a computational basis is different from the statistical mixture of states in the same basis. Such coherent superposition endows the possibility of generating true random numbers, realizing parallel computing, and other classically impossible tasks such as quantum Bernoulli factory. Considering a system that consists of multiple parts, the coherent superposition that exists nonlocally on different systems is called entanglement. By properly manipulating entanglement, it is possible to realize computation and simulation tasks that are intractable with classical means. Investigating quantumness, coherent superposition, and entanglement can shed light on the original of quantum advantages and lead to the design of new quantum protocols. This thesis mainly focuses on the interplay between quantumness and two information tasks, randomness generation and selftesting quantum information processing. We discuss how quantumness can be used to generate randomness and show that randomness can in turn be used to quantify quantumness. In addition, we introduce the Bernoulli factory problem and present the quantum advantage with only coherence in both theory and experiment. Furthermore, we show a method to witness entanglement that is independent of the realization of the measurement. We also investigate randomness requirements in selftesting tasks and propose a random number generation scheme that is independent of the randomness source.

arXiv:1703.00656•Mar 2, 2017•0 citations
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.
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.
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)=2pf(p)=2pf(p)=2p and, as intermediate outputs from the same Bell-measurement statistics, an exact fair coin f(p)=1/2f(p)=1/2f(p)=1/2 and the classically inconstructible function f(p)=4p(1−p)f(p)=4p(1-p)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.
Given a coin with unknown bias $p\ensuremath{\in}[0,1]$, can we exactly simulate another coin with bias f(p)f(p)f(p)? The exact set of simulable functions has been well characterized 20 years ago. In this paper, we ask the quantum counterpart of this question: Given the quantum coin $|p\ensuremath{\rangle}=\sqrt{p}|0\ensuremath{\rangle}+\sqrt{1\ensuremath{-}p}|1\ensuremath{\rangle}$, can we exactly simulate another quantum coin $|f(p)\ensuremath{\rangle}=\sqrt{f(p)}|0\ensuremath{\rangle}+\sqrt{1\ensuremath{-}f(p)}|1\ensuremath{\rangle}$? We give the full characterization of simulable quantum state ${k}_{0}(p)|0\ensuremath{\rangle}+{k}_{1}(p)|1\ensuremath{\rangle}$ from quantum coin $|p\ensuremath{\rangle}=\sqrt{p}|0\ensuremath{\rangle}+\sqrt{1\ensuremath{-}p}|1\ensuremath{\rangle}$, and present an algorithm to transform it. Surprisingly, we show that simulable sets in the quantum-to-quantum case and classical-to-classical case have no inclusion relationship with each other.
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 parameterppp, allow one to simulate exactly a new Bernoulli distribution with parameterf(p)f(p)f(p)for a given functionf(x):D⊆[0,1]→[0,1]f(x):\mathscr{D}\subseteq[0,1]\rightarrow[0,1]f(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.
Quantum information processing shows advantages in many tasks, including quantum communication and computation, comparing to its classical counterpart. The essence of quantum processing lies on the fundamental difference between classical and quantum states. For a physical system, the coherent superposition on a computational basis is different from the statistical mixture of states in the same basis. Such coherent superposition endows the possibility of generating true random numbers, realizing parallel computing, and other classically impossible tasks such as quantum Bernoulli factory. Considering a system that consists of multiple parts, the coherent superposition that exists nonlocally on different systems is called entanglement. By properly manipulating entanglement, it is possible to realize computation and simulation tasks that are intractable with classical means. Investigating quantumness, coherent superposition, and entanglement can shed light on the original of quantum advantages and lead to the design of new quantum protocols. This thesis mainly focuses on the interplay between quantumness and two information tasks, randomness generation and selftesting quantum information processing. We discuss how quantumness can be used to generate randomness and show that randomness can in turn be used to quantify quantumness. In addition, we introduce the Bernoulli factory problem and present the quantum advantage with only coherence in both theory and experiment. Furthermore, we show a method to witness entanglement that is independent of the realization of the measurement. We also investigate randomness requirements in selftesting tasks and propose a random number generation scheme that is independent of the randomness source.