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

arXiv:1709.03687 · Physical Review Letters

Realization of a Quantum Random Generator Certified with the Kochen-Specker Theorem

Anatoly Kulikov, Markus Jerger, Anton Potočnik, Andreas J. Wallraff, Arkady Fedorov

Published Dec 11, 2017• 36 citations
arXivHTMLPDF

Abstract

Random numbers are required for a variety of applications from secure communications to Monte Carlo simulation. Yet randomness is an asymptotic property, and no output string generated by a physical device can be strictly proven to be random. We report an experimental realization of a quantum random number generator (QRNG) with randomness certified by quantum contextuality and the Kochen-Specker theorem. The certification is not performed in a device-independent way but through a rigorous theoretical proof of each outcome being value indefinite even in the presence of experimental imperfections. The analysis of the generated data confirms the incomputable nature of our QRNG.

DOI
10.1103/physrevlett.119.240501

Related papers

A quantum random number generator certified by value indefiniteness

Alastair A. Abbott, Cristian S. Calude, Karl Svozil

In this paper we propose a quantum random number generator (QRNG) that uses an entangled photon pair in a Bell singlet state and is certified explicitly by value indefiniteness. While ‘true randomness’ is a mathematical impossibility, the certification by value indefiniteness ensures that the quantum random bits are incomputable in the strongest sense. This is the first QRNG setup in which a physical principle (Kochen–Specker value indefiniteness) guarantees that no single quantum bit that is produced can be classically computed (reproduced and validated), which is the mathematical form of bitwise physical unpredictability. We discuss the effects of various experimental imperfections in detail: in particular, those related to detector efficiencies, context alignment and temporal correlations between bits. The analysis is very relevant for the construction of any QRNG based on beam-splitters. By measuring the two entangled photons in maximally misaligned contexts and using the fact that two bitstrings, rather than just one, are obtained, more efficient and robust unbiasing techniques can be applied. We propose a robust and efficient procedure based onXORing the bitstrings together – essentially using one as a one-time-pad for the other – to extract random bits in the presence of experimental imperfections, as well as a more efficient modification of the von Neumann procedure for the same task. We also discuss some open problems.

arXiv:1012.1960•Mathematical Structures in Computer Science•Mar 28, 2014•23 citations

Algorithmic Randomness and Quantum Random Number Generation

José Manuel Agüero Trejo

In this Thesis, we develop the only class of QRNGs, to date, that has been proved to be better than any PRNG. This type of QRNG is based on a located form of the Kochen-Specker Theorem. This certification is unique because i) the assumptions used have been experimentally validated, ii) the robustness of measurements was proved theoretically, iii) the quality of quantum random digits generated with this class of QRNG was experimentally shown to be better than that of the best PRNGs, demonstrating for the first time the strong effects of incomputability on the outputs of a quantum random number generator. Finally, we propose a method using high-quality randomness for inverting a class of one-way functions in a pre-given time.

•Jan 1, 2024•0 citations

Kochen-Specker Theorem Revisited and Strong Incomputability of Quantum Randomness

Alastair A. Abbott, Cristian S. Calude, Jonathan Conder +1 more

We present a stronger variant of the Kochen-Specker theorem in which some quantum observables are identified to be provably value indefinite. This result is utilised for the construction and certification of a dichotomic quantum random number generator operating in a three-dimensional Hilbert space. Key words: Kochen-Specker theorem, value indefiniteness, quantum random generator

•Jul 9, 2012•1 citation

Experimentally probing the algorithmic randomness and incomputability of quantum randomness

Alastair A. Abbott, Cristian S Calude, Michael J Dinneen +1 more

Abstract 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.

arXiv:1806.08762•Physica Scripta•Nov 23, 2018•28 citations

Randomness Expansion Secured by Quantum Contextuality

Mark Um, Qi Zhao, Junhua Zhang +6 more

The output randomness from a random number generator can be certified by observing the violation of quantum contextuality inequalities based on the Kochen-Specker theorem. Contextuality can be tested in a single quantum system, which significantly simplifies the experimental requirements to observe the violation comparing to the ones based on nonlocality tests. However, it is not yet resolved as to how to ensure compatibilities for sequential measurements that is required in contextuality tests. Here, we employ a modified Klyachko-Can-Binicio\ifmmode \breve{g}\else \u{g}\fi{}lu-Shumovsky contextuality inequality, which can ease the strict compatibility requirement on measurements. On a trapped single ${}^{138}{\mathrm{Ba}}^{+}$ ion system, we experimentally demonstrate violation of the contextuality inequality and realize quantum random number expansion by closing detection loopholes. We perform $1.29\ifmmode\times\else\texttimes\fi{}{10}^{8}$ trials of experiments and extract a randomness of $5.28\ifmmode\times\else\texttimes\fi{}{10}^{5}$ bits with a speed of $270\phantom{\rule{0.2em}{0ex}}\mathrm{bits}\phantom{\rule{0.2em}{0ex}}{\mathrm{s}}^{\ensuremath{-}1}$. Our demonstration paves the way for practical high-speed spot-checking quantum random number expansion and other secure information processing applications.

arXiv:1902.00244•Physical Review Applied•Mar 31, 2020•21 citations

