2010/04/09 by Cristian S. Calude, Michael J. Dinneen, Monica Dumitrescu +1 · 1 voice · 1 citation
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #cs.CC #quant-ph
paper · pdf · doi:10.1103/physreva.82.022102
published as Phys. Rev. A 82, 022102 (2010) [8 pages] · 23 pages, 5 figures, statistical analysis added, other sections greatly expanded
arxiv published 2010/04/09 · arxiv created 2010/06/15 · arxiv updated 2010/06/15 · openalex publication_date 2010/08/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.