Here’s my idea to protect POW cryptocurrencies from a quantum attack. I’m posting it here in case I have come up with something novel.
TL;DR Protect crypto transactions from quantum attack by using a “key-pair chain” and timelocks to allow fraudulent transactions to be undone.

Suppose Alice creates a random seed, then uses it to create a public/private key pair. Then she takes this public key and uses it as the seed for a new key pair, and then creates another key pair from the latest public key and so on. She ends up with a list of key pairs, and she uses the last pair to create an address in a crypto-currency.

When Alice spends from her address, someone with a quantum computer cracks her exposed public key, and manages to get a fraudulent transaction published to the blockchain before the real one. This is not a problem as Alice’s address is set up with a time lock, giving a time period where generating key pairs can be used to override any transactions. So Alice just needs to create a new transaction and sign it with her penultimate key pair (with a suitably high fee) to get control of her crypto-coins back.

This technique gives Alice protection against a quantum attack. However the attacker could just try again. To get round this, the keys in the key pair chain are not the same. The key at the end is standard encryption strength, the one before is stronger, and the one before that is even stronger. The original key pair can be an implementation of a quantum ‘safe’  signature (e.g. Lamport signatures). So the attacker knows that if they mange to get their fraudulent transaction published, it will just be replaced with a transaction that is much harder to forge, so it is probably not worth trying.

Note that there is an issue with the transaction fee for the forged transaction. If the miner keeps the fee it can be used as a mechanism to siphon off Alice’s funds. If the fee goes to Alice, then people could use the transaction overrides as a cheap way to put data on the blockchain. So there probably needs to be some sort of compromise or fee restriction.

In summary, this technique allows a cryptocurrency to have the security of large signatures, but without increasing the size of data on the blockchain (unless there is an actual attack). The penalty for this security is an increase in the time receivers have to wait for transactions to confirm.