More entropy from shorter experiments using polytope approximations to the quantum set

This paper introduces a systematic method using iterative polytope approximations within the probability estimation framework to significantly improve certified entropy rates and reduce device requirements for finite-size device-independent quantum random number generation and randomness amplification protocols.

The Gist

Imagine you are trying to prove that a machine is truly random. In the world of quantum physics, this is a big deal because if a machine is truly random, it can generate unbreakable encryption keys for the internet.

However, there's a catch: How do you know the machine isn't just following a hidden script?

This paper introduces a clever new way to prove that a quantum device is generating genuine randomness, even when you don't trust the machine's internal workings. Here is the breakdown using simple analogies.

1. The Problem: The "Black Box" and the "Cheater"

Imagine you have a black box (the quantum device). You press buttons (inputs), and it gives you lights (outputs). You want to be sure the lights are random.

But, there is a "Cheater" (an adversary, or "Eve") who might be trying to predict the lights.

• The Old Way: To prove the lights are random, scientists used to draw a giant, fuzzy safety net around all the possible things the machine could do. This net was so big and loose that it included many "fake" scenarios where the Cheater could easily predict the outcome. Because the net was so loose, the proof of randomness was weak, and you needed to run the machine millions of times to get a tiny amount of certified randomness.
• The Goal: We need a tighter net. We need to cut out the "fake" scenarios where the Cheater wins, leaving only the "real" quantum scenarios.

2. The Solution: The "Polytope" (The Shape-Shifting Net)

In math, a "polytope" is just a fancy shape with many flat sides (like a diamond or a soccer ball). The set of all possible "real" quantum behaviors is a weird, curved shape that is hard to calculate.

The authors' new method is like a smart sculptor.

• Step 1: They start with a big, rough block of stone (the loose safety net).
• Step 2: They use two special chisels (algorithms) to chip away the parts of the stone that cannot be real quantum behavior.
  • Chisel 1 (NearV): Looks at the "weird" corners of the stone that are closest to the machine's actual behavior and chips them off.
  • Chisel 2 (MaxGP): Asks, "If I were the Cheater, how would I try to guess the outcome?" It finds the Cheater's best possible tricks and chips away the parts of the stone that allow those tricks.

By removing these "impossible" or "cheating" corners, they create a much tighter, more accurate shape that hugs the real quantum behavior closely.

3. The Result: More Randomness, Less Time

Because this new shape is so much tighter than the old fuzzy net:

• The "Penalty" is smaller: In the past, you had to run the machine for a long time to overcome the "fuzziness" of the old net. Now, because the net is tight, you get a strong proof of randomness much faster.
• The Analogy: Imagine trying to catch a fish.
  • Old Method: You use a giant, loose net. You have to drag it through the ocean for hours to catch one fish, and you aren't even sure it's the right kind of fish.
  • New Method: You use a laser-guided net that fits the fish perfectly. You catch the fish in seconds, and you know for a fact it's the right one.

4. Why This Matters

• Speed: You need fewer "device uses" (fewer button presses) to get the same amount of certified randomness. This saves time and computing power.
• Security: It proves the randomness is secure even against a super-smart Cheater who might have some inside information.
• Real World: The authors tested this on real data from quantum computers and found they could extract twice as much randomness from the same data compared to previous methods.

Summary

The authors built a smart, adaptive filter that removes all the "fake" ways a quantum machine could behave. By doing this, they can prove the machine is truly random much faster and with fewer resources than ever before. It's like upgrading from a wide-mesh fishing net to a precision laser trap, ensuring that the randomness you get is genuine and secure.

Technical Summary

Here is a detailed technical summary of the paper "More entropy from shorter experiments using polytope approximations to the quantum set."

1. Problem Statement

Device-Independent Quantum Random Number Generation (DI-QRNG) aims to generate certified randomness based solely on input-output statistics, without trusting the internal workings of the hardware. While this offers security against computationally unbounded adversaries, it faces two main challenges in practical, finite-size regimes:

1. Low Entropy Rates: Standard security proofs (like the Entropy Accumulation Theorem or Azuma-Hoeffding inequalities) often yield low certified entropy rates, requiring a massive number of device uses ($n$) to generate a positive amount of randomness.
2. Computational Bottlenecks: The Probability Estimation (PE) framework, which is highly effective for finite-size analysis, requires optimizing over the set of allowed quantum behaviors. However, the set of quantum correlations is not a polytope (it is defined by non-linear constraints), making direct optimization intractable.
   • Existing solutions use coarse outer-polytope approximations (e.g., the non-signalling set or simple Tsirelson bounds). These approximations are too loose, allowing hypothetical "supra-quantum" strategies that an adversary could use, thereby artificially lowering the certified entropy bounds.
   • Conversely, fine-grained approximations are computationally intractable in high-dimensional spaces.

The Core Problem: How to construct tight, computationally tractable polytope approximations of the quantum set that exclude non-quantum strategies relevant to the specific experimental data, thereby maximizing certified entropy rates for finite $n$.

2. Methodology

The authors propose a systematic method to generate custom polytope approximations tailored to the typical behavior of a specific device. Their approach integrates these approximations into the PE framework.

A. The PE Framework Context

The PE framework certifies entropy by constructing a Probability Estimation Factor (PEF), $F(C, Z)$, which satisfies:
$$\mathbb{E}[F(C, Z) \mu(D|Z)^\beta] \leq 1$$
for all allowed behaviors $\mu$ in a set $S$. To maximize the certified entropy, one must find the optimal $F$ over the set of allowed behaviors. This optimization is only solvable if $S$ is a convex polytope.

