The entailment between separation logic formulae with inductive predicates (also known as symbolic heaps) has been shown to be decidable for a large class of inductive definitions. Recently, a 2EXPTIME algorithm has been proposed, however no precise lower bound is known (although a EXPTIME-hard bound for this problem has been established). In this paper, we show that deciding entailment between predicate atoms is 2EXPTIME-hard. The proof is based on a reduction from the membership problem for exponential-space bounded alternating Turing machines.