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:1407.0604 · Physical Review Letters

Algorithmic Pseudorandomness in Quantum Setups

Ariel Bendersky, Gonzalo de la Torre, Gabriel Senno, Santiago Daniel Figueira, Antonio Acín

Published Jun 7, 2016• 32 citations
arXivHTMLPDF

Abstract

Many experimental setups in quantum physics use pseudorandomness in places where the theory requires randomness. In this Letter we show that the use of pseudorandomness instead of proper randomness in quantum setups has potentially observable consequences. First, we present a new loophole for Bell-like experiments: if some of the parties choose their measurements pseudorandomly, then the computational resources of the local model have to be limited in order to have a proper observation of nonlocality. Second, we show that no amount of pseudorandomness is enough to produce a mixed state by computably choosing pure states from some basis.

DOI
10.1103/physrevlett.116.230402

Related papers

Near-Term Pseudorandom and Pseudoresource Quantum States

Andrew Tanggara, Mile Gu, Kishor Bharti

A pseudorandom quantum state (PRS) is an ensemble of quantum states indistinguishable from Haar-random states to observers with efficient quantum computers. It allows one to substitute the costly Haar-random state with efficiently preparable PRS as a resource for cryptographic protocols, while also finding applications in quantum learning theory, black hole physics, many-body thermalization, quantum foundations, and quantum chaos. All existing constructions of PRS equate the notion of efficiency to quantum computers which runtime is bounded by a polynomial in its input size. In this work, we relax the notion of efficiency for PRS with respect to observers with near-term quantum computers implementing algorithms with runtime that scales slower than polynomial-time. We introduce the $\mathbf{T}$-PRS which is indistinguishable to quantum algorithms with runtime $\mathbf{T}(n)$ that grows slower than polynomials in the input size $n$. We give a set of reasonable conditions that a $\mathbf{T}$-PRS must satisfy and give two constructions by using quantum-secure pseudorandom functions and pseudorandom functions. For $\mathbf{T}(n)$ being linearithmic, linear, polylogarithmic, and logarithmic function, we characterize the amount of quantum resources a $\mathbf{T}$-PRS must possess, particularly on its coherence, entanglement, and magic. Our quantum resource characterization applies generally to any two state ensembles that are indistinguishable to observers with computational power $\mathbf{T}(n)$, giving a general necessary condition of whether a low-resource ensemble can mimic a high-resource ensemble, forming a $\mathbf{T}$-pseudoresource pair. We demonstate how the necessary amount of resource decreases as the observer's computational power is more restricted, giving a $\mathbf{T}$-pseudoresource pair with larger resource gap for more computationally limited observers.

arXiv:2504.17650•Apr 24, 2025•3 citations

Random 'choices' and the locality loophole

Stefano Pironio

It has been claimed that to close the locality loophole in a Bell experiment, random numbers of quantum origin should be used for selecting the measurement settings. This is how it has been implemented in all recent Bell experiment addressing this loophole. I point out in this note that quantum random number generators are unnecessary for such experiments and that a Bell experiment with a pseudo-random (but otherwise completely deterministic) mechanism for selecting the measurement settings, such as taking a hash function of the latest million tweets with the hashtag #quantum, would be as convincing, or even more, than one using quantum random number generators.

arXiv:1510.00248•Oct 1, 2015•44 citations

Permutation asymmetry unlocks emergent advantage in randomized Bell tests

Wieslaw Laskowski, Tamas Vertesi, Jan Wojcik

All maximally entangled two-qubit states violate local realism with the same probability under uniformly random projective measurements, yet they need not behave identically in randomized Bell tests. We show that when measurement settings are exchanged between the parties in sequential Bell experiments, permutation symmetry of the shared state determines the statistical relation between the two realizations. Permutationally invariant states yield identical nonlocality outcomes in both experiments, whereas asymmetric states can violate local realism in one realization but not in the other. This distinction leads to two operational consequences. First, it enables the detection of correlations between the measurement choices of Alice and Bob through the joint violation statistics. Second, in Bell tests with finite measurement pools, asymmetric maximally entangled states can significantly increase the probability of observing nonlocality without requiring additional resources. Our results identify permutation asymmetry as a useful feature in randomized Bell experiments and highlight a new role of symmetry in quantum nonlocality.

quant-pharXiv:2606.26242•Jun 26, 2026•0 citations

Quantifying nonlocality as a resource for device-independent quantum key distribution

S. Camalet

We introduce, for any bipartite Bell scenario, a measure that quantifies both the amount of nonlocality and the efficiency in device-independent quantum key distribution of a set of measurement outcome probabilities. It is a proper measure of nonlocality as it vanishes when this set is Bell local and does not increase under the allowed transformations of the nonlocality resource theory. This device-independent key rate $R$ is defined by optimizing over a class of protocols, to generate the raw keys, in which each legitimate party does not use just one preselected measurement but randomly chooses at each round one among all the measurements at its disposal. A common and secret key can certainly be established when $R$ is positive but not when it is zero. For any continuous proper measure of nonlocality $N$, $R$ is tightly lower bounded by a nondecreasing function of $N$ that vanishes when $N$ does. There can thus be a threshold value for the amount of nonlocality as quantified by $N$ above which a secret key is surely achievable. A readily computable measure with such a threshold exists for two two-outcome measurements per legitimate party.

