If quantum computers become popular, what impact will it bring to Bitcoin and other existing cryptocoins?

PoW blockchain mining too. PoS/PoI/DPoS blockchains unaffected.

PoW blockchain mining too. PoS/PoI/DPoS blockchains unaffected.

I guess those would be unaffected but those projects would still need to swtich from ecdsa to something else that is "quantum secure" for all their signing right ?

PoW blockchain mining too.

 Also, a quantum computer doesn't need to evaluate a whole hash value, it can verify first bits and throw away nonces that don't suit with high probability.

BTW, why is Cuckoo Cycle less affected, birthday paradox problems are solved with N^(1/3) effort VS N^(1/2).

But Hashcash with large memory requirements will likely not be affected as long as scaling quantum computers up to millions of bits remains elusive.

I didn't find information on time-memory trade-off of quantum computers, but if we assume that the trade-off is not worse than the trade-off of classical computers then we get that memory increase of the hashing function can be counteracted by increasing time we run the computations. So Hashcash with large memory won't save us.

so that each single bits in one round depends on pretty much all bits of previous rounds.

That is a long document to read. Where exactly does it claim that?

I introduced a novel algorithm to solve the bitcoin mining problem without using (explicit) brute force. Instead, the nonce search is encoded as a decision problem and solved by a SAT solver in such a way that a satisfiable instance contains a valid nonce. The key ingredients in the algorithm are a non-deterministic nonce and the ability to take advantage of the known structure of a valid hash using assume statements.

A couple of benchmarks demonstrated that already with simple parameter tuning dramatic speed ups can be achieved. Additionally, I explored the contentious claim that the algorithm might get more efficient with increasing bitcoin difficulty. Initial tests showed that block 218430 with considerably higher difficulty is solved more efficiently than the genesis block 0 for a given nonce range.