Shor's Algorithm

Although my previous post, Quantum Computers, was only a low level introduction to the subject, it piqued my interest. I ended that post with a vague objective for a follow-up:-

In my next post I'll try to learn more about quantum algorithms.

I continued watching videos and quickly discovered that the algorithm with a direct impact on bitcoin is Shor's algorithm (Wikipedia):-

Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization formulated in 1994. Informally it solves the following problem: given an integer N, find its prime factors. On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time (the time taken is polynomial in log N, which is the size of the input).

Next I found a short video on Youtube starring Peter Shor, What is Shor's factoring algorithm?, but it's much too short to explain the subject properly. Another video, Shor's Algorithm, looked more promising, but required knowledge of math concepts that I wasn't familiar with. Fortunately, it was the last clip in a course playlist, Intro to Quantum Computing (no.23/23), that covered the math from the start. From the first videos in the course, I learned that quantum mechanics are based on linear algebra, a subject I studied many years ago when I was still capable of learning complicated new things.

Although I wasn't able to complete the intro course before writing this post, I found another video that explained the algorithm using more basic math. After one full viewing, I can't say that I've grasped it completely, but I'll watch it a few more times until it sinks in.

44 Quantum factoring : Shor's factoring algorithm (25:42) • 'Quantum Mechanics and Quantum Computation'

The Youtube page for that clip says, 'Published on Nov 26, 2016', which is the date on this current post. (How lucky is that?) It's part of another course playlist, Quantum Mechanics and Quantum Computation, that currently stops at '43 Quantum factoring : Period finding', so I assume it will be updated wth the new clip(s) in due time.

From all of this it looks like the cryptographic underpinnings of bitcoin might indeed be at risk in the not-too-distant future, especially if there is an equivalent of Moore's law that applies to quantum computer hardware. Not to worry too much, because Quantum cryptography (Wikipedia) promises a parallel evolution:-

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution which offers an information-theoretically secure solution to the key exchange problem. Currently used popular public-key encryption and signature schemes (e.g., RSA and ElGamal) can be broken by quantum adversaries. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical (i.e. non-quantum) communication.

With all of that in mind, I'll continue any further investigation of the quantum world outside the confines of this blog. After two posts on a quantum detour, I'm ready to return to the main subject: bitcoin.