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:quant-ph/9806059 · Complexity

Quantum mechanics and algorithmic randomness

Ulvi Yurtsever

Published Sep 1, 2000• 13 citations
arXivHTMLPDF

Abstract

A long sequence of tosses of a classical coin produces an apparently random bit string, but classical randomness is an illusion: the algorithmic information content of a classically-generated bit string lies almost entirely in the description of initial conditions. This letter presents a simple argument that, by contrast, a sequence of bits produced by tossing a quantum coin is, almost certainly, genuinely (algorithmically) random. This result can be interpreted as a strengthening of Bell's no-hidden-variables theorem, and relies on causality and quantum entanglement in a manner similar to Bell's original argument.

DOI
10.1002/1099-0526(200009/10)6:1<27::aid-cplx1004>3.0.co;2-r

Related papers

Security of quantum bit-string generation

Jonathan Barrett, Serge Massar

We consider the cryptographic task of bit-string generation. This is a generalization of coin tossing in which two mistrustful parties wish to generate a string of random bits such that an honest party can be sure that the other cannot have biased the string too much. We consider a quantum protocol for this task, originally introduced in Phys. Rev. A 69, 022322 (2004), that is feasible with present day technology. We introduce security conditions based on the average bias of the bits and the Shannon entropy of the string. For each, we prove rigorous security bounds for this protocol in both noiseless and noisy conditions under the most general attacks allowed by quantum mechanics. Roughly speaking, in the absence of noise, a cheater can only bias significantly a vanishing fraction of the bits, whereas in the presence of noise, a cheater can bias a constant fraction, with this fraction depending quantitatively on the level of noise. We also discuss classical protocols for the same task, deriving upper bounds on how well a classical protocol can perform. This enables the determination of how much noise the quantum protocol can tolerate while still outperforming classical protocols. We raise several conjectures concerning both quantum and classical possibilities for large $n$ cryptography. An experiment corresponding to the scheme analyzed in this paper has been performed and is reported elsewhere.

arXiv:quant-ph/0408120•Physical Review A•Nov 11, 2004•15 citations

Considerations about the randomness of bit strings originated from sequences of integer numbers according to a simple quantum computer model

Rubens Viana Ramos

This work uses a simple quantum computer model to discuss the randomness of bit strings originated from integer sequences. The considered quantum computer model has three elements: a processing unit responsible for a mathematical operation, an initial equally weighted superposition and a quantum state used as resource. The randomness depends on the last.

arXiv:1505.00741•Apr 30, 2015•0 citations

Provably Secure Experimental Quantum Bit-String Generation

L.-P. Lamoureux, Edouard Brainis, David Amans +2 more

Coin tossing is a cryptographic task in which two parties who do not trust each other aim to generate a common random bit. Using classical communication this is impossible, but nontrivial coin tossing is possible using quantum communication. Here we consider the case when the parties do not want to toss a single coin, but many. This is called bit-string generation. We report the experimental generation of strings of coins which are provably more random than achievable using classical communication. The experiment is based on the "plug and play" scheme developed for quantum cryptography, and therefore well suited for long distance quantum communication.

arXiv:quant-ph/0408121•Physical Review Letters•Feb 7, 2005•24 citations

Quantum coin tossing and bit-string generation in the presence of noise

Jonathan Barrett, Serge Massar

We discuss the security implications of noise for quantum coin tossing protocols. We find that if quantum error correction can be used, so that noise levels can be made arbitrarily small, then reasonable security conditions for coin tossing can be framed so that results from the noiseless case will continue to hold. If, however, error correction is not available (as is the case with present day technology), and significant noise is present, then tossing a single coin becomes problematic. In this case, we are led to consider random n-bit string generation in the presence of noise, rather than single-shot coin tossing. We introduce precise security criteria for n-bit string generation and describe an explicit protocol that could be implemented with present day technology. In general, a cheater can exploit noise in order to bias coins to their advantage. We derive explicit upper bounds on the average bias achievable by a cheater for given noise levels.

arXiv:quant-ph/0303182•Physical Review A•Feb 27, 2004•25 citations

The algorithmic randomness of quantum measurements

Shahbazi, Mohammad

This paper is a comment on the paper "Quantum Mechanics and Algorithmic Randomness" was written by Ulvi Yurtsever \cite{Yurtsever} and the briefly explanation of the algorithmic randomness of quantum measurements results. There are differences between the computability of probability sources, ( which means there is an algorithm that can define the way that random process or probability source generates the numbers ) and the algorithmic randomness of the sequences or strings which are produced by a source. We may have the source without a computable algorithm for that but it can produce compressible or incompressible strings. For example, so far there is no computable algorithm that can define the abstract meaning of randomness even the easiest one, Bernoulli probability distribution. Historically and philosophically there many scientist believe the existence of the algorithm for a random process is a contradiction because in their opinion, in the definition of a random variable, implicitly assumed that there is no reason for the happening of an event and we just know the probabilities. There is however no need to enter into this matter here. As in the paper mentioned, all the algorithms for simulating a random process try to pass the statistical tests and be close to the abstract meaning of it.

arXiv:1704.01573•Apr 5, 2017•0 citations

Algorithmic Randomness Generation via Quantum Measurement

Jincheng Zhang

