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

Nature

Guaranteed randomness

Valerio Scarani

Published Apr 1, 2010• 8 citations
Publisher
DOI
10.1038/464988a

Related papers

Genuine Randomness vis-a-vis Nonlocality: Hardy and Hardy type Relations.

Souradeep Sasmal, Sayan Gangopadhyay, Ashutosh Rai +2 more

We explore the relationship between randomness and nonlocality based on arguments which demonstrate nonlocality without requiring Bell-type inequalities, such as using Hardy relations and its variant like Cabello-Liang (CL) relations. We first clarify the way these relations enable certification of Genuine Randomness (GR) based on the No-signalling principle. Subsequently, corresponding to a given amount of nonlocality, using the relevant quantifier of GR, we demonstrate the following results: (a) We show that in the 2-2-2 scenario, it is possible to achieve close to the theoretical maximum value of 2 bits amount of GR using CL relations. Importantly, this maximum value is achieved using pure non-maximally entangled states for the measurement settings entailing small amount of nonlocality. Thus, this illustrates quantitative incommensurability between maximum achievable certified randomness, nonlocality and entanglement in the same testable context. (b) We also obtain the device-independent guaranteed amount of GR based on Hardy and CL relations, taking into account the effect of varying preparation procedure which is necessary for ensuring the desired security in this case against adversarial guessing attack. This result is compared with that obtained earlier for the Bell-CHSH case. We find that the monotonicity between such guaranteed randomness and nonlocality persists for the Hardy/CL like for Bell-CHSH inequality, thereby showing commensurability between guaranteed randomness and nonlocality, in contrast to the case of maximum achievable randomness. The results of this combined study of maximum achievable as well as guaranteed amounts of GR, obtained for both fixed and varying preparation procedures, demonstrate that the nature of quantitative relationship between randomness and nonlocality is crucially dependent on which aspect (guaranteed/maximum amount) of GR is considered.

•Nov 25, 2020•1 citation

Randomness

Deborah J. Bennett, Stephen G. Gasiorowicz

Physics Today•Jan 1, 1999•4 citations

Randomness unbound

Rob R. de Ruyter van Steveninck

Physics Today•Jan 1, 2022•0 citations

Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad

Matthew B. Hastings

We consider classical and quantum algorithms which have a duality property: roughly, either the algorithm provides some nontrivial improvement over random or there exist many solutions which are significantly worse than random. This enables one to give guarantees that the algorithm will find such a nontrivial improvement: if few solutions exist which are much worse than random, then a nontrivial improvement is guaranteed. The quantum algorithm is based on a sudden quench of a Hamiltonian; while the algorithm is general, we analyze it in the specific context of MAX- K -LIN 2 , for both even and odd K . The classical algorithm is a ``dequantization of this algorithm", obtaining the same guarantee (indeed, some results which are only conjectured in the quantum case can be proven here); however, the quantum point of view helps in analyzing the performance of the classical algorithm and might in some cases perform better.

arXiv:1904.13339•Quantum•Nov 11, 2019•13 citations

Pretty good shadow tomography

Sabee Grewal, Angelos Pelecanos, Jack Spilecki +2 more

We give a shadow tomography algorithm that uses $O(\log(m) \log(m/δ) / \varepsilon^2)$ copies of the input state. Specifically, given a quantum state $ρ$ and observables $O_1,\ldots,O_m$, the algorithm outputs estimates of $\mathrm{tr}(O_iρ)$ for all $i\in[m]$ that are all accurate to within $\pm\varepsilon$, except with probability at most $δ$. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on $O(\log(m)/\varepsilon^2)$ copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining $\log(m)$ factor separating the complexity of the quantum problem from its classical counterpart.

quant-pharXiv:2610.06781•Oct 6, 2026•1 citation

Unpredictability and Randomness

Rade Vuckovac

The frontiers collection•Jan 1, 2021•0 citations
We explore the relationship between randomness and nonlocality based on arguments which demonstrate nonlocality without requiring Bell-type inequalities, such as using Hardy relations and its variant like Cabello-Liang (CL) relations. We first clarify the way these relations enable certification of Genuine Randomness (GR) based on the No-signalling principle. Subsequently, corresponding to a given amount of nonlocality, using the relevant quantifier of GR, we demonstrate the following results: (a) We show that in the 2-2-2 scenario, it is possible to achieve close to the theoretical maximum value of 2 bits amount of GR using CL relations. Importantly, this maximum value is achieved using pure non-maximally entangled states for the measurement settings entailing small amount of nonlocality. Thus, this illustrates quantitative incommensurability between maximum achievable certified randomness, nonlocality and entanglement in the same testable context. (b) We also obtain the device-independent guaranteed amount of GR based on Hardy and CL relations, taking into account the effect of varying preparation procedure which is necessary for ensuring the desired security in this case against adversarial guessing attack. This result is compared with that obtained earlier for the Bell-CHSH case. We find that the monotonicity between such guaranteed randomness and nonlocality persists for the Hardy/CL like for Bell-CHSH inequality, thereby showing commensurability between guaranteed randomness and nonlocality, in contrast to the case of maximum achievable randomness. The results of this combined study of maximum achievable as well as guaranteed amounts of GR, obtained for both fixed and varying preparation procedures, demonstrate that the nature of quantitative relationship between randomness and nonlocality is crucially dependent on which aspect (guaranteed/maximum amount) of GR is considered.
We consider classical and quantum algorithms which have a duality property: roughly, either the algorithm provides some nontrivial improvement over random or there exist many solutions which are significantly worse than random. This enables one to give guarantees that the algorithm will find such a nontrivial improvement: if few solutions exist which are much worse than random, then a nontrivial improvement is guaranteed. The quantum algorithm is based on a sudden quench of a Hamiltonian; while the algorithm is general, we analyze it in the specific context of MAX- K -LIN 2 , for both even and odd K . The classical algorithm is a ``dequantization of this algorithm", obtaining the same guarantee (indeed, some results which are only conjectured in the quantum case can be proven here); however, the quantum point of view helps in analyzing the performance of the classical algorithm and might in some cases perform better.
We give a shadow tomography algorithm that uses O(log⁡(m)log⁡(m/δ)/ε2)O(\log(m) \log(m/δ) / \varepsilon^2)O(log(m)log(m/δ)/ε2) copies of the input state. Specifically, given a quantum state ρρρ and observables O1,…,OmO_1,\ldots,O_mO1​,…,Om​, the algorithm outputs estimates of tr(Oiρ)\mathrm{tr}(O_iρ)tr(Oi​ρ) for all i∈[m]i\in[m]i∈[m] that are all accurate to within ±ε\pm\varepsilon±ε, except with probability at most δδδ. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on O(log⁡(m)/ε2)O(\log(m)/\varepsilon^2)O(log(m)/ε2) copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining log⁡(m)\log(m)log(m) factor separating the complexity of the quantum problem from its classical counterpart.