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:1708.04338 · Physical Review A

Local randomness: Examples and application

Honghao Fu, Carl A. Miller

Published Mar 19, 2018• 20 citations
arXivHTMLPDF

Abstract

When two players achieve a superclassical score at a nonlocal game, their outputs must contain intrinsic randomness. This fact has many useful implications for quantum cryptography. Recently it has been observed [C. Miller and Y. Shi, Quantum Inf. Computat. 17, 0595 (2017)] that such scores also imply the existence of local randomness---that is, randomness known to one player but not to the other. This has potential implications for cryptographic tasks between two cooperating but mistrustful players. In the current paper we bring this notion toward practical realization, by offering near-optimal bounds on local randomness for the CHSH game, and also proving the security of a cryptographic application of local randomness (single-bit certified deletion).

DOI
10.1103/physreva.97.032324

Related papers

Randomness in nonlocal games between mistrustful players

Carl A. Miller, Yaoyun Shi

If two quantum players at a nonlocal game G achieve a superclassical score, then their measurement outcomes must be at least partially random from the perspective of any third player. This is the basis for device-independent quantum cryptography. In this paper we address a related question: does a superclassical score at G guarantee that one player has created randomness from the perspective of the other player? We show that for complete-support games, the answer is yes: even if the second player is given the first player’s input at the conclusion of the game, he cannot perfectly recover her output. Thus some amount of local randomness (i.e., randomness possessed by only one player) is always obtained when randomness is certified from nonlocal games with quantum strategies. This is in contrast to non-signaling game strategies, which may produce global randomness without any local randomness. We discuss potential implications for cryptographic protocols between mistrustful parties.

arXiv:1706.04984•Quantum Information and Computation•May 1, 2017•7 citations

Certified randomness between mistrustful players

Carl A. Miller, Yaoyun Shi

It is known that if two players achieve a superclassical score at a nonlocal game $G$, then their outputs are certifiably random - that is, regardless of the strategy used by the players, a third party will not be able to perfectly predict their outputs (even if he were given their inputs). We prove that for any complete-support game $G$, there is an explicit nonzero function $F_G$ such that if Alice and Bob achieve a superclassical score of $s$ at $G$, then Bob has a probability of at most $1 - F_G ( s )$ of correctly guessing Alice's output after the game is played. Our result implies that certifying global randomness through such games must necessarily introduce local randomness.

arXiv:1610.05140•Oct 17, 2016•0 citations

No Bound Randomness in Quantum Nonlocality

Ravishankar Ramanathan, Yuan Liu, Y. M. Wu +1 more

Recently it has been found that there exist maximally nonlocal quantum correlations that fail to certify randomness for any fixed input pair, rendering them useless for device-independent spot-checking randomness expansion schemes. Here we show that conversely, in DI randomness amplification protocols where all input pairs are used for randomness generation, any amount of quantum nonlocality is sufficient to certify randomness. This shows that no bound randomness exists in quantum nonlocality - any quantum nonlocal behavior is useful in a DI randomness generation task with appropriate modification of protocol structure. Secondly, we show that in contrast to the hitherto considered fixed-input guessing probability, the average guessing probability over all inputs is a faithful and monotonic measure of nonlocality. We use the average guessing probability to show that in contrast to findings in PRL 134, 090201, the detection efficiency threshold for randomness generation is never lower than that for nonlocality detection. Finally, we analytically compute the average guessing probability by a quantum adversary of a single player's measurement outputs in a standard CHSH Bell test, and use it to demonstrate an improvement in the generation rate in state-of-art amplification protocols.

arXiv:2509.08623•Sep 10, 2025•0 citations

Certifying the absence of quantum nonlocality

Carl A. Miller, Yaoyun Shi

Quantum nonlocality is an inherently non-classical feature of quantum mechanics and manifests itself through violation of Bell inequalities for nonlocal games. We show that in a fairly general setting, a simple extension of a nonlocal game can certify instead the absence of quantum nonlocality. Through contraposition, our result implies that a super-classical performance for such a game ensures that a player's output is unpredictable to the other player. Previously such output unpredictability was known with respect to a third party.

arXiv:1608.01011•Aug 2, 2016•0 citations

More Than One-bit Quantum Randomness Certification and Expansion

Amélie Piveteau, Alban Seguinard, Marcus Grünfeld +4 more

