A semi-definite programming formulation of the device-dependent guessing probability

This paper introduces a semi-definite programming formulation to precisely estimate the intrinsic randomness and an adversary's guessing probability in fully characterized prepare-and-measure quantum setups, demonstrating its ability to determine exact certifiable randomness and revealing that entanglement strictly increases an adversary's predictive power.

The Gist

Imagine you are running a magic show where you pull a rabbit out of a hat. In the quantum world, this "rabbit" is a random number generated by measuring a tiny particle. The big question for security experts is: How truly random is this rabbit? Could a sneaky magician (an adversary named "Eve") have rigged the hat or the rabbit so she knows exactly what's coming out before the trick happens?

This paper introduces a new, powerful mathematical tool to answer that question for the simplest kind of quantum magic tricks, known as "prepare-and-measure" setups.

Here is a breakdown of the paper's findings using simple analogies:

1. The Problem: The "Black Box" Mystery

In the real world, our quantum devices (the hat and the rabbit) aren't perfect. They are noisy, like a radio with static.

• The Setup: Alice (the honest user) has a device that prepares a specific quantum state (the rabbit) and measures it (pulls the rabbit out). She knows what the device should do.
• The Threat: Eve (the hacker) might know more than Alice. She might have a secret "cheat sheet" or a hidden connection to the device that lets her guess the outcome.
• The Difficulty: Until now, calculating exactly how much Eve could guess was like trying to solve a maze that keeps changing shape. There was no general, easy way to find the answer, especially when the device is noisy.

2. The Solution: A "Magic Calculator" (Semidefinite Programming)

The authors created a new mathematical recipe called a Semidefinite Programming (SDP) formulation.

• The Analogy: Imagine trying to find the highest point in a foggy mountain range. Previously, you had to guess your way up, and you might get stuck in a small valley thinking it was the peak. The new SDP method is like a drone that can see the whole mountain range at once and instantly tells you the exact highest peak.
• What it does: It takes the messy, noisy reality of the quantum device and turns it into a clean, solvable math problem. This allows scientists to calculate the exact amount of randomness that is guaranteed to be safe from Eve, rather than just guessing with a "best guess" upper limit.

3. What They Discovered (The Three Tests)

The authors tested their new calculator on three different scenarios to see how it worked:

• Test A: The Noisy Mirror
  They looked at a scenario where both the rabbit and the hat were covered in "static" (depolarizing noise).

  • Result: Their calculator confirmed that a previous mathematical guess about how random this setup was, was actually perfect. It proved that the old guess was the absolute limit.

• Test B: The Leaky Detector
  They looked at a setup where the detector (the hand pulling the rabbit) was sometimes lazy or inefficient.

  • Result: Previous methods assumed the "leak" was in a specific, simple way. The new calculator showed that if Eve is clever enough to use a more complex "leak," she can guess slightly better than the old methods thought. This means previous estimates of randomness were slightly too optimistic (overestimating the safety).

