Degree of Entanglementa

Günther Krenn, Anton Zeilinger

William J. Munro, Kae Nemoto, Andrew G. White

Entanglement is a critical resource used in many current quantum information schemes. As such entanglement has been extensively studied in two qubit systems and its entanglement nature has been exhibited by violations of the Bell inequality. Can the amount of violation of the Bell inequality be used to quantify the degree of entanglement? What do Bell inequalities indicate about the nature of entanglement?

Ilias Diakonikolas, Daniel M. Kane

The degree-d Chow parameters of a Boolean function are its degree at most d Fourier coefficients. It is well-known that degree-d Chow parameters uniquely characterize degree-d polynomial threshold functions (PTFs) within the space of all bounded functions. In this paper, we prove a robust version of this theorem: For f any Boolean degree-d PTF and g any bounded function, if the degree-d Chow parameters of f are close to the degree-d Chow parameters of g in ℓ2-norm, then f is close to g in ℓ1-distance. Notably, our bound relating the two distances is independent of the dimension. That is, we show that Boolean degree-d PTFs are robustly identifiable from their degree-d Chow parameters. No non-trivial bound was previously known for d >1.

John M. Myers, Tai Tsun Wu