Maximal device-independent randomness in every dimension

1. Problem Statement

The paper addresses the fundamental limits of Device-Independent Quantum Random Number Generation (DIQRNG).

• Context: In DIQRNG, randomness is certified solely from observed measurement statistics (Bell correlations) without trusting the internal workings of the devices. This relies on the violation of Bell inequalities to guarantee that an eavesdropper (Eve) cannot predict the outcomes.
• The Limit: It is theoretically established that for a quantum system with local dimension $d$, the maximum amount of certifiable private randomness is bounded by $2 \log(d)$ bits.
• The Gap: While this bound is known, it was previously only proven to be achievable for $d=2$ (qubits). For dimensions $d > 2$, it was unknown whether this fundamental limit could be reached, and if so, what explicit protocols (states and measurements) would achieve it. Existing numerical approaches for $d=3$ fell short of the bound, and analytical solutions were lacking.
• The Challenge: Standard certification tools like self-testing (which uniquely identifies states and measurements up to local isometries) generally fail for non-projective measurements (POVMs), which are required to reach the maximal randomness bound.

2. Methodology

The authors develop a novel analytical framework combining Bell inequalities, sum-of-squares (SOS) decompositions, and C-algebra representation theory*.

A. The Setup: Balanced Informationally Complete (BIC) POVMs

• The protocol utilizes a specific family of measurements called Balanced Informationally Complete POVMs (BIC-POVMs).
• A BIC-POVM in dimension $d$ consists of $d^2$ rank-1 projections $\{P_j\}$ such that $\sum P_j = dI$ and they form a basis for the space of operators $M_d(\mathbb{C})$.
• The authors prove the existence of such POVMs in every dimension $d$ using group-theoretic constructions (Weyl operators) and specific fiducial vectors.

B. The Bell Inequality

• They construct a specific Bell inequality (linear function of correlations) tailored to the BIC-POVM structure.
• Alice's Settings: She has $d^2(d^2-1)/2 + 1$ settings. Most are 3-outcome measurements used for "checking" the state, and one setting (labeled povm) has $d^2$ outcomes used for generating randomness.
• Bob's Settings: He has $d^2$ binary-outcome measurements.
• The Bound: The maximum quantum value of this Bell function is proven to be $d^2$.

C. Certification Technique: "Weak" Self-Testing

Since non-projective POVMs cannot be fully self-tested (due to Naimark's dilation theorem), the authors introduce a weaker certification method:

1. Sum-of-Squares (SOS) Decomposition: They prove that the shifted Bell operator $\beta I - W_d$ (where $\beta = d^2$) can be written as a sum of squares of operators. This proves $d^2$ is the tight upper bound.
2. Local Support Compression: Instead of characterizing the entire Hilbert space, they analyze the operators compressed onto the local support of the quantum state ($\text{supp}_A \rho$ and $\text{supp}_B \rho$).
3. Algebraic Characterization: They define a C*-algebra $A_S$ generated by the relations satisfied by the BIC-POVM elements. Using representation theory, they show that any optimal strategy must decompose into a direct sum of irreducible representations of this algebra.
4. State Factorization: They prove that in any optimal strategy, the state restricted to the local support is a mixture of maximally entangled states of dimension $r_\alpha d$, tensored with uncharacterized states. Crucially, the randomness-generating measurement acts trivially on the uncharacterized parts and as a BIC-POVM on the maximally entangled parts.

3. Key Contributions

1. Achieving the Fundamental Bound: The paper provides the first explicit proof that the theoretical maximum of $2 \log(d)$ bits of device-independent randomness can be extracted from any local dimension $d$.
2. Explicit Protocols: They provide a constructive protocol for every $d$, specifying the required state (maximally entangled) and the specific measurements (BIC-POVMs and related projective checks).
3. New Certification Framework: The authors develop a technique to certify randomness in scenarios where full self-testing is impossible (non-projective measurements). This relies on:
   • Certifying properties of operators compressed to the local support.
   • Utilizing the representation theory of the algebra generated by the measurement relations.
4. Existence of BIC-POVMs: They provide rigorous proofs for the existence of BIC-POVMs in all dimensions, distinguishing them from the more restrictive Symmetric IC-POVMs (SIC-POVMs), whose existence is a famous open problem.

4. Main Results

• Theorem 3.2: If a quantum strategy achieves the maximal value $d^2$ of the constructed Bell inequality, the conditional von Neumann entropy $H(A|E)$ of Alice's povm outcome is exactly $2 \log(d)$.
• Structure of Optimal Strategies: Any optimal strategy is equivalent (up to local isometries) to a mixture of states of the form:
  $$\bigoplus_\alpha |\chi_\alpha\rangle \otimes |\phi_{r_\alpha d}\rangle$$
  where $|\phi_{r_\alpha d}\rangle$ is a maximally entangled state of dimension $r_\alpha d$. The randomness-generating measurement acts as a BIC-POVM on the entangled part and trivially on the rest.
• Classical vs. Quantum Gap: The paper analyzes the classical value of the Bell inequality, showing a strict separation between classical and quantum values, ensuring the protocol is robust against classical strategies.

5. Significance and Implications

• Resource Efficiency: The result demonstrates that one can fully harness the "dimension" of a quantum system for randomness generation. As quantum technologies scale to higher dimensions (qudits), this protocol ensures the theoretical maximum efficiency is achievable.
• Beyond Self-Testing: The methodology opens new avenues for device-independent certification in scenarios where full self-testing is too demanding or impossible (e.g., non-projective measurements). This is crucial for practical quantum information processing where ideal projective measurements are hard to implement.
• Practicality:
  • The protocol uses a locally $d$-dimensional entangled state. While BIC-POVMs are non-projective, they can be implemented via Naimark dilation (using an ancilla held only by Alice) or via standard physical degrees of freedom (like spatial modes of photons) without needing a new physical system.
  • The authors discuss "spot-checking" protocols, where the randomness-generating setting is chosen most of the time, minimizing the randomness cost of the verification settings.
• Mathematical Insight: The work connects quantum randomness certification with the algebraic structure of POVMs, offering new insights into the existence and properties of BIC-POVMs and their relation to SIC-POVMs.

In summary, this paper resolves a long-standing open problem in quantum information theory by proving that the fundamental limit of device-independent randomness is achievable in every dimension, utilizing a novel algebraic certification technique that bypasses the limitations of traditional self-testing.