Self-testing with untrusted random number generators

Imagine you are trying to verify that a magic trick is real, but you have a strict rule: you cannot trust the magician, and you cannot trust the person picking the cards.

In the world of quantum physics, this is called Self-Testing. It's a way to prove that a mysterious "black box" device is actually doing quantum magic (like generating entangled particles) just by looking at the input and output numbers, without ever opening the box to see how it works.

For a long time, scientists had a big problem: To prove the magic was real, they assumed the person picking the settings (the "Random Number Generator" or RNG) was perfectly independent. They assumed the RNG had no secret connection to the magic box. If the RNG and the box were secretly whispering to each other, the whole test could be faked.

This paper says: "We don't need perfect independence anymore. We just need a tiny bit of leftover randomness."

Here is the breakdown using simple analogies:

1. The Old Rule: The "Perfect Stranger"

Imagine you are testing a new video game console. To prove it's a real console and not a fake one, you ask a friend to randomly press buttons.

The Old Assumption: Your friend must be a "perfect stranger." They must have absolutely no idea what the console is doing, and the console must have no way of predicting which buttons your friend will press.
The Problem: In the real world, we use computers to generate random numbers. What if the computer generating the numbers is secretly linked to the console? If they are linked, the console could cheat and fake the results.

2. The New Discovery: The "Leaky Bucket"

The authors of this paper found a loophole. They realized you don't need your friend to be a perfect stranger. You just need them to be unpredictable enough.

The Analogy: Imagine your friend is holding a bucket of water (the random numbers).
- Old Rule: The bucket must be completely sealed. No water can leak out to the console, and the console can't see inside.
- New Rule: The bucket can have a tiny hole. As long as the water (randomness) doesn't completely stop flowing, and the console can't perfectly predict exactly which drop will fall next, the test still works!

They call this "Residual Randomness." Even if the source of the random numbers is slightly "tainted" or correlated with the device, as long as there is some randomness left that the device can't predict, the test holds up.

3. The Magic Trick: "Hardy Tests" vs. "Bell Scores"

The paper makes a fascinating distinction between two ways of testing the device:

The "Score" Method (Bell Inequalities): This is like asking, "How many points did you get?"
- The Result: If the random number generator is even slightly correlated with the device, this method fails. The device can cheat the score. It's like a student cheating on a math test because they know the teacher's schedule.
The "Impossible Event" Method (Hardy Tests): This is like asking, "Did you do something that is physically impossible?"
- The Result: This method succeeds even with a leaky bucket.
- The Metaphor: Imagine a magician claims they can make a coin vanish. If they do it, it's magic. But if they claim they can make a coin vanish and make it appear in your pocket at the same time, that's a logical contradiction.
- The paper shows that if the device produces a result that is logically impossible (like a coin being in two places at once), it must be doing real quantum magic, even if the person picking the settings is slightly suspicious. The "impossibility" is so strong that it breaks through the correlation.

4. The Big Win: Testing "Partially Entangled" States

In quantum physics, particles can be "entangled" (linked).

Maximally Entangled: Like two coins that are always exactly opposite (Heads/Tails).
Partially Entangled: Like two coins that are mostly opposite, but sometimes both land on Heads.

For years, scientists could only "self-test" the perfectly linked coins if the settings were perfectly random. This paper proves you can now test any partially linked state, even if the randomness source is untrusted, as long as that "leaky bucket" of randomness exists.

Why Does This Matter?

Think of Device-Independent Cryptography as a super-secure lock.

Before: You could only use this lock if you were 100% sure the key-maker (the random number generator) was honest and uncorrelated with the lock. This is hard to guarantee in the real world.
Now: You can use this lock even if the key-maker is a bit shady, as long as they aren't completely in the lock's pocket.

In a nutshell:
The authors found a way to verify quantum devices using "impossible" logic puzzles (Hardy tests) that are so robust, they work even when the random number generator isn't perfectly independent. It turns a strict "all-or-nothing" requirement into a more realistic "mostly independent" one, making secure quantum technology much more practical for the real world.

Here is a detailed technical summary of the paper "Self-testing with untrusted random number generators" by Moisés Bermejo Morán and Ravishankar Ramanathan.

1. Problem Statement

Self-testing is a powerful protocol in quantum information that allows users to verify the internal state and measurements of a quantum device (black-box) solely based on input-output statistics, typically by observing the maximal violation of a Bell inequality.

The Limitation: Standard self-testing protocols rely heavily on the measurement independence assumption. This assumes that the random number generators (RNGs) used to choose measurement settings are perfectly random and completely uncorrelated with the device being tested (and any potential eavesdropper).
The Reality: In realistic scenarios, RNGs may be imperfect or partially correlated with the device. If the settings are correlated with the device's hidden variables, local hidden variable models can mimic quantum correlations, breaking the security and certification guarantees of device-independent protocols.
The Core Question: Can self-testing be achieved if the randomness source is untrusted (i.e., potentially correlated with the device), provided the source retains some degree of unpredictability?

2. Methodology

The authors propose a framework that relaxes the strict independence assumption to a weaker condition called Residual Randomness.

