# Derivation of the linear cross entropy

I'm looking at cross-entropy benchmarks and there's much that I'm reading at the moment but I'm stuck on one detail: how to derive the linear cross-entropy formula from the cross-entropy formula.

The cross-entropy of probability densities $$p(x)$$ and $$q(x)$$ over $$D=2^N$$ possible values of $$x\in \{0,1\}^N$$ is given by

$$-\sum^D q(x) \log p(x)$$

I took the linearization of the log function $$\log (x) = x-1$$ in an attempt to get the linear cross entropy (following the derivation of Linear entropy). As the linearization, I obtain

$$-\sum^D q(x) (p(x) -1) = 1 -\sum^D q(x) p(x)$$

In both "Quantum supremacy using a programmable superconducting processor" and "Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage" [arXiv:2112.01657] the linear cross-entropy is given as

$$D\sum_{x}^{D} q(x) p(x) -1$$

1. I have no idea why my sign is off and where the pre-factor of $$D$$ comes from. I can recover the linear XEB formula if $$\log(p(x))\approx 1-D p(x)$$. However, I don't know how I can get the factor of $$D$$ to appear in any sensible approximation.

2. I tested some numerics and the XE and the linear XE do not appear to follow the same trends. I did an interpolation from $$q_{s=0} = p$$ to $$q_{s=1}=unif$$ in five steps and found that the XE increases as $$q$$ is further from $$p$$ while the linear XEB decreases to zero as $$q$$ approaches the uniform distribution. I think this is correct but I'm lost on the intuition/understanding of how the XE and linear XE are connected.

import numpy as np

#fix seed
np.random.seed(0)

#qubits
n=10

D=2**n
#print(D)

#print("Randomly choosen \ket p in basis \e")
#print(p)

#distro p
p = np.random.rand(D)
p = p / sum(p)

#distro q_s = (1-s) \ket p + s \ket Delta
Delta = np.random.rand(D)
Delta = Delta / sum(Delta)

#sharp
peaked = np.zeros(D)
peaked[np.random.randint(D)] =1.0

#unif
unif = np.ones(D)
unif = unif / sum(unif)

def getq(s,qmax=unif):
"""get q for a given mixing parameter s"""
if s>1:
s=1
if s<0:
s=0
return (1-s) * p + (s) * qmax

def xel(p,q):
"""linear cross entropy of two distributions"""

#sum
S=0

for k in range(len(p)):
S= S + (p[k] * q[k])

return D*S -1

def xe(p,q):
"""cross entropy"""
#sum
S=0

for k in range(len(p)):
if q[k]==0:
continue

S = S - q[k] * np.log(p[k])

return S

def S(p):
""" Entropy of probability density vector """
#entropy
S=0

for k in range(len(p)):
if p[k]==0:
continue

S = S - p[k]* np.log(p[k])

return S

def purity(p):
""" linear entropy """
#sum
S = 0

for k in range(len(p)):
S = S + p[k]*(p[k]-1)

return S

print("Entropy of \ket p", S(p))
print("Purity of \ket p",purity(p))
print(" ")
print("Entropy of \ket q_max",S(getq(1,qmax)))
print("Purity of \ket q_max",purity(getq(1)))
print(" ")

print("purity max", purity(unif))

svals = np.linspace(0,1,5)
for s in svals:
print("  s=",s)
q= getq(s,qmax)

print("xel_pq",xel(p,q))
print("xe_pq",xe(p,q))

#print("xel_qp",xel(q,p))
#print("xe_qp",xe(q,p))

print(" ")

s xel_pq xe_pq
0.0 0.3448222395967324 6.734095320988952
0.25 0.25861667969755 6.860293267333703
0.5 0.17241111979836532 6.9864912136784465
0.75 0.08620555989918333 7.112689160023204
1.0 1.9984014443252818e-15 7.238887106367953

In case anyone else gets caught up on this detail: I spoke to Soonwon Choi and he explained that the "linear" cross-entropy is not a linearization of the cross-entropy. Rather it is called linear'' since the components of $$p$$ appear linearly.