Generally exact complexities aren't interesting, but I couldn't find any info on it for this case at all.

Specifically my question, is let's say I have a polynomial p(n) and I want to have a quantum Turing machine that solves factorization at at most p(n)/c steps s.t. it has an error probability of at most 2^(-p(n)), what is the maximum c I can get? What if I expand the question to c being a function of n, can this be done for c(n)=n?



1 Answer 1


Welcome to QCSE. A lot of people have given a lot of thought to how long it would take to explicitly execute Shor's algorithm on a cryptographically relevant problem.

One fantastic paper by Gidney and Ekerå is here. There, they give a polynomial number of Toffoli/CCNOT gates to factor an $n$-bit number as $0.3n^3$ and a circuit depth of $500n^2$. So, I guess you can say that the constant prefactor for the number of Toffoli gates are $0.3$, while the constant prefactor for the depth is $500$.

And yes, Shor's algorithm is "probabilistic" insofar as, even running on error-free logical qubits with error-free gates we will get a random output for each run of the QFT, but that's why we are always concerned with the expected number of runs and the number of times we have to run the QFT to get an output, to feed into the other classical portions (the continued-fraction portion) of Shor's algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.