Truncated Modular Exponentiation Operators: A Strategy for Quantum Factoring

Abstract

Modular exponentiation (ME) operators are one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. These operators are often referred to as the bottleneck of the algorithm. I propose a method for constructing the ME operators that requires only $3n + 1$ qubits with no ancillary qubits. The method relies upon the simple observation that the work register starts in state $\vert 1 \rangle$. Therefore, we do not have to create an ME operator $U$ that accepts a general input, but rather, one that takes an input from the periodic sequence of states $\vert f(x) \rangle$ for $x \in \{0, 1, \cdots, r-1\}$. Here, the ME function with base $a$ is defined by $f(x) = a^x ~({\textrm mod}~N)$ and has a period of $r$. For an $n$-bit number $N$, the operator $U$ can be partitioned into $r$ levels, where the gates in level $x \in \{0, 1, \cdots, r-1\}$ increment the state $\vert f(x) \rangle = \vert w_{n-1} \cdots w_1 w_0 \rangle$ to the state $\vert f(x+1) \rangle = \vert w_{n-1}^\prime \cdots w_1^\prime w_0^\prime\rangle$. The gates below $x$ do not affect the state $\vert f(x+1) \rangle$. This amounts to transforming an $n$-bit binary number $w_{n-1} \cdots w_1 w_0$ into another binary number $w_{n-1}^\prime \cdots w_1^\prime w_0^\prime$, without altering the previous states, which can be accomplished by a set of formal rules involving multi-control-NOT gates and single-qubit NOT gates. The process of gate construction can therefore be automated, which is essential for factoring larger numbers. The obvious problem with this method is that it is self-defeating: If we knew the operator $U$, then we would know the period $r$ of the ME function, and there would be no need for Shor's algorithm. I show, however, that the ME operators are very forgiving, and truncated approximate forms in which levels have been omitted are able to extract factors just as well as the exact operators. I demonstrate this by factoring the numbers $N = 21, 33, 35, 143, 247$ by using less than half the requisite number of levels in the ME operators. This procedure works because the method of continued fractions only requires an approximate phase value, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. This is the basis for a factorization strategy in which one level at a time is iterated over using an automated script. In this way, we fill the circuits for the ME operators with more and more gates, and the correlations between the various composite operators $U^p$ (where $p$ is a power of two) compensate for the missing levels. Quanta 2024; 13: 47–82.