2014/10/29 by Renan Gross, Scott Aaronson, Gross, Renan +1
Computer Science · Physics and Astronomy · #Chaos-based Image/Signal Encryption #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.1410.8019
arxiv created 2014/10/29 · openalex publication_date 2014/10/29 · arxiv updated 2014/10/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Recent randomness expansion protocols have been proposed which are able to generate an unbounded amount of randomness from a finite amount of truly random initial seed. One such protocol, given by Miller and Shi, uses a pair of non-signaling untrusted quantum mechanical devices. These play XOR games with inputs given by the user in order to generate an output. Here we present an analysis of the required seed size, giving explicit upper bounds for the number of initial random bits needed to jump-start the protocol. The bits output from such a protocol are ε-close to uniform even against quantum adversaries. Our analysis yields that for a statistical distance of ε=10-1 and ε=10-6 from uniformity, the number of required bits is smaller than 225,000 and 715,000, respectively; in general it grows as O(log(1)/(ε)).