B. The Proposed Algorithms

The authors introduce two iterative algorithms to refine an initial outer-polytope approximation ($P_{in}$, e.g., the non-signalling set) into a tighter polytope ($P_Q$) that better approximates the quantum set $Q$. Both algorithms rely on the NPA hierarchy (Navascués-Pironio-Acín) to determine quantum bounds and identify non-quantum vertices.

1. Algorithm 1: NearV (Nearest Non-Quantum Vertices)

   • Intuition: An adversary can decompose the observed device behavior into a convex combination of vertices of the polytope. If the decomposition includes non-quantum vertices, the entropy bound is weakened.
   • Process:
     1. Identify the $m$ vertices of the current polytope closest to the observed typical behavior $\vec{p}$.
     2. Randomly select one of these "near" non-quantum vertices ($\vec{v}_{near}$).
     3. Find the closest point in the quantum set ($\vec{q} \in Q$) to this vertex.
     4. Construct a quantum Bell inequality (a half-space) defined by the vector $\vec{b} = \vec{v}_{near} - \vec{q}$ that separates the non-quantum vertex from the quantum set.
     5. Intersect the current polytope with this new inequality to remove the non-quantum region.
   • Goal: Iteratively prune the polytope near the observed data.

2. Algorithm 2: MaxGP (Maximum Guessing Probability)

   • Intuition: Focuses on the specific adversarial strategies that maximize the probability of guessing the output (minimizing min-entropy).
   • Process:
     1. For a given input setting, solve an optimization problem to find the set of behaviors $\{\vec{\mu}_\lambda\}$ that maximize the adversary's guessing probability for the observed distribution.
     2. If any of these optimal strategies are non-quantum, treat them similarly to Algorithm 1: find the closest quantum point and generate a separating Bell inequality.
     3. Refine the polytope by intersecting with these new inequalities.
   • Goal: Directly target the strategies that pose the greatest threat to entropy certification.

C. Integration with Randomness Amplification

The method is extended to Randomness Amplification protocols, where the input source is weakly random and potentially correlated with the device (modeled by Santha-Vazirani sources). The authors construct a joint polytope for inputs and outputs, allowing the PE framework to handle correlated inputs without assuming independence.

3. Key Contributions

1. Systematic Polytope Construction: A novel, general-purpose framework for generating tight outer-polytope approximations of the quantum set, moving beyond static, coarse approximations.
2. Two Efficient Algorithms: The development of NearV and MaxGP, which balance computational cost with approximation quality by iteratively removing only the non-quantum regions most relevant to the specific experimental data.
3. Software Implementation: Public release of Python code (PE_polytope_approximation) that integrates these algorithms with the PE framework, making the method accessible for practical DI-QRNG implementations.
4. Extension to Correlated Inputs: Successful application of the method to randomness amplification scenarios, a notoriously difficult problem in DI-QRNG.

4. Results

The authors tested their method on various scenarios using both simulated noisy data and real experimental data.

• Bipartite CHSH Scenarios:

  • Applied to standard and asymmetric CHSH inequalities with varying noise levels.
  • Result: The new polytope approximations yielded significantly higher certified entropy rates compared to previous methods (using non-signalling sets or Tsirelson bounds).
  • Finite-Size Advantage: The method achieved positive entropy rates with fewer device uses (orders of magnitude fewer in some cases) compared to the Entropy Accumulation Theorem (EAT) or Azuma-Hoeffding-based methods.

• Experimental Data (Loophole-Free CHSH):

  • Tested on data from real-world loophole-free Bell tests (e.g., Rosenfeld et al., Zhang et al.).
  • Result: For the dataset in [24], the method nearly doubled the extractable entropy rate compared to previous analyses, whereas previous attempts with refined polytopes only showed marginal gains.

• Tripartite Mermin Scenarios:

  • Tested on data from a Quantinuum H1 ion-trap quantum computer performing a Mermin-Bell test.
  • Result: The method provided improved entropy bounds, demonstrating scalability to tripartite systems.

• Randomness Amplification:

  • Applied to a bipartite protocol using Hardy paradoxes and Santha-Vazirani sources.
  • Result: Achieved improvements of several orders of magnitude in entropy rates compared to existing techniques, with no added complexity in the security analysis.

5. Significance and Conclusion

• Practical Impact: This work bridges the gap between theoretical security proofs and practical implementation. By enabling higher entropy rates with fewer device uses, it makes DI-QRNG more viable for real-world applications where generating large amounts of data is costly or slow.
• Overcoming the Post-Processing Bottleneck: Randomness extraction algorithms are computationally expensive and scale with the input size. By reducing the number of required device rounds ($n$) to achieve a target entropy, the method alleviates the computational bottleneck of post-processing.
• Security: The method provides rigorous security proofs against computationally unbounded adversaries (classical side information) and, by extension, can be adapted for quantum side information.
• Scalability: While vertex enumeration (a step in the algorithm) is computationally intensive for very high-party scenarios, the authors demonstrate that for the common bipartite and tripartite setups, the method is highly effective and ready for deployment.

In summary, the paper provides a ready-to-use, effective tool to prove security with improved certified entropy rates in the most common practical DI-QRNG protocols, significantly outperforming existing state-of-the-art techniques in the finite-size regime.