Adventures in quantum factoringIt all started this summer when I finally got round to participating in this year's edition of
Q# Coding Contest (Q# is a pretty slick
F#-inspired programming language for developing quantum algorithms by Microsoft). Most of the challenges they wanted us to solve were entertaining, but kind of anticlimactic -- I mean, checking if a number is divisible by 3 is fun, but that's not exactly the problem we really need quantum computers for. Sometime after the contest, my curiosity got the best of me, and I started to think if I could find a small but useful algorithm in the Q# documentation that I could implement on my own to get a sense of what real quantum programming looks like.
This is where it hit me -- I may not know or care much about quantum chemistry and Hartree–Fock theory, but I'm fond of cryptography, and
post-quantum crypto is all the rage these days. To understand why exactly we suddenly need to deprecate basically all currently deployed public-key crypto, I set out to implement
Shor's algorithm for the quantum simulator built into Q# to try and break RSA factor small integers.
When I was doing preliminary research, I stumbled upon a
paper with a poignant title that showed how easy it is to (intentionally or accidentally) cheat by creating a specialized quantum circuit for factoring a particular integer if you already know its factors. Naturally, I wanted to avoid that and implement a fully general algorithm. I was also determined to use as few qubits as possible because I hoped to eventually factor 15 (or 21 if I get fortunate) on real quantum hardware. With that in mind, I found a beginner-friendly
paper that looked sufficiently close to SOTA in terms of the number of qubits used and got to work.
In contrast to the Q# Coding Contest challenges, Shor's algorithm has a non-trivial classical part that has to run on a regular computer. In fact, the algorithm is not really about factoring; it's about finding a period of f(x) = a^x mod n. So first you have to do a bunch of work to recast factoring in terms of period finding, and then use the period p you found to identify the factors you are after. It gets a little involved because what you actually get from the quantum part of the algorithm is not p proper but an approximation to x/p (where x is a number less than p), but all in all, the classical part is not terribly exciting.
Not surprisingly, the exciting part is the quantum circuit for period finding. There's a really beautiful algorithm called Quantum Phase Estimation (see
this excellent book for more details) that says you can accurately estimate the eigenvalue of a quantum operator by preparing an eigenstate, applying the operator a few times controlled on a qubit that is in an equal superposition of basis states, applying an inverse Fourier transform, and then measuring. For period finding, the quantum operator is simply the modular multiplication modulo n. However, it turns out that, while quantum computers excel at computing Fourier transforms, they are astonishingly bad at such complex operations as
checks notes adding two numbers together modulo another number, since all quantum operations have to be reversible, which means you have resort to tricks such as dummy quantum registers that are always set to zero (and sure enough, more Fourier transforms).
Debugging this is even harder than debugging CUDA code, but it feels like magic when it finally works. My initial implementation would give me periods that kinda sorta looked right (hard to tell, it's an approximation after all), but then I looked through my code and found that I messed up the order of bits when rotating qubits. When I fixed that, the periods suddenly started to look exactly right; at that moment, I gasped quite literally and audibly.
