PoWs requiring billions of bits are pretty safe from QC quadratic speedup,
which is still struggling to work for mere dozens of qubits.
We have stopped on time-memory trade-off...
Not all TMTOs are linear...
Some PoWs need q^2 more time to use q times less memory,
which you cannot overcome with a quadratic quantum speedup.