Refactor Shor's algorithm

[Cryoris]

What is the expected enhancement?

Shor's algorithm could use a refactor, it currently uses a lot of old Qiskit logic which could be written in a much more compact manner. For instance the inverse() method of circuits and gates and the control() method of gates could be leveraged. Also things like U3(pi, 0, pi) can be placed by the proper gate X, since there is no performance deterioration anymore for this change (right?).

This would be a nice project to start contributing, since one needs to get to know both Shor's algorithm and what circuits can do in current Qiskit.

[MetcalfeTom]

@Cryoris I would like to take on this issue!

As proposed, I would replace the generic UGates with their more familiar notation, also adding type hints for all the class functions as well.

In terms of making use of inverse(), my plan there would be to make the gate-applying functions more modular - i.e. have them create and return QuantumCircuit objects which can be inverted and appended to the main circuit instruction list with circuit.extend(). Is there is a better suggestion which fits the codestyle better?

[Cryoris]

Sounds great!

Thanks for also thinking of the type hints 😉

In terms of making use of inverse(), my plan there would be to make the gate-applying functions more modular - i.e. have them create and return QuantumCircuit objects

I think we could make this more efficient if we would not re-construct the circuits in every function call. If you see that circuits are the same and only the qubits they get applied to changes, then you could construct the circuit once and store it.

appended to the main circuit instruction list with circuit.extend().

The extend method will soon be deprecated (see Qiskit/qiskit#4208). If you want to add a circuit to another circuit you can use circuit.combine (it has an inplace argument to append in-place) and to add an Instruction or Gate you can use circuit.append.

Also there is a generic control method if you can cast the circuit to a Gate instance (using the circuit.to_gate() method), which might be handy!

If you have any questions, need input or just want to discuss something, let me know!

[MetcalfeTom]

Thanks for the help @Cryoris,

I like the ability of casting to Gate, it is very elegant. I used it to build a gate for the addition in Fourier Space. With the help of .control() and .inverse(), this has simplified most of the circuit construction down to two functions - _controlled_controlled_phi_add_mod_N() and _controlled_multiple_mod_N().

For a complete solution, I'm trying to cast those functions to gates too (both can leverage .control() and .inverse()). However I can't think of a way to avoid re-constructing their circuits with each call, since the parameter a changes with the control qubit used. What do you think?

I suppose I could store this number using a classical register, if that didn't make things too complicated.

[Cryoris]

Hmm in principle there's the qiskit.circuit.Parameter object which can be used as variable in e.g. rotation angles etc. But seeing that a undergoes quite complex computations I don't think this is possible, as the Parameters only support basic arithmetic operations such as +=*/.

I think it would be okay to reconstruct the circuits here, in the end the expensive part is transpiling the circuits, not building them. In future, we could either rewrite the _get_angles function to use the available operations on Parameter objects, or add more operations to the Parameter. As you said, adding a classical register seems a bit too complicated, also if new users try to understand the implementation.