← blog or something

21

At the end of 2025, I had decided that I wanted to factor 21. Not in a classical-quantum hybrid way, or in a compiled way, but with a pure quantum algorithm and an uncompiled oracle/circuit on a real QPU.

The inspiration was a blog by Craig Gidney: Why haven’t quantum computers factored 21 yet?

Could I factor 21 with a pure quantum algorithm with an uncompiled circuit on a NISQ device? I had some ideas.

Who said that the algorithm had to be scalable? I didn’t, neither was I motivated to look for a quantum advantage over Shor’s algorithm or Regev’s improvement. With that in mind, I decided I was going to look for a pure quantum algorithm that should scale badly, but at least allow me to factor 21 on today’s NISQ hardware.

I had worked on the number theory side of Shor’s algorithm, so I decided to have a look at it again. Picking a random base aa with gcd⁡(a,N)=1\gcd(a, N) = 1, and finding the even period rr where ar/2≢±1(modN)a^{r/2} \not\equiv \pm 1 \pmod{N}, which ultimately factors NN. Hmmm.

I thought, “what if I look for a specific base with a specific period rr? What if I search for the successful base with the period r=2r = 2? Surely, that’s proven by CRT that there will always be 2 successful bases with the period 2 when pp and qq are odd and distinct.”

Okay, so what will my algorithm do? Find the base with the period 2. How? Take all the bases from 1<a<N1 < a < N, square them, take mod NN, and find where it equals to 1.

Is it a pure quantum algorithm? If the modular arithmetic is a quantum step, yes. Also, does the algorithm require any knowledge of pp or qq? Nope.

It chooses a random base aa like Shor. It does the modular arithmetic as a quantum step. Doesn’t need a QFT though. Has conditions that aa has to meet, like Shor. Shor’s base is successful approximately 50% of the time when chosen randomly. This algorithm has a probability much worse which decreases as NN scales. It’s extremely inefficient, as it needs to try almost NN bases for the algorithm to succeed.

What would the quantum circuit implementation look like?

At first I thought of doing the quantum modular squaring subroutine for all aa in superposition and then applying Grover’s to find the bases with the period 2. That didn’t seem like it would be possible on a NISQ device by a huge margin.

Well, after months of ignoring this problem, I realised in a shower that the algorithm allows decomposition! f(a)=[a2≡1(modN), a≠±1]f(a) = [a^2 \equiv 1 \pmod N,\ a \neq \pm1] is local: it depends only on aa and the constant NN. The circuit could just do a range of aa at a time rather than all aa at once, breaking down into subcircuits for each range, possibly reducing the expensive modular squaring subroutine circuit and the Grover’s subroutine. I could even do one aa at a time, which just avoids the entire Grover’s subroutine as well.

Hence, I am here to write about it. I do not know if it will work, but I have hope.