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.
$\begingroup$
$\endgroup$
3
-
4$\begingroup$ This seems more a mathematics or computer science question, and less a physics question. Perhaps there are other sites on the stackexchange network that would be a better fit for this. $\endgroup$– FlorisCommented Oct 6, 2017 at 18:20
-
$\begingroup$ You write down the algorithm and count the number of gates it requires? There are papers on that. $\endgroup$– Norbert SchuchCommented Oct 6, 2017 at 20:40
-
2$\begingroup$ Did you check the wikipedia page en.wikipedia.org/wiki/Shor%27s_algorithm? It gives a gate count. What more do you want to know? $\endgroup$– Norbert SchuchCommented Oct 8, 2017 at 4:31
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Oct 9, 2017 at 1:10