NMR Experiment Factors Numbers with Gauss Sums

We factor the number 157573 using an NMR implementation of Gauss sums. Although the current implementation is classical and scales exponentially, we believe that an extension to the quantum regime using entangled states is possible.

Figure 1

Factorization interference pattern for $N=157573=13\times 17\times 23\times 31$ obtained from the Gauss sum ${\mathcal{A}}_N^{(M)}$ (black dots) and from the Gauss sum ${\overline{\mathcal{C}}}_N^{(M)}$ corresponding to damping (circles). In both cases, already $M+1=11$ terms are sufficient to clearly discriminate the factors from nonfactors. Note the different scales for ${\mathcal{A}}_N^{(M)}$ and ${\overline{\mathcal{C}}}_N^{(M)}$.

Figure 2

The contrast $\mathcal{V}$ of the factorization interference pattern of Fig. 1 as a function of the number $M$ of terms in the Gauss sum ${\mathcal{A}}_N^{(M)}$ for $N=157573$ (circles) and $N=4683359$ (black dots).

Figure 3

NMR implementation of our factorization scheme using Gauss sums. The $y$-pulse which prepares the initial density matrix ${\rho }_{\mathrm{in}}$ is followed after a time $\tau$ by a pulse which imprints the phase ${\varphi }_0$ on the spins. This pulse is the first of a sequence of $M+1$ pulses, each imprinting a different phase ${\varphi }_m$. At times ${\tau }_m+\tau \equiv (2m+1)\tau +\tau$, we measure the echo, that is, the polarization $s_m$ in $x$-direction and sum the echoes $s_m$ over all $m$ to obtain $S^{(M)}$. In order to implement a Gauss sum, the phases ${\varphi }_m$ need to be proportional to the number $N$ to be factored and have to increase linearly as a function of $m$ since the spin dynamics expressed by $s_m$ depends on the sum over all phases of the previous pulses.

Figure 4

Experimental realization of factoring $N=157573=13\times 17\times 23\times 31$ using the NMR implementation of the Gauss sum ${\overline{\mathcal{C}}}_N^{(M)}$. In the top and bottom, we depict the echo height $s_m$ measured at times ${\tau }_m+\tau$ and the resulting average ${\overline{\mathcal{C}}}_N^{(M)}$ for different trial factors $\ell$, respectively. For factors such as $\ell =17$, the signals $s_m$ are approximately constant as a function of $m$ with an average value ${\overline{\mathcal{C}}}_N^{(M)}(17)$ close to unity. In contrast, for a nonfactor such as $\ell =18$, $s_m$ oscillates around zero and when summed over $m$, almost averages out as indicated by the arrow.

Figure 5

Probing the limits of our factorization scheme. Factorization interference pattern for the 24-digit number $N=1062885837863046188098307=pq$ obtained from a numerical simulation of the Gauss sum ${\mathcal{A}}_N^{(M)}$ in the immediate neighborhood of the prime factor $p=790645490053$ for $M=200$. Here, we encounter several ghost factors ${\ell }_g$ with $1/\sqrt{2}<|{\mathcal{A}}_N^{(M)}({\ell }_g)|<1$.