Programming Quantum Computers

Chapter 12. Shor’s Factoring Algorithm

If you’d heard about one application of quantum computing before you picked up this book, there’s a good chance it was Shor’s factoring algorithm.

Quantum computing was mostly considered to be of academic, rather than practical, interest until Peter Shor’s 1994 discovery that a sufficiently powerful quantum computer can find the prime factors of a number exponentially faster than any conventional machine. In this chapter, we take a hands-on look at one specific implementation of Shor’s QPU factoring algorithm.

Far from being a mere mathematical curiosity, the ability to quickly factorize large numbers can help break the Rivest–Shamir–Adleman (RSA) public-key cryptosystem. Anytime you spin up an ssh session you’re making use of RSA. Public-key cryptosystems like RSA work by a process wherein a freely available public key can be used by anybody to encrypt information. But once encrypted, the information can only be decrypted using a secret, privately held key. Public-key cryptosystems are often compared to an electronic version of a mailbox. Imagine a locked box with a slit allowing anyone to post (but not retrieve) a message, and a door with a lock to which only the owner has the key. It turns out that the task of finding the prime factors of a large number N works really well as part of a public-key cryptosystem. The assurance that someone can only use the public key to encrypt and not to decrypt information rests on the assumption that finding ...