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


#from Google notation

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

#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)

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

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

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

def xel(p,q):
    """linear cross entropy of two distributions"""
    for k in range(len(p)):
        S= S + (p[k] * q[k])
    return D*S -1

def xe(p,q):
    """cross entropy"""
    for k in range(len(p)):
        if q[k]==0:
        S = S - q[k] * np.log(p[k])
    return S

def S(p):
    """ Entropy of probability density vector """
    for k in range(len(p)):
        if p[k]==0:
        S = S - p[k]* np.log(p[k])
    return S

def purity(p):
    """ linear entropy """
    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(" ")
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

2 Answers 2


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.


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").

  • $\begingroup$ I read it but it gives no hints on the derivation of the linear XEB from the XEB and I cannot find the factor of D that's given. I found numerically that F=0 for the uniform distro using the given form of the linear XE. Moreover, from reading the appendix several times, it is still unclear (to me) how linear XE is derived or even connected to XE. $\endgroup$ Apr 11, 2022 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.