4

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?

Mithrandir24601
  • 3,796
  • 3
  • 24
  • 45
William
  • 182
  • 9

2 Answers2

3

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.

Joseph Geipel
  • 1,241
  • 1
  • 6
  • 6
2

The references below explain the construction of modular exponentiation circuit. I also attempt to implement the circuit accordingly in https://github.com/thyung/qiskit_factorization using qiskit and factorize some numbers with qasm_simulator.

Vlatko Vedral, Adriano Barenco and Artur Ekert, Quantum Networks for Elementary Arithmetic Operations

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

thyung
  • 21
  • 1