  Given a local Hamiltonian, how difficult is it to determine the entanglement
structure of its ground state? We show that this problem is computationally
intractable even if one is only trying to decide if the ground state is
volume-law vs near area-law entangled. We prove this by constructing strong
forms of pseudoentanglement in a public-key setting, where the circuits used to
prepare the states are public knowledge. In particular, we construct two
families of quantum circuits which produce volume-law vs near area-law
entangled states, but nonetheless the classical descriptions of the circuits
are indistinguishable under the Learning with Errors (LWE) assumption.
Indistinguishability of the circuits then allows us to translate our
construction to Hamiltonians. Our work opens new directions in Hamiltonian
complexity, for example whether it is difficult to learn certain phases of
matter.

Quantum Physics;Computational Complexity;Cryptography and Security