Shor's Discrete Logarithm Algorithm with a QFT with a small prime base

Question

Suppose you replace both QFTs in Shor's discrete logarithm algorithm with simpler QFTs with small prime base w. Does this algorithm extract the discrete logarithm modulo w? It seems it does, provided you guarantee that the full discrete logarithm is not too large, and that the Hadamards in the second register only generate a smaller range of values, $max(b)$ such that $max(b)max(\alpha) < p-1$, where $\alpha$ is the full discrete logarithm. So for instance, if $max(b)$ = $max(\alpha)$ = $\frac{2^{\lfloor \log p \rfloor}}{64}$, then the modified Shor's algorithm will output $\alpha \mod w$. The modified Shor circuit will end in state:

$$ \sum_{c=0}^{2^{\lceil \log p \rceil}} \sum_{d=0}^{max(b)} \sum_{a=0}^{2^{\lceil \log p \rceil}} \sum_{b=0}^{max(b)} \exp(\frac{2 \pi i}{w}(ac+bd))|c,d,g^ax^{-b} \mod p\rangle $$

The restricted range of $b$ works for the following reason. If we write $y \equiv g^k$ (the power of $x$ can be written as a power of $g$), then $a-rb \equiv k \mod (p-1)$ and

$$ a = rb + k - (p-1)\lfloor \frac{br+k}{p-1} \rfloor $$

$a$ should have the entire range of $2^{\lceil \log p \rceil}$ and $b$ should be restricted to $max(b)$. This isn't a problem because any $a$ will have a $k$ which ranges from $0$ to $p-1$, so $a$ and $b$ will always have solutions. $r$ in the substitution should be chosen to be in the range $[0,max(r)]$ in order to avoid errors with taking the second modulus.

Following Shor, the amplitude is $$ \frac{1}{w\sqrt{ max(b)max(a)}} \sum_{b=0}^{max(b)} \exp\big( \frac{2\pi i}{w}(brc+kc+bd-c(p-1)\lfloor \frac{br+k}{p-1} \rfloor)\big) $$

Factor out a factor of $\exp(2\pi i \frac{kc}{w})$ that doesn't affect the probability and get

$$ \frac{1}{w\sqrt{ max(b)max(a)}} \sum_{b=0}^{max(b)} \exp(\frac{2\pi i}{w}bT)\exp(\frac{2\pi i}{w}V) $$ where $T = rc + d - \frac{r}{p-1}\{c(p-1)\}_w$ and

$V = \big( \frac{br}{p-1} - \lfloor \frac{br+k}{p-1} \rfloor\big) \{c(p-1)\}_w$

$V$ is automatically small as in the normal algorithm. For $T$, those $c,d$ such that $rc+d=0\mod w$ encode the period modulo $w$. $\frac{\{c(p-1)\}_w}{w} < 1$, so if $\frac{max(b)r}{p-1} << 1$ then the exponentials for all terms will be close to 1 for pairs $c,d$ such that $rc+d=0\mod w$, so that the $max(b)+1$ sums will all be constructive. If $rc+d \neq 0 \mod w$, then $\exp(\frac{2\pi i}{w}bT)$ will contain terms at least as "cycled through" as $\exp(\frac{2\pi i}{w}max(b))$, and destructive interference will guarantee their sum is nearly 0.

From the Chinese Remainder Theorem, multiple runs with different small primes can be used to reconstruct the entire discrete logarithm. Note that the small prime circuit has the same asymptotic complexity as the full discrete logarithm circuit and would require O(n) runs to construct the entire logarithm, so it would be much slower in practice. All notation is from Peter Shor's original paper, except for $\alpha$.

https://arxiv.org/abs/quant-ph/9508027

Answer 1

I'm going to change the notation slightly to make it a bit easier for me: I'll assume it's an arbitrary group of order $N$.

There is a minor mistake in your first equation, which is that the QFT will have different moduli for the different integers. That is, $a$ is an $n$-bit register, so the QFT will produce a phase modulo $2^n$, whereas $b$ is a $\lceil \lg w\rceil$ bit register to which you are applying a QFT modulo $w$. I will also assume the QFT on $a$ is done modulo $N$, as that makes the analysis much easier. This leaves a state of

$$\sum_{c=0}^{N-1}\sum_{d=0}^{w-1}\sum_{a=0}^{N-1}\sum_{b=0}^{w-1}\exp\left(2\pi i \left(\frac{ac}{N}+\frac{bd}{w}\right)\right)\left\vert c,d,g^k\right\rangle$$ where $a-rb\equiv k\mod N$.

I'll focus on the state corresponding to some fixed value of $k$. The set of states in superposition will be all $c$ and $d$, plus pairs $(a,b)$ in the set

$$K =\left\{(a,b) : a- rb\equiv k \mod N, 0\leq a \leq N-1, 0\leq b\leq w-1\right\}$$

In the usual Shor's algorithm, every value of $a$ (or $b$) is in a pair in this set, and for each one there is approximately one value of $b$ (or $a$) forming such a pair. Here, there will be many values of $a$ that are not in the set. But maybe that's fine, because for a fixed value of $b$, there will still be a unique value of $a$ such that $a\equiv k+rb\mod N$.

