# Modular exponentiation quantum circuit design for Shor's algorithm

I'm studying Shor's algorithm and I'm wondering how to build the quantum circuit for the modular exponentiation calculation in the Shor's algorithm.

Is the circuit found classically (using conventional computers) by checking the truth table of the modular exponentiation calculation result?

For example, when I try to run the Shor's algorithm for factoring N=15 with a randon number a=2, the truth table of the modular exponentiation function $$(f(x)=2^xmod15)$$ looks like below:

In binary representation, the truth table looks like below:

The quantum circuit for this truth table looks like below:

Is the quantum circuit for this calculation found by conventaionl classical computers?

## 1 Answer

There are many quantum implementations of modular exponentiation to choose from depending on whether you want to optimize qubit count vs time and other similar tradeoffs.

However, for the method closest in idea to this that is functional, first note a straight-up modular exponentiation truth table for every $$x$$ would be countereffective since, even though any individual modular exponentation is tractable, it would require exponential time to solve for every single $$x$$ (and you could find the period while creating the table anyways): however, if you want to use this basic idea of efficiently classically creating a truth table and making a quantum circuit, you can just make a truth table for only the $$\log_2(n^2)$$ ($$n$$ being the number factored) powers of 2 necessary to obtain the period which can be classically determined in polynomial time, since those are all you need to perform Shor's Algorithm.

If you then have a way to make a set of controllable gates $$U(a)$$ that do modular multiplication on the computational basis by $$a$$, then you take the consecutive results $$a$$ of your table, use the corresponding $$U(a)$$ on a register started at $$\left| 1\right>$$ based on the controls that will be inverse QFTed, and you will be able to implement Shor's Algorithm without having used exponential classical or quantum resources. But $$U(a)$$ can be complicated to generally implement: https://arxiv.org/pdf/1202.6614.pdf and https://arxiv.org/pdf/quant-ph/0205095.pdf both provide options.

• First, sorry, the first $log_2(x)$ was a quite confusing typo. For general base $a$ and number to be factored $n$, in order to obtain the period necessary, you at worst need to know every $a^{2^x} \pmod n$ up until you reach a $2^x$ that is greater than the number squared. If you generated every $a^x \pmod n$ up to there rather than every $a^{2^x} \pmod n$, even if you could do modular exponentiation quickly you'd have to do it a number of times comparable to the factored number itself, so it would be worse than trial division. Apr 11 at 0:10
• There's some confusion that comes from the fact your example base is also 2 and it's an exponent in an exponent. You only need the exponents that are powers of 2 up to the number squared, and, you can do each one tractably and will only need to do work out $log_2(n^2)$ times, which, from the perspective of big O notation on the factored number's bit count, is polynomial time. Apr 11 at 0:15
• The thing I am saying is you need to just generate the truth tables for every $a^{2^x} \pmod n$ up to $2^x > n^2$, the truth table you showed included $2^3 \pmod{15}$ which is unnecessary and, if you did go that far to include all those, there'd be too many to do. Apr 11 at 0:23