  The decision problem version of estimating the Shannon entropy is the Entropy
Difference problem (ED): given descriptions of two circuits, determine which
circuit produces more entropy in its output when acting on a uniformly random
input. The analogous problem with quantum circuits (QED) is to determine which
circuit produces the state with greater von Neumann entropy, when acting on a
fixed input state and after tracing out part of the output. Based on plausible
complexity-theoretic assumptions, both of these problems are believed to be
intractable for polynomial-time quantum computation. In this paper, we
investigate the hardness of these problems in the case where the input circuits
have logarithmic and constant depth, respectively. We show that, relative to an
oracle, these problems cannot be as hard as their counterparts with
polynomial-size circuits. Furthermore, we show that if a certain type of
reduction from QED to the log-depth version exists, it implies that any
polynomial-time quantum computation can be performed in log depth. While this
suggests that having shallow circuits makes entropy estimation easier, we give
indication that the problem remains intractable for polynomial-time quantum
computation by proving a reduction from Learning-With-Errors (LWE) to
constant-depth ED. We then consider a potential application of our results to
quantum gravity research. First, we introduce a Hamiltonian version of QED
where one is given two local Hamiltonians and asked to estimate the
entanglement entropy difference in their ground states. We show that this
problem is at least as hard as the circuit version and then discuss a potential
experiment that would make use of the AdS/CFT correspondence to solve LWE
efficiently. We conjecture that unless the AdS/CFT bulk to boundary map is
exponentially complex, this experiment would violate the intractability
assumption of LWE.
