Bound Entanglement Is Insufficient for an Exponential Quantum Learning Advantage

Quantum learning tasks often exhibit an exponential separation in sample complexity between entanglement-assisted and entanglement-free protocols. While entanglement is known to be the driver of this advantage, it is not clear which specific properties of entangled resources are required. This paper investigates whether bound entanglement—a class of nondistillable entangled states—is sufficient to provide an exponential learning advantage, or if a stronger form of entanglement is necessary.

The authors utilize the reduction criterion, a mathematical condition satisfied by all bound-entangled states. They analyze two primary learning tasks: Pauli-channel learning and conjugate-state learning. By imposing the reduction criterion as a one-sided restriction on either the input states or the measurement effects (POVMs), they test whether an exponential advantage persists. They further quantify the robustness of this obstruction by relaxing the criterion using conditional min-entropy, allowing for a continuous transition between restricted and unrestricted resource regimes.

The study proves that if either the input states or the measurement effects satisfy the reduction criterion, the exponential learning advantage is lost. Specifically, for Pauli-channel learning, the sample complexity reverts to the scaling of entanglement-free protocols, even when the unrestricted side of the protocol retains arbitrary quantum correlations. This obstruction holds for both incoherent and one-sided coherent adaptive protocols. Similarly, in conjugate-state learning, the reduction criterion prevents the logarithmic-sample advantage typically enabled by unrestricted joint measurements. These results demonstrate that the operational utility of entanglement for learning is not determined by the mere presence of entanglement, but by its ability to violate the reduction criterion.