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$.


  • $\begingroup$ Can you clarify the difference between $y$ and $x$, and explain what $r$ represents? I think usually the register with $g^ax^{-b}$ is measured; do you do that here? $\endgroup$ – Sam Jaques Jun 15 at 15:27
  • $\begingroup$ $r$ is the discrete logarithm, (although perhaps I haven't been careful and it represents $r \mod (p-1) \mod w$ is some places). It arises because $\mathcal{Z}^*_p$ is a cyclic group and for some $r$ $x^r=g$. So $g^ax^{-b}=g^ag^{-br}=g^{a-rb}=g^k=y$. $x$ is just the base of the discrete logarithm we wish to find; y is shorthand for $g^ax^{-b}$. No, the first two registers $c, d$ contain the period data. The third register $g^ax^{-b} is just to create the entanglement to find the discrete logarithm. $\endgroup$ – botsina Jun 15 at 15:59

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.

| improve this answer | |
  • $\begingroup$ I checked and the "variant" QFT defined by $y_k = \frac{1}{\sqrt N} \sum_{n=0}^{N-1} x_n \omega_w^{kn}$ is unitary up to a $O(\frac{w}{N})$ error. The main use I see for the CRT method is that it can be combined with May and Schlieper's paper (arxiv.org/abs/1905.10074) to put finding discrete logarithms and factoring semiprimes in BPP. The CRT method bypasses the need for a homomorphic universal hash function used with the Mosca-Ekert circuit. Instead, a simple universal hash function like $ay+b \mod p \mod m$ should work (where the hash function parameters are $a,b$). $\endgroup$ – botsina Jun 20 at 3:30
  • $\begingroup$ The hash can be computed from the multiplication matrices for computing modular exponentiation by summing out the divisible by $m$ part, replacing $x \mod p \mapsto a_ix \mod p$ with $x \mod p \mod m \mapsto a_ix \mod p \mod m$, where $a_i = g^{2^j} or x^{l} \mod p$ (i.e we compute the normalized probability). A similar method can be used to compute the actual hash. $\endgroup$ – botsina Jun 20 at 3:30
  • $\begingroup$ To calculate the transition matrices, one needs N to be very smooth and preferably a power of 2. If you use variant QFTs with base $w$, you can represent the first two registers as being just $w$ qubits each. The multiplication matrices can be combined with the Hadamard and controlled gates to get $O(\log N)$ $(2w+m)\times(2w+m)$ matrices which are multiplied together to get the final probability amplitudes. If you use the proper QFT base $N$ and still use just $2w$ qubits for the period registers, there will be $O(\frac{1}{w})$ errors in the final transition amplitudes. $\endgroup$ – botsina Jun 20 at 3:31
  • $\begingroup$ If you try to find discrete logarithms from the full range of possible discrete logarithms, you need to be careful about the accumulation of errors, and probably only two $c,d$ pairs will be correct (and $m$ should be chosen to be large, perhaps 100). $\endgroup$ – botsina Jun 20 at 3:32
  • 1
    $\begingroup$ Do you know how $c$ could have a full range but a denominator of $w$? I don't know enough about QFT circuits to know how to express this. If $c$ has its full range I think it will still involve more superpositions than we could simulate classically. $\endgroup$ – Sam Jaques Jun 26 at 8:34

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


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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.