Back in the 80’s when quantum computers were being modeled by names such as Yuri Manin and Richard Feynman, no one was really seeing it as a threat, not only because it was really far from actually being a real working quantum computer (even traditional computers were not something to write home about in that time), but because cryptography was only taking its first steps, and, for the next two decades, it was reserved only for banking and other sites which required a very strong level of security. Nowadays, cryptography is everywhere, any major website or application probably uses it. It is also, of course, the foundation of cryptocurrencies.
Public key cryptography, the kind which is used in cryptocurrencies, works by assigning pairs of public keys to private keys. The public key encrypts the message and the private key decrypts it. Only the private key which is paired with the public one can decrypt a message sent in the public key “language”. Finding one private key based on another public key is, surprisingly, not physically impossible, although currently unachievable utilizing our current best computer power capabilities. To hack a key, a very powerful computer would have to solve one of the three hard problems which cryptography currently relies on: the integer factorization problem, the discrete logarithm problem, or the elliptic-curve discrete logarithm problem. These problems are so hard that there’s not even enough energy in our solar system which could power an ideal supercomputer to solve them.
Now, 14 years after the theoretical quantum computer models was proposed, an algorithm which would only work on such devices, called the Shor’s algorithm, was formulated by Peter Shor. This algorithm solves the following problem: given an integer N, find its prime factors. This is a condition sufficient to solve those hard problems and break most public-key cryptography systems currently used. No classical computer could run such algorithm, so there’s currently not one computer which could hack your Bitcoin wallet.
Quantum computers, instead, are immensely more powerful than the classical ones. Instead of working with series of binary states called bits (that can be 0 or 1) like classical computers, which ultimately are translated into information, they use quantum bits (qubits), which are series of not only 0 and 1 states, but superpositions of them, a technology based on quantum mechanical phenomena. While some algorithms would require an unreasonable number of bits to run, they would do the same thing using much fewer qubits, as a string of information in qubits would be much shorter than one using bits.
While quantum computing used to only be plausible on paper, people knew it was a matter of time before those machines would be actually put into practice, so post-quantum cryptography conferences (called PQcrypto) have been held since 2006 to discuss possible solutions to the quantum threat.
Before some events that happened last year, the data science community has been very chilled about this issue, because, despite the effort put forward by several companies and institutions, none of them was slightly close to building a working quantum computer.
In 2016, though, IBM announced that they have launched a five-qubit processor, a machine that, although not being powerful enough to surpass the computational power of some very powerful classical computers, proved that quantum computing could, indeed, get off the drawing board. In May 2017, they eventually launched a 20-qubit quantum computer which is available for experiments through their IBM quantum experience program. Additionally, the head of Google’s quantum computing team, Harmut Neven, promised last year that they were to release a 49-qubit system within, at most, 12 months.
Today’s top classical supercomputers would be able to simulate, at most, the power of a 20-qubit computer. 49-qubits is an impressive increase, a computer capable of so much power no super powerful supercomputer could even come close. Academic and corporate quantum researchers expect that, within two to five years from now, 30 to 100 qubit quantum computers are likely to be available for sale.
This makes the alarm bells start to ring for public key protected systems vulnerable to quantum attacks, which are, as of today, most of them. Some cryptocurrencies and other cryptography protected applications are already implementing post-quantum cryptography measures to preclude these attacks. However, no one knows exactly when they are going to be viable. Post-quantum cryptography utilizes algorithms much more complex than the traditional ones and is thought to be secure against quantum computing hacks.
After cryptocurrencies gained so much buzz in 2017, quantum computing has everything to be the new hype. Similar to Bitcoin, which was released in 2009, but became mainstream only in the last couple years, quantum computing is already here, but people will probably only start talking about it when the going gets tough.