On Estimating the Entropy of Shallow Circuit Outputs

Computing the entropy of probability distributions and quantum states is a fundamental task in information processing. In this talk I'll discuss recent work with Matty Hoban (arXiv:2002.12814) in which we show that estimating the entropy of quantum states (or probability distributions) produced by shallow quantum circuits is at least as hard as the Learning-With-Errors problem, and thus believed to be intractable for efficient quantum computation. This shows that circuits do not need to be complex to render the computation of entropy a difficult task. We also give complexity-theoretic evidence that the problem is not as hard as its counterpart with general polynomial-size circuits, seemingly occupying an intermediate hardness regime. As a potential application to quantum gravity research, we relate these results to the complexity of the bulk-to-boundary dictionary of AdS/CFT.