Certified quantum supremacy in entanglement-assisted prepare-measure random-access-code

Technical Summary: Certified Quantum Supremacy in Entanglement-Assisted Prepare-Measure Random-Access Codes

Problem Statement
The paper addresses the limitations of standard Prepare-Measure Random-Access Codes (PMRACs), a framework where a sender (Alice) encodes an $n$-bit string into a physical system of dimension $d$ (sending $l < n$ bits or qubits) for a receiver (Bob) to decode a specific bit $x_y$ based on an input $y$. While standard quantum PMRACs offer advantages over classical counterparts, this work investigates a "semi-device-independent" (SDI) scenario enhanced by prior entanglement. Specifically, the authors explore a family of $n \to l$ entanglement-assisted PMRAC games where Alice and Bob share a bipartite entangled state. Alice applies local quantum operations (unitaries) to her subsystem to encode her input $x$ and transmits her $l$ qubits to Bob, who performs a joint measurement on the received qubits and his retained half of the entangled state. The goal is to determine the optimal quantum success probabilities for these games and demonstrate "quantum supremacy" over both classical RACs and standard (non-entangled) quantum PMRACs.

Methodology
The authors employ a semi-device-independent framework, assuming a bound on the Hilbert-space dimension of the communicated system without trusting the internal workings of the preparation and measurement devices. The core methodology involves:

1. Analytical Optimization: The authors derive optimal success probabilities for specific cases ($4 \to 1$, $4 \to 2$, and $5 \to l$) using an elegant analytical technique. This involves formulating the success probability in terms of a correlation function $I$ and maximizing it using convex inequalities and properties of scaled Frobenius norms.
2. State and Measurement Certification: By analyzing the conditions required to achieve the optimal correlation values, the authors deduce necessary properties of the shared quantum states, Alice's encoding unitaries, and Bob's measurement observables.
3. Generalization: The framework is extended to a general $n \to n-2$ case to derive upper bounds on quantum success probabilities for arbitrary $n$.

Key Contributions and Results

• $4 \to 1$ Entanglement-Assisted PMRAC:

  • The authors analytically derive the optimal quantum success probability as $(P_{4\to1}^Q)_{opt} = \frac{1}{2} + \frac{1}{2\sqrt{2}} \approx 0.853$.
  • This value exceeds the optimal classical success probability for $4 \to 2$ ($P_{4\to2}^C = 0.75$) and the standard quantum PMRAC ($P_{4\to1}^{SQ} \approx 0.7415$).
  • Certification: Achieving this optimal probability certifies that the shared state is a maximally entangled two-qubit state, that Alice's encoding operations are specific mutually anti-commuting unitaries, and that Bob's measurements are uniquely determined by these states. This establishes a "self-testing" capability for the unitary operations.

• $4 \to 2$ Entanglement-Assisted PMRAC:

  • The optimal quantum success probability is derived as $(P_{4\to2}^Q)_{opt} = \frac{1}{2} + \frac{\sqrt{3}}{4} \approx 0.933$.
  • This surpasses the classical limit even when three classical bits are communicated ($P_{4\to3}^C$).
  • State Necessity: The authors prove that achieving this optimal value necessitates the shared state to be a three-qubit GHZ state (or a state in the GHZ class). Unlike the $4 \to 1$ case, they note the challenge in analytically proving the existence of a "grand unitary" transformation between bases for this case, though they provide explicit constructions for states and measurements.

• $5 \to l$ Entanglement-Assisted PMRAC:

  • The paper derives upper bounds for $5 \to 1$, $5 \to 2$, and $5 \to 3$ scenarios.
  • The derived upper bounds are approximately $0.847$, $0.887$, and $0.947$, respectively.
  • These results consistently demonstrate a quantum advantage over classical RACs for the same communication constraints.

• General $n \to n-2$ Case:

  • The framework is generalized to arbitrary $n$ where $l = n-2$.
  • An upper bound for the quantum success probability is derived: $P_{n\to n-2}^Q \leq \frac{1}{2} + \frac{\sqrt{n(n-1)}}{2^n}$.
  • The paper confirms that for $n=\{3, 4, 5\}$, the specific results derived earlier satisfy this general bound.

Significance and Claims
The paper claims to demonstrate certified quantum supremacy in the context of entanglement-assisted communication games. The primary significance lies in the ability to not only outperform classical and standard quantum protocols but also to certify the underlying physical resources and operations in a semi-device-independent manner.

Specifically, the authors claim:

1. Superiority: Entanglement-assisted PMRACs strictly outperform both classical RACs and standard quantum PMRACs for the cases analyzed.
2. Self-Testing: The optimal success probability in the $4 \to 1$ case serves as a witness that certifies the shared state is maximally entangled, Alice's local unitary operations are specific anti-commuting operators, and Bob's measurements are fixed.
3. Resource Identification: For the $4 \to 2$ case, the optimal value is shown to be achievable only if the shared resource is a GHZ-class state, highlighting the specific role of multipartite entanglement in these communication tasks.

The authors conclude that their conceptual and technical framework provides a foundation for systematically investigating entanglement-assisted communication games, though they note that general $n$-bit cases for arbitrary $l$ remain computationally demanding and are left for future work. They also suggest that studying the robustness of these protocols against noise is a potential future direction.