I\'m a fledgling computer science scholar, and I\'m being asked to write a paper

Question

I'm a fledgling computer science scholar, and I'm being asked to write a paper which involves integer factorization. As a result, I'm having to look into Shor's algorithm on quantum computers.

For the other algorithms, I was able to find specific equations to calculate the number of instructions of the algorithm for a given input size (from which I could calculate the time required to calculate on a machine with a given speed). However, for Shor's algorithm, the most I can find is its complexity: O( (log N)^3 ).

Is there either some way I can find its speed/actual complexity from its Big-O Notation? If not, is there someone who can tell me what I want, or how to find it?

Explanation / Answer

What you are asking for does not exist, for good reasons.

Today there is no existing computer that can execute Shor's algorithm. To run Shor's algorithm, you need a quantum computer, which doesn't exist yet. Therefore, you shouldn't expect precise estimates of its speed or running time, as that will depend upon the details of the computer that the algorithm is run on -- and we can't possibly know those details until we've successfully built one.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.