One of the striking properties of quantum mechanics is the occurrence of the Bell-type non-locality. They are a fundamental feature of the theory that allows two parties that share an entangled quantum system to observe correlations stronger than possible in classical physics. In addition to their theoretical significance, non-local correlations have practical applications, such as device-independent randomness generation, providing private unpredictable numbers even when obtained using devices delivered by an untrusted vendor. Thus, determining the quantity of certifiable randomness that can be produced using a specific set of non-local correlations is of significant interest. First, we present an experimental realization of recent Bell-type operators designed to provide private random numbers that are secure against adversaries with quantum resources. We use semi-definite programming to give lower bounds on the generated randomness in terms of both min-entropy and von Neumann entropy in a device-independent scenario. Our results demonstrate the first experiment that certifies nearly two bits of randomness from binary measurements of two parties [1], [2]. Apart from single-round certification, we provide an analysis of finite-key protocol for quantum randomness expansion using the Entropy Accumulation Theorem. Second, we present an efficient and practical method for certifying quantum randomness using generalized measurements. Indeed, we have derived a method for self-testing the presence of POVMs. We present the certification of more than one bit of min-entropy from a single POVM on one of the qubits of an entangled state using a variant of the elegant Bell inequality. We also obtain more than one bit of randomness in a prepare and measure scenario of a similar structure with a POVM on a single qubit [3]. We provide numerical simulations to demonstrate the effectiveness of our randomness certification and expansion.

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)•Jun 23, 2025•0 citations

Quantum Nonlocality and Device-Independent Randomness Robust to Relaxations of Bell Assumptions

Ravishankar Ramanathan, Yuan Liu

The question of certifying quantum nonlocality under a relaxation of the assumptions in the Bell theorem has gained traction, with potential for device-independent applications under weak seeds and cross-talk. Recently, it was shown that quantum nonlocality can be certified even under a simultaneous arbitrary (but not full) relaxation of the assumptions of Measurement Independence (MI) and Parameter Independence (PI), using states of local dimension $d = poly((1-ε)^{-1})$ for an $ε\in [0,1)$-relaxation. Here, we derive three results strengthening the state-of-art. Firstly, we show that states of constant local dimension $d$ are already sufficient to certify quantum nonlocality under arbitrary MI and PI relaxation, albeit in a non-robust manner. Secondly, and as a theoretical paradigm to derive the above, we introduce the notion of \textit{measurement-dependent parameter-dependent locality} as the set of input-output behaviors under simultaneous relaxations of measurement and parameter independence. We provide a rigorous characterisation of the vertices of the polytope of joint input-output behaviors that obey a $μ$-relaxation of MI and $ε$-relaxation of PI. We highlight a relation between nonlocality certification under PI relaxation and that under detection inefficiencies by pointing out alternative extremal correlations to the Eberhard correlations that also allow to achieve detection efficiency of $η= 2/3$ in the two-input scenario. Finally, we study the implication of the relaxed assumptions for device-independent randomness certification. We analytically derive the quantum guessing probability for one player's outcomes in the CHSH Bell test, as a function of the noise in the test as well as of a leakage of an average amount of $I(X:B) < 1$ bits of input information per measurement round.

