# Is there a simple, formulaic way to construct a modular exponentiation circuit?

I'm a newcomer to quantum computing and circuit construction, and I've been struggling to understand how to make a modular exponentiation circuit. From what I know, there are several papers on the matter (like Pavlidis, van Meter, Markov and Saeedi, etc.) but they are all so complicated and involve a lot of efficiency and optimization scheme that make it impossible for me to understand. When I read it in Nielsen and Chuang, specifically in Box 5.2 the author wrote them without any example, as if it is very easy to make (it probably is, but not for me).

Anyway, I've learned about the algorithm to do modular exponentiation using binary representation (it's simple enough at least this thing), but I don't know how to make a circuit out of it. Here's the picture I believe describing the process:

So how do I build those $$U$$ circuit? Can anyone, for example, tell me how do things changed when say I went from $$11^x (\mod{15})$$ to $$7^x (\mod{21})$$? I don't care if the circuit is not gonna be optimized and contain thousands of gates, but I want to at least understand the first step before going into more advanced stuffs like optimization.

Thank you very much!

• This question and answer about an implementation of the order finding circuit and modular exponation circuit gives some insight.quantumcomputing.stackexchange.com/questions/4852/… – Bram Jul 22 '19 at 20:26
• Thank you! I've also seen these modular multiplication circuits in Markov and Saeedi in the form of SWAP gate, and even though I did try the numbers in and it works, I still couldn't see how; it's like something we make when we've already know the answer, and just make a circuit that gives out the correct answer. Why do we use the SWAP gates, and in that order for C = 2 , 4 or 7, 11? How do things changed when say M = 21 for example? I couldn't understand those things... – Kim Dong Jul 23 '19 at 3:56

Here's, surely, a very non-optimal way of doing it. Imagine we have a unitary $$V$$ which performs the operation $$V|x\rangle|y\rangle=|x\rangle|xy\text{ mod }N\rangle.$$ We can deal with how $$V$$ might work separately, but if you have that, we want to see how we can use it to calculate any $$|x^{2^i}\text{ mod }N\rangle$$. The trick is that if both inputs are $$x^{2^j}\text{ mod }N$$, then the output is $$x^{2^{j+1}}\text{ mod }N$$, so we only have to repeat this construction $$i$$ times. For example, in the circuit below: Here, I've used the control-not to denote transversal application to achieve copying of one (effectively classical) register to another. This lets you do any of the $$U$$ operations that you need, assuming that you know how to implement $$V$$. Don't forget that, as part of a larger circuit, you have to 'uncompute' the data on any auxiliary registers.

So, how do we implement $$V$$? Let me give some of the components. Let $$x=x_1x_2x_3\ldots x_n$$ and $$y=y_1y_2\ldots y_n$$ be the binary representations of $$x$$ and $$y$$. The product $$xy$$ is easy to calculate by long multiplication. For example, $$x_iy_j$$ is a bit value (so there are never any carries from the multiplication steps) that is equivalent to applying the Toffoli (controlled-controlled-not) with $$x_i$$ and $$y_j$$ as the two inputs. So you can calculate $$y_1x$$, $$y_2x$$, $$y_3x\ldots$$ on separate registers and then add them up.

Addition is another standard circuit. Imagine you want to add $$x_1x_2\ldots x_n$$ and $$y_1y_2\ldots y_n$$. We need to have additional two registers: one for the output, one for the carry bit. The least significant bit of output is $$x_n\oplus y_n$$, which can be calculated with controlled-nots. The carry bit has value $$z_n=x_ny_n$$. The next output is $$x_{n-1}\oplus y_{n-1}\oplus z_{n}$$, which we can again do with controlled nots. The carry bit is a majority vote - are two or more of $$x_{n-1},y_{n-1},z_n$$ value 1? One way to implement this is: You can keep repeating this process bit by bit to compute the sum. Then, again, don't forget to uncompute all the ancillas.

• Thank you for your answer. I still have 2 problems though:$\\$ 1. I'm still not sure how we can use multiplication and addition to make a circuit that calculate modulus. I'm a physics student and I don't really know about circuit. Can you elaborate for me? $\\$ 2. This method looks like it's gonna take a massive number of qubits since we effectively just multiply everything out instead of doing memory-efficient modular arithmetic right? I estimated using 30 qubits just to store the $x^j$ answer if we were to do $19^7 \mod(21) = 1$. So this is definitely unusable as of right now right? – Kim Dong Jul 24 '19 at 12:47
• @D.Tran You didn't ask for usable. You asked for a general method that could get you started. All the methods that have been used have involved a very deliberate choice of $a$ that makes things easy, and some very specific improvements for those cases. – DaftWullie Jul 24 '19 at 12:59
• Yes, the 2nd question isn't too important, but as in the 1st one I'm still not sure how to use it to do modulo... – Kim Dong Jul 24 '19 at 13:18
• @D.Tran Functionally, what is it you would do if you were asked to calculate $x\text{ mod }N$, given $x$ and $N$? – DaftWullie Jul 25 '19 at 7:17
• If I were to do it by hand, I'll try to divide x to N, then multiply N by the rounded down result, then take x minus the multiplied result. – Kim Dong Jul 25 '19 at 8:55

The method of transversal copying by a CNOT is solid and you can stack up the building blocks for the quantum part of shor algorithm. However ad-hoc circuit synthesis based at a pattern of the function truth table could be efficiënt in some cases as described in arxiv 1310.6446v2. First case is for factoring N=15 and base a = 2 with period r = 4. In exponential formulation we have $$f(x)=a^{x}\text{ mod }15$$ With values

Setup a truth table for input x between 0 and 3. Input x is represented by 2 qubits x2 and x1. Output y is represented by 4 qubits y4,y3,y2,y1 For example if x = 2 then x2=1 and x1=0 then only y3 =1 so put a NOT on this line.

Furthermore underlined entries in table 1 are the ones that are modified by a toffoli gate to get the right output in the circuit according the table 1. We can use this module in the overall algorithm according to https://arxiv.org/pdf/0705.1398.pdf