Experimental Certification of Random Numbers via Quantum Contextuality

Mark Um, Xiang Zhang, Junhua Zhang +5 more

The intrinsic unpredictability of measurements in quantum mechanics can be used to produce genuine randomness. Here, we demonstrate a random number generator where the randomness is certified by quantum contextuality in connection with the Kochen-Specker theorem. In particular, we generate random numbers from measurements on a single trapped ion with three internal levels, and certify the generated randomness by showing a bound on the minimum entropy through observation of violation of the Klyachko-Can-Binicioglu-Shumovsky (KCBS) inequality. Concerning the test of the KCBS inequality, we close the detection efficiency loophole for the first time and make it relatively immune to the compatibility loophole. In our experiment, we generate 1 × 10(5) random numbers that are guaranteed to have 5.2 × 10(4) bits of minimum entropy with a 99% confidence level.

Scientific Reports•Apr 9, 2013•70 citations
Random numbers are required for a variety of applications from secure communications to Monte Carlo simulation. Yet randomness is an asymptotic property, and no output string generated by a physical device can be strictly proven to be random. We report an experimental realization of a quantum random number generator (QRNG) with randomness certified by quantum contextuality and the Kochen-Specker theorem. The certification is not performed in a device-independent way but through a rigorous theoretical proof of each outcome being value indefinite even in the presence of experimental imperfections. The analysis of the generated data confirms the incomputable nature of our QRNG.
In this paper we propose a quantum random number generator (QRNG) that uses an entangled photon pair in a Bell singlet state and is certified explicitly by value indefiniteness. While ‘true randomness’ is a mathematical impossibility, the certification by value indefiniteness ensures that the quantum random bits are incomputable in the strongest sense. This is the first QRNG setup in which a physical principle (Kochen–Specker value indefiniteness) guarantees that no single quantum bit that is produced can be classically computed (reproduced and validated), which is the mathematical form of bitwise physical unpredictability. We discuss the effects of various experimental imperfections in detail: in particular, those related to detector efficiencies, context alignment and temporal correlations between bits. The analysis is very relevant for the construction of any QRNG based on beam-splitters. By measuring the two entangled photons in maximally misaligned contexts and using the fact that two bitstrings, rather than just one, are obtained, more efficient and robust unbiasing techniques can be applied. We propose a robust and efficient procedure based onXORing the bitstrings together – essentially using one as a one-time-pad for the other – to extract random bits in the presence of experimental imperfections, as well as a more efficient modification of the von Neumann procedure for the same task. We also discuss some open problems.
In this Thesis, we develop the only class of QRNGs, to date, that has been proved to be better than any PRNG. This type of QRNG is based on a located form of the Kochen-Specker Theorem. This certification is unique because i) the assumptions used have been experimentally validated, ii) the robustness of measurements was proved theoretically, iii) the quality of quantum random digits generated with this class of QRNG was experimentally shown to be better than that of the best PRNGs, demonstrating for the first time the strong effects of incomputability on the outputs of a quantum random number generator. Finally, we propose a method using high-quality randomness for inverting a class of one-way functions in a pre-given time.
Abstract 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.
The output randomness from a random number generator can be certified by observing the violation of quantum contextuality inequalities based on the Kochen-Specker theorem. Contextuality can be tested in a single quantum system, which significantly simplifies the experimental requirements to observe the violation comparing to the ones based on nonlocality tests. However, it is not yet resolved as to how to ensure compatibilities for sequential measurements that is required in contextuality tests. Here, we employ a modified Klyachko-Can-Binicio\ifmmode \breve{g}\else \u{g}\fi{}lu-Shumovsky contextuality inequality, which can ease the strict compatibility requirement on measurements. On a trapped single 138Ba+{}^{138}{\mathrm{Ba}}^{+}138Ba+ ion system, we experimentally demonstrate violation of the contextuality inequality and realize quantum random number expansion by closing detection loopholes. We perform $1.29\ifmmode\times\else\texttimes\fi{}{10}^{8}$ trials of experiments and extract a randomness of $5.28\ifmmode\times\else\texttimes\fi{}{10}^{5}$ bits with a speed of $270\phantom{\rule{0.2em}{0ex}}\mathrm{bits}\phantom{\rule{0.2em}{0ex}}{\mathrm{s}}^{\ensuremath{-}1}$. Our demonstration paves the way for practical high-speed spot-checking quantum random number expansion and other secure information processing applications.
The intrinsic unpredictability of measurements in quantum mechanics can be used to produce genuine randomness. Here, we demonstrate a random number generator where the randomness is certified by quantum contextuality in connection with the Kochen-Specker theorem. In particular, we generate random numbers from measurements on a single trapped ion with three internal levels, and certify the generated randomness by showing a bound on the minimum entropy through observation of violation of the Klyachko-Can-Binicioglu-Shumovsky (KCBS) inequality. Concerning the test of the KCBS inequality, we close the detection efficiency loophole for the first time and make it relatively immune to the compatibility loophole. In our experiment, we generate 1 × 10(5) random numbers that are guaranteed to have 5.2 × 10(4) bits of minimum entropy with a 99% confidence level.