3
$\begingroup$

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:

enter image description here

In binary representation, the truth table looks like below:

enter image description here

The quantum circuit for this truth table looks like below:

enter image description here

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

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Joseph Geipel
    Apr 11 at 0:10
  • $\begingroup$ 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. $\endgroup$
    – Joseph Geipel
    Apr 11 at 0:15
  • $\begingroup$ 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. $\endgroup$
    – Joseph Geipel
    Apr 11 at 0:23

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.