5. Entanglement

The proof of Theorem 4 (http://planetmath.org/3distributeddynamicalsystems#Thmthm4)showed the structure presheaf has non-unique descent,reflecting the fact that measuring devices do not necessarilyreduce to products of subdevices. Similarly, as we will see,measurements do not in general decompose into independentsubmeasurements. Entanglement, $\gamma$, quantifies how far ameasurement diverges in bits from the product of itssubmeasurements. It turns out that $\gamma >0$ is necessary fora system to generate more information than the sum of itscomponents: non-unique descent thus provides “room at the top”to build systems that perform more precise measurementscollectively than the sum of their components.

Entanglement has no direct relation to quantum entanglement.The name was chosen because of a formal resemblance between thetwo quantities, see Supplementary Information of [1].

Definition 10.

Entanglement over partition $𝒫=\{M_1\mathrm{\dots }{M}_m\}$of $src({𝔪}_{𝐃})$ is

$$\gamma ({𝔪}_{𝐃},𝒫,d_{out})=H[{𝔪}_{𝐃}^{\mathrm{♮}}\circ d_{out}\parallel \underset{i=1}{\overset{m}{\otimes }}{\pi }_j\circ {𝔪}_j^{\mathrm{♮}}\circ d_{out}]$$

where ${\pi }_j:𝒱S^{𝐃}\to 𝒱S^{M_j}$ and ${𝔪}_j=\{(k,l)\in {𝔪}_{𝐃}|k\in M_j\}$.

Projecting via ${\pi }_j$ marginalizes onto the subspace$𝒱S^{M_j}$. Entanglement thus compares the measurementperformed by the entire system with submeasurements over thedecomposition of the source occasions into partition $𝒫$.

Theorem 9 (effective information decomposes additively whenentanglement is zero).

$$\gamma ({𝔪}_{𝐃},𝒫,d_{out})=0⟹ei({𝔪}_{𝐃},d_{out})=\sum _{i=1}^{m}ei({𝔪}_j,d_{out}).$$

Proof: Follows from the observations that (i)$H[p\parallel p_1\otimes p_2]=0$ if and only if $p=p_1\otimes p_2$; (ii)$H[p_1\otimes p_2\parallel q_1\otimes q_2]=H[p_1\parallel q_1]+H[p_2\parallel q_2]$;and (iii) the uniform distribution on $𝐃$ is a tensor ofuniform distributions on subsystems of $𝐃$.$\mathrm{■}$

The theorem shows the relationship between effective informationand entanglement. If a system generates more information “thanit should” (meaning, more than the sum of its subsystems), thenthe measurements it generates are entangled. Alternatively, onlyindecomposable measurements can be more precise than the sum oftheir submeasurements.

We conclude with some detailed computations for$X\times Y\stackrel{𝑔}{\to }Z$, Diagram (11) (http://planetmath.org/4measurement#id2).Let $𝒫=\{X|Y\}$.

Theorem 10 (entanglement and effective information for$g\mathrm{:}X\mathrm{\times }Y\mathrm{\to }Z$).

$\gamma ({𝔪}_{XY},𝒫,{\delta }_z)$$={\displaystyle \sum _{(x,y)\in g^{-1}(z)}}{\displaystyle \frac{1}{|g^{-1}(z)|}}{\log }_2{\displaystyle \frac{|g^{-1}(z)|}{|g_{x\times Y}^{-1}(z)|\cdot |g_{X\times Y}^{-1}(z)|}}$

$=ei({𝔪}_{XY},{\delta }_z)-ei({𝔪}_{X\bullet },{\delta }_z)-ei({𝔪}_{\bullet Y},{\delta }_z).$

Proof:The first equality follows from Propositions 5 (http://planetmath.org/4measurement#Thmthm5)and 6 (http://planetmath.org/4measurement#Thmthm6)

$$\gamma ({𝔪}_{XY},𝒫,{\delta }_z)=\sum _{(x,y)\in g^{-1}(z)}=\sum _{(x,y)\in g^{-1}(z)}\frac{1}{|g^{-1}(z)|}{\log }_2\left[\frac{1}{|g^{-1}(z)|}\cdot \frac{|g^{-1}(z)|}{|g_{x\times Y}^{-1}(z)|}\frac{|g^{-1}(z)|}{|g_{X\times Y}^{-1}(z)|}\right].$$

From the same propositions it follows that$ei({𝔪}_{XY},{\delta }_z)-ei({𝔪}_{X\bullet },{\delta }_z)-ei({𝔪}_{\bullet Y},{\delta }_z)$ equals

$${\log }_2\frac{|X|\cdot |Y|}{|g^{-1}(x)|}-\sum _x\frac{|g_{x\times Y}^{-1}(z)|}{|g^{-1}(z)|}{\log }_2\frac{|X|\cdot |g_{x\times Y}^{-1}(z)|}{|g^{-1}(z)|}-\sum _y\frac{|g_{X\times y}^{-1}(z)|}{|g^{-1}(z)|}{\log }_2\frac{|Y|\cdot |g_{X\times y}^{-1}(z)|}{|g^{-1}(z)|}$$

$$={\log }_2\frac{1}{g^{-1}(z)}-\sum _{(x,y)\in g^{-1}(z)}\frac{1}{|g^{-1}(z)|}\cdot {\log }_2\frac{|g_{X\times y}^{-1}(z)|}{|g^{-1}(z)|}\cdot \frac{|g_{x\times Y}^{-1}(z)|}{|g^{-1}(z)|}.$$

Entanglement quantifies how far the size of the pre-image of$g^{-1}(z)$ deviates from the sizes of its $X\times y$ and$x\times Y$ slices as $x$ and $y$ are varied.$\mathrm{■}$

By Corollary 8 (http://planetmath.org/4measurement#Thmthm8)entanglement also equals $ei({𝔪}_{X\bullet }\to {𝔪}_{XY},{\delta }_z)-ei({𝔪}_{\bullet Y},{\delta }_z)$. InDiagram (11) (http://planetmath.org/4measurement#id2)entanglement is the vertical arrow minus both arrows at thebottom, or the difference between opposing diagonal arrows.Note that the diagonal arrows from left to right areconstructed by adding edge $v_Y\to v_Z$ to the nullsystem and the subsystem ${𝔪}_{X\bullet }=\{v_X\to v_Z\}$ respectively. Entanglement is thedifference between the information generated by the diagonalarrows. It quantifies the difference between the information$\{v_Y\to v_Z\}$ generates in two different contexts.

Corollary 11 (characterization of disentangled set-valued functions).

Function $X\mathrm{\times }Y\stackrel{𝑔}{\mathrm{\to }}Z$ performs adisentangled measurement when outputting $z$ iff

$$g^{-1}(z)=g_{x\times Y}^{-1}(z)\times g_{X\times y}^{-1}(z)$$

for any $x\mathrm{,}y$ such that $g\mathit{}\mathrm{(}x\mathrm{,}y\mathrm{)}\mathrm{=}z$.

Proof:By Theorem 10 entanglement is zero iff

$$|g^{-1}(z)|=|g_{x\times Y}^{-1}(z)|\cdot |g_{X\times y}^{-1}(z)|$$

for any $x,y$ such that $g(x,y)=z$. This implies the desiredresult since $g^{-1}(z)\hookrightarrow g_{x\times Y}^{-1}(z)\times g_{X\times y}^{-1}(z)$.$\mathrm{■}$

Thus, the measurement generated by $g$ is disentangled iff itspre-image $g^{-1}(z)$ satisfies a strong geometric“rectangularity” constraint: that the pre-image decomposesinto the product of its $x\times Y$ and $X\times y$ slices forall pairs of slices intersecting $g^{-1}(z)$. Thecategorizations performed within a disentangled measuringdevice have nothing to do with each other, so that the deviceis best considered as two (or more) distinct devices thathappen to have been grouped together for the purposes ofperforming a computation.

Example 4.

An XOR-gate $g:X\times Y\to Z$ outputting 0generates an entangled measurement. The pre-image is$g^{-1}(0)=\{00,11\}$ so the XOR-gate generates 1 bitof information about occasions $v_X$ and $v_Y$. However,the bit is not localizable. The measurementgenerates no information about occasion $v_X$ taken singly,since its output could have been 0 or 1 with equalprobability; and similarly for $v_Y$.

Finally, and unsurprisingly, a function is completelydisentangled across all its measurements iff it is aproduct of two simpler functions:

Corollary 12 (completely disentangled functions are products).

If $X\mathrm{\times }Y\stackrel{𝑔}{\mathrm{\to }}Z$ is surjective, then
$\gamma \mathit{}\mathrm{(}{\mathrm{m}}_{X\mathit{}Y}\mathrm{,}\mathrm{P}\mathrm{,}{\delta }_z\mathrm{)}\mathrm{=}\mathrm{0}$ for all $z\mathrm{\in }Z$ iff $g$decomposes into $X\mathrm{\times }Y\stackrel{g_{\mathrm{1}}\mathrm{\times }{g}_{\mathrm{2}}}{\mathrm{\to }}{Z}_{\mathrm{1}}\mathrm{\times }{Z}_{\mathrm{2}}\mathrm{=}Z$ for $X\stackrel{g_{\mathrm{1}}}{\mathrm{\to }}{Z}_{\mathrm{1}}$ and$Y\stackrel{g_{\mathrm{2}}}{\mathrm{\to }}{Z}_{\mathrm{2}}$.

Proof:The reverse implication is trivial.In the forward direction, note that $Z=\{g^{-1}(z)|z\in Z\}$and, by Corollary 11, each pre-image has productstructure $g^{-1}(z)=g_{x\times Y}^{-1}(Z)\times g_{X\times Y}^{-1}(z)$. Let $Z_1=\{g_{X\times y}^{-1}|y\in Y\text{ and }z\in Z\}$ and similarly for $Z_2$. Define

$$g_1:X\to Z_1:x\mapsto \text{the unique element ofform }{g}_{X\times y}^{-1}(z)\text{ containing it,}$$

and similarly for $g_2$.