Implement Shor's algorithm for the DLP

[mhinkie]

What is the expected behavior?

Provide an implementation of Shor's algorithm for the discrete logarithm problem similar to the implementation of Shor's algorithm for prime factorization in qiskit/algorithms/factorizers/shor.py.

I have already implemented the Algorithm based on: https://arxiv.org/abs/quant-ph/9903071
(see https://github.com/mhinkie/ShorDiscreteLog for the code)

There still are some details to discuss before implementation can begin:

• I have implemented the modular exponentiation using three different approaches to be able to compare them. One of them is the circuit described in https://arxiv.org/abs/quant-ph/0205095 (Beauregard), which is also used in the current implementation of Shor's algorithm for prime factorization. This version performs best in the simulator, because the number of used qubits is relatively low. Judging by the number of performed gate operations and the circuit depth however, on an actual quantum computer the gate based on this paper https://arxiv.org/abs/1801.01081 will perform best, even though it is slower on the simulator because of the number of qubits needed. Which version of the modular exponentiation do you prefer?
• If you prefer Beauregard's gate, should I restructure the code s.t. the modular exponentiation gate is in its own file? This way the gate can be referenced in both the algorithm for prime factorization and the algorithm for the DLP and no duplicate code is introduced.
• Are there any specific requirements regarding the interface? My plan is to provide, in addition to the constructor, a construct_circuit and a solve function and to return the result as an AlgorithmResult similar to shor.py.

[mhinkie]

@Cryoris Hi, I hope I found the right username in Github. I wrote on Slack yesterday about implementing an algorithm for the DLP and I've created this issue to discuss the details.