DYNAMIC QUANTUM BERNOULLI RANDOM WALKS

Philippe Biane

Caishi Wang, Ce Wang, Suling Ren +1 more

Swarnadeep Majumder, Austen Couvertier

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.

Nadine Guillotin‐Plantard, René Schott

Quantum Bernoulli random walks can be realized as random walks on the dual of SU(2). We use this realization in order to study a model of dynamic quantum Bernoulli random walk with time-dependent transitions. For the corresponding dynamic random walk on the dual of SU(2), we prove several limit theorems (local limit theorem, central limit theorem, law of large numbers, large deviation principle). In addition, we characterize a large class of transient dynamic random walks.

Luigi Accardi, G. S. Watson