Simulating QPE + Grover using Low-Rank Stabilizer Decomposition

I agree that the Bravyi et al. paper is not easy to understand and they should have made some reference implementation available.

Without going into details, I don't think it is likely to get an improvement. For Grover alone, you need to do $O(2^{n/2})$ steps and in each step, you basically do a rotation. This rotation is very unlikely to be Clifford, thus you apply $O(2^{n/2})$ non-Clifford gates. Any stabiliser-based simulation method eventually scales exponentially with the number of non-Clifford gates. Thus, this should explode very fast.

(Well, this should hold for any simulation method in this context).

So as long as you don't find a smart recompilation which reduces the "magic" in the circuit (which is probably highly non-trivial), I would say that there is not much to gain.

Perhaps, you could have a look at the very recent paper by Hakop Pashayan et al. There is also a QIP talk on Youtube from last week.

Their technique is quite unique and might get you somewhere. So far, I cannot really judge how far, because I don't understand it well enough. But, they provide an implementation of their algorithm on github (Ref. [35] in their paper).