Residual Randomness Assumption: The authors assume that the outputs of the random sources ( $s, t$ ) cannot be perfectly predicted by the measurement outcomes ( $a, b$ ) and settings ( $x, y$ ). Mathematically, this is expressed as $p(st|abxy) > 0$ for all possible outcomes. This implies that even conditioned on the device's state and measurement results, the source retains some entropy.
Shift from Probabilistic to Possibilistic Tests:
- Traditional self-testing often relies on maximizing Bell inequalities (probabilistic approaches, e.g., CHSH).
- The authors utilize Hardy-type tests and tilted Hardy tests, which rely on impossibility conditions (probabilities of certain events being exactly zero) rather than just maximizing a value.
Mathematical Framework:
- They model the scenario as a Bell experiment with untrusted sources, where the joint probability distribution is $p(stab|xy)$ .
- They utilize the NPA hierarchy (Navascués-Pironio-Acín) and semidefinite programming to characterize quantum distributions under the residual randomness constraint.
- They prove that "impossible events" (zero probabilities) in the distribution are independent of the source index ( $s, t$ ) under the residual randomness assumption (Lemma 1).

3. Key Contributions

A. Self-Testing of Partially Entangled States

The primary contribution is the proof that all pure bipartite partially entangled states can be self-tested even when the measurement settings are chosen by untrusted sources, provided the sources satisfy the residual randomness constraint.

Mechanism: They extend tilted Hardy tests (originally proposed by Zhao et al.) to the untrusted source scenario.
Result: By observing specific zero-probability events and a specific maximal quantum value for a tilted Bell expression, the device is certified to be in a state $|\psi_w\rangle = \cos\theta_w|00\rangle + \sin\theta_w|11\rangle$ up to local isometries.
Significance: This provides a semi-device-independent certification of the independence between the randomness source and the device. If the protocol succeeds, it certifies that the source was not fully correlated with the device.

B. Extension to Arbitrary Dimensions (Qudits)

The authors generalize the qubit results to arbitrary dimensions ( $d$ ).

Method: They construct an inhomogeneous covering tree for the target state $|\psi\rangle = \sum c_i |ii\rangle$ .
Protocol: By decomposing the high-dimensional state into a set of two-dimensional subspaces (edges of the tree) and applying the Hardy self-test to each edge, they can self-test the entire global state.
Efficiency: They show that this can be achieved with a manageable number of measurement settings (one $d$ -outcome measurement and $d-1$ dichotomic measurements per party).

C. Fundamental Distinction: Hardy vs. Bell Values

The paper establishes a critical theoretical boundary between different types of self-tests:

Hardy Tests (Possibilistic): Succeed under arbitrarily weak residual randomness (as long as $p(st|abxy) > 0$ ). They rely on the existence of "impossible" events which remain impossible regardless of the source correlation.
Bell Inequalities (Probabilistic): Fail under weak independence. The authors demonstrate that a maximal CHSH value ($2\sqrt{2} $) **does not** self-test the state if the residual randomness is weak (specifically, if the correlation allows$ l < 1/4$). In such cases, one can construct local hidden variable models that mimic the maximal quantum value without the device actually being in the target state.

4. Key Results

Proposition 2: For any partially entangled two-qubit state, there exist conditions (three zero-probability events and one tilted Bell value) that uniquely self-test the state and measurements, even with untrusted sources satisfying residual randomness.
Proposition 5 & Theorem 6: These conditions extend to arbitrary dimensions. Any pure bipartite partially entangled state $|\psi\rangle = \sum c_i |ii\rangle$ can be self-tested using a protocol based on a covering tree and Hardy tests.
Impossibility of Self-Testing Maximal Entanglement (in 2D): The paper notes that maximal entanglement in dimension 2 cannot be self-tested using Hardy-type tests because such tests require non-maximal entanglement to generate the necessary "impossible" events.
Failure of CHSH: A maximal CHSH violation does not guarantee self-testing in the presence of untrusted sources with residual randomness $l < 1/4$ . The source could be correlated with the device to fake the violation.

5. Significance and Implications

Robustness of Device-Independent Protocols: This work significantly broadens the applicability of device-independent quantum cryptography and randomness amplification. It shows that perfect independence of the RNG is not strictly necessary; a weaker "residual randomness" condition suffices for certifying the quantum state.
Semi-Device Independence: The protocol effectively acts as a self-check for the independence assumption. If the self-test passes, the user is guaranteed that the RNG was not fully compromised by the device.
Theoretical Insight: The paper highlights a fundamental difference between probabilistic nonlocality (Bell inequalities) and possibilistic nonlocality (Hardy tests). Possibilistic tests are more robust against measurement dependence, making them superior for scenarios where the independence assumption is suspect.
Future Directions: The authors identify that robust self-testing (tolerance to noise) with untrusted sources remains an open question, as does the generalization of these results to maximal entanglement in higher dimensions.

In summary, the paper demonstrates that self-testing is possible beyond the independence assumption by leveraging the structural rigidity of "impossible events" in quantum mechanics, offering a more realistic path for certifying quantum devices in adversarial environments.