On estimating the entropy of shallow circuit outputs
arXiv:2002.12814
Abstract
Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. Here, we examine the hardness of this task for the case of probability distributions or quantum states produced by shallow circuits. Specifically, we show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors (LWE) problem, and thus believed to be intractable even for efficient quantum computation. This illustrates that quantum circuits do not need to be complex to render the computation of entropy a difficult task. We also give complexity-theoretic evidence that this problem for log-depth circuits is not as hard as its counterpart with general polynomial-size circuits, seemingly occupying an intermediate hardness regime. Finally, we discuss potential future applications of our work for quantum gravity research by relating our results to the complexity of the bulk-to-boundary dictionary of AdS/CFT.
Substantial changes with respect to v1. Fixed typos, small bugs and updated references. Clarified that our results apply for circuits with unbounded fan-out gates. Included a version of the entropy estimation problem, known as the entropy ratio problem, for which we proved similar hardness results. Added discussion on follow-up works which introduced the notion of quantum pseudoentanglement
References in corpus (18)
- Holographic Derivation of Entanglement Entropy from AdS/CFT
- Concentrating Partial Entanglement by Local Operations
- Area laws for the entanglement entropy - a review
- Entanglement Renormalization and Holography
- Measuring Renyi Entanglement Entropy with Quantum Monte Carlo
- The Ryu-Takayanagi Formula from Quantum Error Correction
- Hamiltonian simulation with nearly optimal dependence on all parameters
- A Sharp Fannes-type Inequality for the von Neumann Entropy
- Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem?
- Maximum Likelihood Estimation of Functionals of Discrete Distributions
- The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
- Polynomial time quantum computation with advice
- Classical Hardness of Learning with Errors
- Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
- Depth-efficient proofs of quantumness
- Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality
- Quantum Depth in the Random Oracle Model
- Distinguishing Short Quantum Computations