Guaranteed randomness

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.

Deborah J. Bennett, Stephen G. Gasiorowicz

Rob R. de Ruyter van Steveninck

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.

Roger Colbeck, Adrian Kent

Randomness is an important resource for many applications, from gambling to secure communication. However, guaranteeing that the output from a candidate random source could not have been predicted by an outside party is a challenging task, and many supposedly random sources used today provide no such guarantee. Quantum solutions to this problem exist, for example a device which internally sends a photon through a beam-splitter and observes on which side it emerges, but, presently, such solutions require the user to trust the internal workings of the device. Here we seek to go beyond this limitation by asking whether randomness can be generated using untrusted devices---even ones created by an adversarial agent---while providing a guarantee that no outside party (including the agent) can predict it. Since this is easily seen to be impossible unless the user has an initially private random string, the task we investigate here is private randomness expansion. We introduce a protocol for private randomness expansion with untrusted devices which is designed to take as input an initially private random string and produce as output a longer private random string. We point out that private randomness expansion protocols are generally vulnerable to attacks that can render the initial string partially insecure, even though that string is used only inside a secure laboratory; our protocol is designed to remove this previously unconsidered vulnerability by privacy amplification. We also discuss extensions of our protocol designed to generate an arbitrarily long random string from a finite initially private random string. The security of these protocols against the most general attacks is left as an open question.

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.