arXiv:1912.01886•Physical Review A•Jul 20, 2020•6 citations

Efficient Quantum Pseudorandomness with Nearly Time-Independent Hamiltonian Dynamics

Yoshifumi Nakata, Christoph Hirche, Masato Koashi +1 more

Methods for generating quantum pseudorandomness are essential to understanding randomness in many quantum phenomena, but have not been fully explored. A new analysis shows that quantum pseudorandomness can appear spontaneously in certain many-body systems, leading to a prescription for developing quantum circuits that generate pseudorandomness.

arXiv:1609.07021•Physical Review X•Apr 10, 2017•108 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
Many experimental setups in quantum physics use pseudorandomness in places where the theory requires randomness. In this Letter we show that the use of pseudorandomness instead of proper randomness in quantum setups has potentially observable consequences. First, we present a new loophole for Bell-like experiments: if some of the parties choose their measurements pseudorandomly, then the computational resources of the local model have to be limited in order to have a proper observation of nonlocality. Second, we show that no amount of pseudorandomness is enough to produce a mixed state by computably choosing pure states from some basis.
A pseudorandom quantum state (PRS) is an ensemble of quantum states indistinguishable from Haar-random states to observers with efficient quantum computers. It allows one to substitute the costly Haar-random state with efficiently preparable PRS as a resource for cryptographic protocols, while also finding applications in quantum learning theory, black hole physics, many-body thermalization, quantum foundations, and quantum chaos. All existing constructions of PRS equate the notion of efficiency to quantum computers which runtime is bounded by a polynomial in its input size. In this work, we relax the notion of efficiency for PRS with respect to observers with near-term quantum computers implementing algorithms with runtime that scales slower than polynomial-time. We introduce the T\mathbf{T}T-PRS which is indistinguishable to quantum algorithms with runtime T(n)\mathbf{T}(n)T(n) that grows slower than polynomials in the input size nnn. We give a set of reasonable conditions that a T\mathbf{T}T-PRS must satisfy and give two constructions by using quantum-secure pseudorandom functions and pseudorandom functions. For T(n)\mathbf{T}(n)T(n) being linearithmic, linear, polylogarithmic, and logarithmic function, we characterize the amount of quantum resources a T\mathbf{T}T-PRS must possess, particularly on its coherence, entanglement, and magic. Our quantum resource characterization applies generally to any two state ensembles that are indistinguishable to observers with computational power T(n)\mathbf{T}(n)T(n), giving a general necessary condition of whether a low-resource ensemble can mimic a high-resource ensemble, forming a T\mathbf{T}T-pseudoresource pair. We demonstate how the necessary amount of resource decreases as the observer's computational power is more restricted, giving a T\mathbf{T}T-pseudoresource pair with larger resource gap for more computationally limited observers.
It has been claimed that to close the locality loophole in a Bell experiment, random numbers of quantum origin should be used for selecting the measurement settings. This is how it has been implemented in all recent Bell experiment addressing this loophole. I point out in this note that quantum random number generators are unnecessary for such experiments and that a Bell experiment with a pseudo-random (but otherwise completely deterministic) mechanism for selecting the measurement settings, such as taking a hash function of the latest million tweets with the hashtag #quantum, would be as convincing, or even more, than one using quantum random number generators.
All maximally entangled two-qubit states violate local realism with the same probability under uniformly random projective measurements, yet they need not behave identically in randomized Bell tests. We show that when measurement settings are exchanged between the parties in sequential Bell experiments, permutation symmetry of the shared state determines the statistical relation between the two realizations. Permutationally invariant states yield identical nonlocality outcomes in both experiments, whereas asymmetric states can violate local realism in one realization but not in the other. This distinction leads to two operational consequences. First, it enables the detection of correlations between the measurement choices of Alice and Bob through the joint violation statistics. Second, in Bell tests with finite measurement pools, asymmetric maximally entangled states can significantly increase the probability of observing nonlocality without requiring additional resources. Our results identify permutation asymmetry as a useful feature in randomized Bell experiments and highlight a new role of symmetry in quantum nonlocality.
We introduce, for any bipartite Bell scenario, a measure that quantifies both the amount of nonlocality and the efficiency in device-independent quantum key distribution of a set of measurement outcome probabilities. It is a proper measure of nonlocality as it vanishes when this set is Bell local and does not increase under the allowed transformations of the nonlocality resource theory. This device-independent key rate RRR is defined by optimizing over a class of protocols, to generate the raw keys, in which each legitimate party does not use just one preselected measurement but randomly chooses at each round one among all the measurements at its disposal. A common and secret key can certainly be established when RRR is positive but not when it is zero. For any continuous proper measure of nonlocality NNN, RRR is tightly lower bounded by a nondecreasing function of NNN that vanishes when NNN does. There can thus be a threshold value for the amount of nonlocality as quantified by NNN above which a secret key is surely achievable. A readily computable measure with such a threshold exists for two two-outcome measurements per legitimate 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.