Derivation of the linear cross entropy

Question

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

#from Google notation
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

Answer 1

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.

The form is motivated by this benchmark taking the value 1 when the samples are obtained from sufficiently random circuits (Porter-Thomas) and taking the value 0 if the samples are uniformly random.

Answer 2

the reasoning behind this definition is explained in section IV in the SI of the supremacy paper. To me at least the simplest way to get a feeling for this definition is that it will give F=0 for a uniform distribution and F=1 for a Porter Thomas distribution (see "two limiting cases").