Will quantum computing threaten Bitcoin and other cryptocurrencies?

It has often been stated that quantum computing will end all cryptocurrencies because quantum computers just magically break every cryptography - simply because they are quantum computers. Let's have a look at how this turns out in reality and what kind of threat quantum computing really poses to Bitcoin and it's relatives.

What are quantum computers?

TA quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. The basic principle behind quantum computation is that quantum properties can be used to represent data and perform operations on these data. A theoretical model is the quantum Turing machine, also known as the universal quantum computer.
Although quantum computing is still in its infancy, experiments have been carried out in which quantum computational operations were executed on a very small number of qubits (quantum bit). Both practical and theoretical research continues with interest, and many national government and military funding agencies support quantum computing research to develop quantum computers for both civilian and national security purposes, such as cryptanalysis.

Note that the abbreviation QC can stand for either quantum computer(s) or quantum cryptography.

What threats quantum computers pose to cryptography?

The most widely feared use-case for quantum computers is that they will be used to crack public-key cryptography - this is what is used to sign your bitcoin transactions. On traditional binary computing machines, it takes 2^128 computing operations to get the Bitcoin private key associated with a Bitcoin public key. This number seems small to look at but is so large in reality that any attempt to crack a Bitcoin private key using binary computers is doomed to fail. For quantum computers, there is a process called "Shor's Algorithm" that would could this effort down to about 128^3 operations, which is a much smaller number.

For symmetric cryptography - which is what is used to mine blocks in Bitcoin and any other "Proof-of-Work" system, quantum attacks exist as well but are much less effective.
The fastest attack known to date is called Grover's Algorithm-
Utilizing this, the number of operations required to attack symmetric cryptography is cut by a square root factor. That means to attack the SHA-256 algorithm used in Bitcoin mining, it would take 2^256 operations on a binary computer but 2^128 operations on a quantum computer. Both of these numbers are still impractically large for systems currently in existence and will probably stay so for many, many years to come. Since Bitcoin mining is, in essence, a brute force attack against symmetric cryptography, it is unlikely to ever be exploited by quantum computers. This is always a function of computing power versus cost. As quantum computers will likely stay expensive for very long, it will probably not be economical to put up quantum miners in place of traditional binary miners (the ASICs of today) In such a sense, the mining of Bitcoin is already "quantum resistant" without any special measures.

Timeline

Creating a quantum computer is a massive challenge for engineers today. In this year 2017, the largest general purpose quantum computers can only operate on 10 qubits, which is by far too small to do any meaningful attacks on cryptography. Using Shors Algorithm would require between 1000 and 2000 qubit quantum computers to be built, which are probably quite a while away. A rough estimate for when this technology will be available are the years 2030 to 2040.

Possible ways to keep crypto quantum secure

As we have already found out, Bitcoin already has a certain kind of quantum resistance in it's mining. The sensible point is your Bitcoin wallets public and private keys. These are only exposed when you send transactions, by signing a transaction to go to a specific address. If you practice adress re-use and don't use your Bitcoin adresses more than one time (which is recommended anyway) then your public key is only revealed for this one instance. A quantum computer computer likely will not ever be able to break your public key in the timespan it takes for your transaction to be enscribed into a block. At least not in a timespan that will matter to you. It will likely still be several many decades before quantum computers will be this fast. If you keep in mind that traditional cryptography used in bitcoin has only been around for 5-7 decades so far, it is likely we will have found better technology for public key cryptography by then and implemented this into Bitcoin.

There is already such a system, in fact, currently favored by Bitcoin developers. These are called Lamport signatures.
These could be implemented into the existing Bitcoin software as a softfork. From an end-uses viewpoint, this would appear as the creation of a new address type, and everyone would need to send their bitcoins to this new address type to achieve quantum security. Simple, isn't it?