• Test C: The Multi-Outcome Trick
  They looked at a trick where the device could produce many different outcomes (like pulling out a rabbit, a dove, or a dove's egg).

  • Result: A previous theory claimed that if you trust the measurement device completely, you could generate infinite randomness. The new calculator showed that if Eve is allowed to have a secret link to the measurement device, that "infinite randomness" vanishes once you have more than 3 or 4 possible outcomes. The safety was an illusion caused by assuming the device was perfectly isolated.

4. The Big Surprise: Entanglement is a Superpower

The most interesting finding is about entanglement (a spooky connection between particles).

• The Old Assumption: Many security models assume that the device preparing the state and the device measuring it are separate and only share "classical" information (like a phone call).
• The New Finding: The authors proved that if the preparation device and the measurement device are entangled (linked by quantum magic), Eve's ability to guess the outcome strictly increases.
• The Analogy: Imagine two spies trying to guess a secret code. If they just talk on the phone (classical correlation), they might guess 90% of the time. But if they share a telepathic link (entanglement), they can guess 91% of the time. Even that tiny 1% difference matters in high-stakes security. This is the simplest example ever shown where this quantum link gives the hacker an unfair advantage.

Summary

This paper gives us a better, more honest ruler to measure quantum randomness. It shows that:

1. We can now calculate the exact safety of simple quantum random number generators.
2. Previous methods often overestimated safety by assuming the devices were simpler or more isolated than they really are.
3. If the devices share a quantum connection (entanglement), the hacker's power goes up, meaning we need to be even more careful about how we build these devices.

The authors have even made their "calculator" code available so others can use it to test their own quantum devices.

Technical Summary

Technical Summary: A Semi-Definite Programming Formulation of the Device-Dependent Guessing Probability

Problem Statement
In quantum mechanics, the intrinsic randomness generated by measuring a state that is not an eigenstate of the observable is a fundamental resource for Quantum Random Number Generators (QRNGs). While the simplest QRNG scenario involves a fully characterized (device-dependent) prepare-and-measure (PM) setup—where a known state $\rho_S$ is measured by a known Positive Operator-Valued Measure (POVM) $\{M^a_S\}$—quantifying the exact amount of certifiable randomness remains challenging.

The standard operational metric for randomness is the conditional min-entropy, $H_{\min}(A|E)$, which is derived from the maximum probability ($P_{\text{guess}}$) with which an adversary (Eve) can guess the measurement outcomes given quantum side information. In a device-dependent scenario, Eve is assumed to hold a purification of the joint state of the system and any ancillary systems involved in the measurement dilation. As noted in prior work [4], calculating this guessing probability involves a non-convex optimization problem over all possible Naimark dilations of the measurement and all possible correlations Eve might share with the devices. No general computational procedure existed to solve this non-convex problem exactly, often forcing researchers to rely on upper bounds or restrictive assumptions (e.g., assuming no entanglement between the preparation and measurement devices).

Methodology
The authors address this computational gap by proving that the device-dependent guessing probability can be reformulated as a Semidefinite Program (SDP).

1. Reformulation of the Optimization: The authors start with the definition of $P_{\text{guess}}$ as a maximization over projective measurements (PVMs) $\{\Pi^a_{SM}\}$ on the system-ancilla space and Eve's measurement outcomes. By introducing subnormalized states conditioned on Eve's outcomes, the problem is recast into a form involving non-commutative polynomials.
2. SDP Construction: Leveraging techniques from [5, 13], the authors express the projective measurement $\{\Pi^a_{SM}\}$ in a block form relative to an orthonormal basis of the system Hilbert space. This allows the definition of generalized moment matrices $\Gamma_e$.
3. Linear Constraints: The objective function and the physical constraints (compatibility with the known state $\rho_S$, the known POVM $\{M^a_S\}$, and the projectivity/completeness of the PVM) are expressed as linear functions of the coefficients of these moment matrices.
4. Completeness: The authors prove (Theorem 1) that this SDP relaxation is not merely an upper bound but provides a complete characterization of the guessing probability. Specifically, any feasible solution to the SDP corresponds to a valid physical solution of the original non-convex problem, ensuring the SDP yields the exact maximum guessing probability.

Key Results and Applications
The paper applies this SDP formulation to three specific scenarios to benchmark the method and determine exact randomness values where only bounds were previously known:

1. Depolarized State and Measurement: The authors analyze a setup where both the qubit state and the measurement are subject to depolarizing noise. The SDP results match the analytic lower bound derived in [6], confirming that the analytic bound is tight and the SDP correctly identifies the exact amount of certifiable randomness.
2. Depolarized State and Inefficient Detector: Revisiting a scheme proposed by Berta and Brandão [7] for quantum computers, the authors compare the randomness estimated using a specific, fixed dilation (as done in [7]) against the unrestricted optimization provided by their SDP. They find that fixing the dilation leads to a slight overestimation of the intrinsic randomness, demonstrating the necessity of optimizing over all possible dilations.
3. Uncharacterized State with Equiangular Measurements: The authors investigate a source-device-independent scheme [8] where the state is uncharacterized, but the measurement is a trusted, equiangular $k$-outcome POVM. While [8] claimed unbounded randomness could be extracted for $k > 3$ under the assumption of trusted measurements, the authors show that if Eve is allowed to be correlated with the measurement device (i.e., the measurement is not fully trusted), the certifiable randomness vanishes for $k=4$. This highlights the critical impact of measurement trust assumptions.

Entanglement and Predictive Power
A significant theoretical contribution of the paper is the demonstration that entanglement between the state preparation device and the measurement device strictly increases Eve's predictive power.

• The authors compare the guessing probability $P_{\text{guess}}$ (allowing arbitrary correlations, including entanglement) with $P^{\text{sep}}_{\text{guess}}$ (constrained to separable states between the system and the measurement register).
• Using a specific qubit state and binary measurement, they show that $P_{\text{guess}} > P^{\text{sep}}_{\text{guess}}$.
• This result implies that assuming the absence of entanglement between the preparation and measurement devices (a common simplification in some frameworks) leads to an overestimation of the generated randomness, even in the most elementary scenarios involving a single qubit and a binary measurement.

Significance and Claims
The paper claims to provide the first general, computationally friendly method to estimate the intrinsic randomness in device-dependent PM setups without relying on non-convex optimization heuristics or restrictive assumptions about device correlations.

• Certification: The SDP allows for the exact determination of certifiable randomness in scenarios where only upper bounds were previously available.
• Fundamental Insight: The work establishes that entanglement assistance between the preparation and measurement devices is a resource that strictly enhances an adversary's ability to predict outcomes, a consequence that is observable even in simple binary measurement scenarios.
• Practical Utility: The method serves as a general tool for certifying randomness in realistic, noise-affected quantum devices, offering a rigorous recipe for the simplest device-dependent QRNGs.

The authors conclude that their formulation advances the understanding of randomness generation in the presence of quantum side information and provides a robust framework for future randomness certification protocols.