So, for a fixed $c, d, k$ we get

$$\sum_{b=0}^{w-1}\exp\left(2\pi i\left(\frac{(k+rb)c}{N}+\frac{bd}{w}\right)\right)\left\vert c,d,g^k\right\rangle$$

where I used the fact that powers of an $N$th root of unity are isomorphic to integers mod $N$.

Let $N'\equiv N^{-1}\mod w$ (assume $w$ and $N$ are co-prime):

$$=\exp(2\pi i\tfrac{kc}{N})\sum_{b=0}^{w-1}\exp\left(2\pi i\frac{b}{w}\left(rcN' + d\right)\right)\left\vert c,d,g^k\right\rangle$$

This will be non-zero if and only if $rcN'\equiv -d \mod w$. When we measure $c$ and $d$, we will thus find $-dc^{-1}N\equiv r\mod w$.

So I think this technique will work to recover the discrete log modulo $w$.

I don't think it's correct when you say "$a$ and $b$ will always have solutions". For a given $b$, $k$, and $r$, if $0\leq a\leq 2^{\lceil\lg p\rceil} -1$, there might be $1$ or $2$ solutions for $a$ such that $a-rb\equiv k\mod p -1$. Suppose $b=k=0$; then we have $a=p-1$ and $a=2(p-1)$ as solutions. The analysis for using $a\in \{0,\dots, 2^{\lceil\lg p\rceil}-1\}$ will probably be really tricky to get right, but it should work in principle.

Normally Shor's algorithm for DLP needs $2\lceil\lg p\rceil$ computations of the group action in a single run. Your technique reduces it to $\lceil \lg p\rceil + \lceil \lg w\rceil$, but you need to repeat roughly $\frac{\lg p}{\lg w}$ times. So the total cost in quantum gates goes up, but each individual run can be smaller. Maybe this would be preferable because of error correction: Since each run must be smaller, the error tolerance can be higher and maybe it can use less error correction overhead.

Answer 2

I rechecked the small $w$ QFT for unitarity and it doesn't work. The off diagonal terms fail to cancel when input and output bases differ by multiples of $w$. However, the superposition only depends on the value of the first QFT $\mod w$. A prime-factor QFT can be factored if its basis is the product of two relatively prime numbers as described at

https://en.wikipedia.org/wiki/Prime-factor_FFT_algorithm

Then, the non-base $w$ part can be summed out and the QFT can be simplified to a base $w$ QFT. So if you assume $N=Lw$, the input and output indices can be rewritten as

$n = n_1L+n_2w$

$k = k_1 L' L + k_2 w' w $

where $L' = L^{-1} \mod w$ and $w' = w^{-1} \mod L$

This represents modular structure of the indices

$n \mod w = n_1 L \mod w$ and $n \mod L = n_2 w \mod L$

$k \mod w = k_1 (L^{-1} \mod w)(L \mod w) + 0 = k_1 \mod w = k_1$ and

$k \mod L = 0 + k_2 (w^{-1} \mod L) (w \mod L) = k_2 \mod L = k_2$

$$ X_{k_1 L' L + k_2 w' w} = \sum_{n_1=0}^{w-1} (\sum_{n_2=0}^{L-1} x_{n_1L+n_2w} \omega_{L}^{n_2k_2}) \omega_{w}^{n_1k_1} $$

If you sum out the $\mod L$ subregister, leaving only the $\mod w$ subregister, you get

$$ Y_{k_1}= \sum_{k_2=0}^{L-1}X_{k_1 L' L + k_2 w' w} = \sum_{n_1=0}^{w-1} (\sum_{k_2=0}^{L-1} \sum_{n_2=0}^{L-1} x_{n_1L+n_2w} \omega_{L}^{n_2k_2}) \omega_{w}^{n_1k_1} = \phi_L \sum_{n_1=0}^{w-1} y_{n_1L} \omega_{w}^{n_1k_1} = \phi_L \sum_{n_1=0}^{w-1} y_{n_3} \omega_{w}^{n_3L'k_1} $$

Plancherel's theorem implies that the summed out probability (indexed by $n_1$) is constant before and after the application of a QFT. Assuming one performs the base $N$ QFT before the base $w$ QFT, $x_{n_1L+n_2w}$ will have solutions (= 0, 1) for all $n_1, n_2$ (i.e. for each index $n_1$, every index $n_2$ will have a basis vector with coefficient $1$), so the base $L$ part of the first QFT will have the same phase value for all $n_1$. So that, up to a constant phase, the QFT on the $\mod w$ subregister only depends on the base $w$ QFT.

It's possible to choose a good $L, N=Lw$ such that $N=Lw$ is very close to the group order and such that $L \mod w = 1$ so that both QFTs in the compressed 'classical' circuit can use a plain base $w$-QFT. Changing $L$ will cause small changes in the $w$ phases that are in superposition and induce (a typically sizeable) change in the overall phase.