Small Quantum Signatures - Reality check needed
I see two problems with this idea.

The first problem is Shor's algorithm; that's a quantum algorithm that is able to find the cycle length of a group (and if you can solve that problem, it is easy to factor and compute discrete logs).  In this case, if we define the group of elements defined by the initial start state in the signature, where $H^n$ is the initial state stepped $n$ times (with the group operation defined as $H^a + H^b = H^{a+b}$), Shor's algorithm should be able to find the cycle length of the group, and as you point out, that allows the attacker to reverse the operation.  The only defense I can see it to deliberately select an operation where the above is a semigroup; that is, where the set of elements $H^n$ never come back to the initial state $H^0$, but instead hits a loop later on (and so the first collision $H^x = H^y$ occurs with $x, y &gt; 2^{256}$).  I don't know how you would ensure that.

The second problem I foresee is the mathematical structure that you would need within your PRNG; to be able to compute $H^n$ in $o(n)$ time, you need quite a bit of mathematical structure within your PRNG; I would worry that such structure could be exploited by an attacker.  For example, in your case of multiplying by a noninvertable matrix, I believe that an attacker can just look at the subspace defined by the nonintertable matrix, and effectively step backwards (by looking only for solutions that are within that subspace).  There are methods that appear to be strong against classical computers (e.g. squaring modulo a hard to factor composite), but the ones I can think of run into issues against a Quantum Computer.

Bottom line: I don't believe the idea's quite dead; I do see a number of difficulties in the path.