Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSearching for evidence of algorithmic randomness and incomputability in the output of quantum random number generators
63
0
0.0
(
0
)
Added by
Maximilian Schlosshauer
Publication date
2021
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Ideal quantum random number generators (QRNGs) can produce algorithmically random and thus incomputable sequences, in contrast to pseudo-random number generators. However, the verification of the presence of algorithmic randomness and incomputability is a nontrivial task. We present the results of a search for algorithmic randomness and incomputability in the output from two different QRNGs, performed by applying tests based on the Solovay-Strassen test of primality and the Chaitin-Schwartz theorem. The first QRNG uses measurements of quantum vacuum fluctuations. The second QRNG is based on polarization measurements on entangled single photons; for this generator, we use looped (and thus highly compressible) strings that also allow us to assess the ability of the tests to detect repeated bit patterns. Compared to a previous search for algorithmic randomness, our study increases statistical power by almost 3 orders of magnitude.
rate research
Read More
The advantages of quantum random number generators (QRNGs) over pseudo-random number generators (PRNGs) are normally attributed to the nature of quantum measurements. This is often seen as implying the superiority of the sequences of bits themselves generated by QRNGs, despite the absence of empirical tests supporting this. Nonetheless, one may expect sequences of bits generated by QRNGs to have properties that pseudo-random sequences do not; indeed, pseudo-random sequences are necessarily computable, a highly nontypical property of sequences. In this paper, we discuss the differences between QRNGs and PRNGs and the challenges involved in certifying the quality of QRNGs theoretically and testing their output experimentally. While QRNGs are often tested with standard suites of statistical tests, such tests are designed for PRNGs and only verify statistical properties of a QRNG, but are insensitive to many supposed advantages of QRNGs. We discuss the ability to test the incomputability and algorithmic complexity of QRNGs. While such properties cannot be directly verified with certainty, we show how one can construct indirect tests that may provide evidence for the incomputability of QRNGs. We use these tests to compare various PRNGs to a QRNG, based on superconducting transmon qutrits and certified by the Kochen-Specker Theorem, to see whether such evidence can be found in practice. While our tests fail to observe a strong advantage of the quantum random sequences due to algorithmic properties, the results are nonetheless informative: some of the test results are ambiguous and require further study, while others highlight difficulties that can guide the development of future tests of algorithmic randomness and incomputability.
In contrast with software-generated randomness (called pseudo-randomness), quantum randomness is provable incomputable, i.e. it is not exactly reproducible by any algorithm. We provide experimental evidence of incomputability --- an asymptotic property --- of quantum randomness by performing finite tests of randomness inspired by algorithmic information theory.
We deal with randomness-quantifiers and concentrate on their ability do discern the hallmark of chaos in time-series used in connection with pseudo random number generators (PRNG). Workers in the field are motivated to use chaotic maps for generating PRNGs because of the simplicity of their implementation. Although there exist very efficient general-purpose benchmarks for testing PRNGs, we feel that the analysis provided here sheds additional didactic light on the importance of the main statistical characteristics of a chaotic map, namely, i) its invariant measure and ii) the mixing constant. This is of help in answering two questions that arise in applications, that is, (1) which is the best PRNG among the available ones? and (2) If a given PRNG turns out not to be good enough and a randomization procedure must still be applied to it, which is the best applicable randomization procedure?. Our answer provides a comparative analysis of several quantifiers advanced in the extant literature.
Quantum random number generators (QRNG) based on continuous variable (CV) quantum fluctuations offer great potential for their advantages in measurement bandwidth, stability and integrability. More importantly, it provides an efficient and extensible path for significant promotion of QRNG generation rate. During this process, real-time randomness extraction using information theoretically secure randomness extractors is vital, because it plays critical role in the limit of throughput rate and implementation cost of QRNGs. In this work, we investigate parallel and real-time realization of several Toeplitz-hashing extractors within one field-programmable gate array (FPGA) for parallel QRNG. Elaborate layout of Toeplitz matrixes and efficient utilization of hardware computing resource in the FPGA are emphatically studied. Logic source occupation for different scale and quantity of Toeplitz matrices is analyzed and two-layer parallel pipeline algorithm is delicately designed to fully exploit the parallel algorithm advantage and hardware source of the FPGA. This work finally achieves a real-time post-processing rate of QRNG above 8 Gbps. Matching up with integrated circuit for parallel extraction of multiple quantum sideband modes of vacuum state, our demonstration shows an important step towards chip-based parallel QRNG, which could effectively improve the practicality of CV QRNGs, including device trusted, device-independent, and semi-device-independent schemes.
A quantum random number generator (QRNG) as a genuine source of randomness is essential in many applications, such as number simulation and cryptography. Recently, a source-independent quantum random number generator (SI-QRNG), which can generate secure random numbers with untrusted sources, has been realized. However, the measurement loopholes of the trusted but imperfect devices used in SI-QRNGs have not yet been fully explored, which will cause security problems, especially in high-speed systems. Here, we point out and evaluate the security loopholes of practical imperfect measurement devices in SI-QRNGs. We also provide corresponding countermeasures to prevent these information leakages by recalculating the conditional minimum entropy and adding a monitor. Furthermore, by taking into account the finite-size effect,we show that the influence of the afterpulse can exceed that of the finite-size effect with the large number of sampled rounds. Our protocol is simple and effective, and it promotes the security of SI-QRNG in practice as well as the compatibility with high-speed measurement devices, thus paving the way for constructing ultrafast and security-certified commercial SI-QRNG systems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