quant-pharXiv:2512.18513•Dec 23, 2025•0 citations
When two players achieve a superclassical score at a nonlocal game, their outputs must contain intrinsic randomness. This fact has many useful implications for quantum cryptography. Recently it has been observed [C. Miller and Y. Shi, Quantum Inf. Computat. 17, 0595 (2017)] that such scores also imply the existence of local randomness---that is, randomness known to one player but not to the other. This has potential implications for cryptographic tasks between two cooperating but mistrustful players. In the current paper we bring this notion toward practical realization, by offering near-optimal bounds on local randomness for the CHSH game, and also proving the security of a cryptographic application of local randomness (single-bit certified deletion).
If two quantum players at a nonlocal game G achieve a superclassical score, then their measurement outcomes must be at least partially random from the perspective of any third player. This is the basis for device-independent quantum cryptography. In this paper we address a related question: does a superclassical score at G guarantee that one player has created randomness from the perspective of the other player? We show that for complete-support games, the answer is yes: even if the second player is given the first player’s input at the conclusion of the game, he cannot perfectly recover her output. Thus some amount of local randomness (i.e., randomness possessed by only one player) is always obtained when randomness is certified from nonlocal games with quantum strategies. This is in contrast to non-signaling game strategies, which may produce global randomness without any local randomness. We discuss potential implications for cryptographic protocols between mistrustful parties.
It is known that if two players achieve a superclassical score at a nonlocal game GGG, then their outputs are certifiably random - that is, regardless of the strategy used by the players, a third party will not be able to perfectly predict their outputs (even if he were given their inputs). We prove that for any complete-support game GGG, there is an explicit nonzero function FGF_GFG​ such that if Alice and Bob achieve a superclassical score of sss at GGG, then Bob has a probability of at most 1−FG(s)1 - F_G ( s )1−FG​(s) of correctly guessing Alice's output after the game is played. Our result implies that certifying global randomness through such games must necessarily introduce local randomness.
Recently it has been found that there exist maximally nonlocal quantum correlations that fail to certify randomness for any fixed input pair, rendering them useless for device-independent spot-checking randomness expansion schemes. Here we show that conversely, in DI randomness amplification protocols where all input pairs are used for randomness generation, any amount of quantum nonlocality is sufficient to certify randomness. This shows that no bound randomness exists in quantum nonlocality - any quantum nonlocal behavior is useful in a DI randomness generation task with appropriate modification of protocol structure. Secondly, we show that in contrast to the hitherto considered fixed-input guessing probability, the average guessing probability over all inputs is a faithful and monotonic measure of nonlocality. We use the average guessing probability to show that in contrast to findings in PRL 134, 090201, the detection efficiency threshold for randomness generation is never lower than that for nonlocality detection. Finally, we analytically compute the average guessing probability by a quantum adversary of a single player's measurement outputs in a standard CHSH Bell test, and use it to demonstrate an improvement in the generation rate in state-of-art amplification protocols.
Quantum nonlocality is an inherently non-classical feature of quantum mechanics and manifests itself through violation of Bell inequalities for nonlocal games. We show that in a fairly general setting, a simple extension of a nonlocal game can certify instead the absence of quantum nonlocality. Through contraposition, our result implies that a super-classical performance for such a game ensures that a player's output is unpredictable to the other player. Previously such output unpredictability was known with respect to a third party.
One of the striking properties of quantum mechanics is the occurrence of the Bell-type non-locality. They are a fundamental feature of the theory that allows two parties that share an entangled quantum system to observe correlations stronger than possible in classical physics. In addition to their theoretical significance, non-local correlations have practical applications, such as device-independent randomness generation, providing private unpredictable numbers even when obtained using devices delivered by an untrusted vendor. Thus, determining the quantity of certifiable randomness that can be produced using a specific set of non-local correlations is of significant interest. First, we present an experimental realization of recent Bell-type operators designed to provide private random numbers that are secure against adversaries with quantum resources. We use semi-definite programming to give lower bounds on the generated randomness in terms of both min-entropy and von Neumann entropy in a device-independent scenario. Our results demonstrate the first experiment that certifies nearly two bits of randomness from binary measurements of two parties [1], [2]. Apart from single-round certification, we provide an analysis of finite-key protocol for quantum randomness expansion using the Entropy Accumulation Theorem. Second, we present an efficient and practical method for certifying quantum randomness using generalized measurements. Indeed, we have derived a method for self-testing the presence of POVMs. We present the certification of more than one bit of min-entropy from a single POVM on one of the qubits of an entangled state using a variant of the elegant Bell inequality. We also obtain more than one bit of randomness in a prepare and measure scenario of a similar structure with a POVM on a single qubit [3]. We provide numerical simulations to demonstrate the effectiveness of our randomness certification and expansion.
The question of certifying quantum nonlocality under a relaxation of the assumptions in the Bell theorem has gained traction, with potential for device-independent applications under weak seeds and cross-talk. Recently, it was shown that quantum nonlocality can be certified even under a simultaneous arbitrary (but not full) relaxation of the assumptions of Measurement Independence (MI) and Parameter Independence (PI), using states of local dimension d=poly((1−ε)−1)d = poly((1-ε)^{-1})d=poly((1−ε)−1) for an ε∈[0,1)ε\in [0,1)ε∈[0,1)-relaxation. Here, we derive three results strengthening the state-of-art. Firstly, we show that states of constant local dimension ddd are already sufficient to certify quantum nonlocality under arbitrary MI and PI relaxation, albeit in a non-robust manner. Secondly, and as a theoretical paradigm to derive the above, we introduce the notion of \textit{measurement-dependent parameter-dependent locality} as the set of input-output behaviors under simultaneous relaxations of measurement and parameter independence. We provide a rigorous characterisation of the vertices of the polytope of joint input-output behaviors that obey a μμμ-relaxation of MI and εεε-relaxation of PI. We highlight a relation between nonlocality certification under PI relaxation and that under detection inefficiencies by pointing out alternative extremal correlations to the Eberhard correlations that also allow to achieve detection efficiency of η=2/3η= 2/3η=2/3 in the two-input scenario. Finally, we study the implication of the relaxed assumptions for device-independent randomness certification. We analytically derive the quantum guessing probability for one player's outcomes in the CHSH Bell test, as a function of the noise in the test as well as of a leakage of an average amount of I(X:B)<1I(X:B) < 1I(X:B)<1 bits of input information per measurement round.