  In this work, we use quantum complexity theory to quantify the difficulty of
distinguishing eigenstates obeying the Eigenstate Thermalization Hypothesis
(ETH). After identifying simple operators with an algebra of low-energy
observables and tracing out the complementary high-energy Hilbert space, the
ETH leads to an exponential suppression of trace distance between the
coarse-grained eigenstates. Conversely, we show that an exponential hardness of
distinguishing between states implies ETH-like matrix elements. The BBBV lower
bound on the query complexity of Grover search then translates directly into a
complexity-theoretic statement lower bounding the hardness of distinguishing
these reduced states.