The generation of high-quality random numbers is a cornerstone of numerous fields, including cryptography, simulation, and statistical modeling. Classical methods for random number generation often rely on deterministic algorithms that, despite their complexity, ultimately produce predictable sequences. This paper proposes a novel approach to random number generation that harnesses the unique properties of quantum mechanics, specifically quantum measurement. We argue that classical algorithms are fundamentally limited in their ability to produce true randomness. Our approach utilizes quantum measurement processes, projecting a qubit into a superposition state, to generate random numbers. The resulting sequences exhibit statistical properties superior to those attainable through classical methods, offering a potentially significant advancement in the field of randomness generation. We detail the theoretical underpinnings, outlining the core mechanism and highlighting the key advantages. This work establishes a framework for leveraging quantum phenomena to achieve truly random number generation. ---

•Aug 29, 2026•0 citations
A long sequence of tosses of a classical coin produces an apparently random bit string, but classical randomness is an illusion: the algorithmic information content of a classically-generated bit string lies almost entirely in the description of initial conditions. This letter presents a simple argument that, by contrast, a sequence of bits produced by tossing a quantum coin is, almost certainly, genuinely (algorithmically) random. This result can be interpreted as a strengthening of Bell's no-hidden-variables theorem, and relies on causality and quantum entanglement in a manner similar to Bell's original argument.
We consider the cryptographic task of bit-string generation. This is a generalization of coin tossing in which two mistrustful parties wish to generate a string of random bits such that an honest party can be sure that the other cannot have biased the string too much. We consider a quantum protocol for this task, originally introduced in Phys. Rev. A 69, 022322 (2004), that is feasible with present day technology. We introduce security conditions based on the average bias of the bits and the Shannon entropy of the string. For each, we prove rigorous security bounds for this protocol in both noiseless and noisy conditions under the most general attacks allowed by quantum mechanics. Roughly speaking, in the absence of noise, a cheater can only bias significantly a vanishing fraction of the bits, whereas in the presence of noise, a cheater can bias a constant fraction, with this fraction depending quantitatively on the level of noise. We also discuss classical protocols for the same task, deriving upper bounds on how well a classical protocol can perform. This enables the determination of how much noise the quantum protocol can tolerate while still outperforming classical protocols. We raise several conjectures concerning both quantum and classical possibilities for large nnn cryptography. An experiment corresponding to the scheme analyzed in this paper has been performed and is reported elsewhere.
Coin tossing is a cryptographic task in which two parties who do not trust each other aim to generate a common random bit. Using classical communication this is impossible, but nontrivial coin tossing is possible using quantum communication. Here we consider the case when the parties do not want to toss a single coin, but many. This is called bit-string generation. We report the experimental generation of strings of coins which are provably more random than achievable using classical communication. The experiment is based on the "plug and play" scheme developed for quantum cryptography, and therefore well suited for long distance quantum communication.
We discuss the security implications of noise for quantum coin tossing protocols. We find that if quantum error correction can be used, so that noise levels can be made arbitrarily small, then reasonable security conditions for coin tossing can be framed so that results from the noiseless case will continue to hold. If, however, error correction is not available (as is the case with present day technology), and significant noise is present, then tossing a single coin becomes problematic. In this case, we are led to consider random n-bit string generation in the presence of noise, rather than single-shot coin tossing. We introduce precise security criteria for n-bit string generation and describe an explicit protocol that could be implemented with present day technology. In general, a cheater can exploit noise in order to bias coins to their advantage. We derive explicit upper bounds on the average bias achievable by a cheater for given noise levels.
This paper is a comment on the paper "Quantum Mechanics and Algorithmic Randomness" was written by Ulvi Yurtsever \cite{Yurtsever} and the briefly explanation of the algorithmic randomness of quantum measurements results. There are differences between the computability of probability sources, ( which means there is an algorithm that can define the way that random process or probability source generates the numbers ) and the algorithmic randomness of the sequences or strings which are produced by a source. We may have the source without a computable algorithm for that but it can produce compressible or incompressible strings. For example, so far there is no computable algorithm that can define the abstract meaning of randomness even the easiest one, Bernoulli probability distribution. Historically and philosophically there many scientist believe the existence of the algorithm for a random process is a contradiction because in their opinion, in the definition of a random variable, implicitly assumed that there is no reason for the happening of an event and we just know the probabilities. There is however no need to enter into this matter here. As in the paper mentioned, all the algorithms for simulating a random process try to pass the statistical tests and be close to the abstract meaning of it.
The generation of high-quality random numbers is a cornerstone of numerous fields, including cryptography, simulation, and statistical modeling. Classical methods for random number generation often rely on deterministic algorithms that, despite their complexity, ultimately produce predictable sequences. This paper proposes a novel approach to random number generation that harnesses the unique properties of quantum mechanics, specifically quantum measurement. We argue that classical algorithms are fundamentally limited in their ability to produce true randomness. Our approach utilizes quantum measurement processes, projecting a qubit into a superposition state, to generate random numbers. The resulting sequences exhibit statistical properties superior to those attainable through classical methods, offering a potentially significant advancement in the field of randomness generation. We detail the theoretical underpinnings, outlining the core mechanism and highlighting the key advantages. This work establishes a framework for leveraging quantum phenomena to achieve truly random number generation. ---