How to calculate the number of operations required to factor a number $n$ with Shor's Algorithm? Essentially, how to find the number of clock cycles required to factor a number $n$ on a quantum computer with Shor's Algorithm? An example on any architecture would be helpful.
 A: Making an accurate estimate is difficult, because there are so many factors that it depends on.


*

*What circuit constructions are you using to perform the modular exponentiation?

*How are you performing non-Clifford operations? How are you producing magic states?

*Are you magic-state-production limited or are you measure-react-delay limited?

*What kinds of circuit and topological optimizations are you applying? Are you doing on-the-fly optimizations? How effective are they on average?

*What kind of overhead is there in terms of moving qubits around so that they can interact?


The answers to these questions are all in flux as more research is done. For a historical estimate, see the paper "Surface codes: Towards practical large-scale quantum computation". They use a modular exponentiation circuit that uses $\approx 280 N^3$ T gates arranged into $\approx 120 N^3$ layers (separated by Clifford gates, which have negligible cost in comparison).
If lots more qubits are available, you can use circuits with better asymptotic complexity. $\tilde{O}(N)$ depth and $\tilde{O}(N^2)$ count are easily achievable with known classical multiplication algorithms, but they may not be better for typical RSA key sizes. There are also many possible constant-factor improvements. For example, Toffoli gates in a compute/uncompute pair only require 4 T gates total instead of 14. Only time will tell what actually gets used.
