Architecture-Dependent Execution Time of Shor's Algorithm

Details Architecture-Dependent Execution Time of Shor's Algorithm Architecture-Dependent Execution Time of Shor's Algorithm

2005-07-04

arxiv.org/abs/quant-ph/0507023v2

Proc. Mesoscopic Superconductivity + Spintronics 2006

Physics

Quantum Physics

6 pages, 2 figures, single-column World Scientific format. v2: published version, shortened text, slightly revised performance

Scientific paper

We show how the execution time of algorithms on quantum computers depends on the architecture of the quantum computer, the choice of algorithms (including subroutines such as arithmetic), and the ``clock speed'' of the quantum computer. The primary architectural features of interest are the ability to execute multiple gates concurrently, the number of application-level qubits available, and the interconnection network of qubits. We analyze Shor's algorithm for factoring large numbers in this context. Our results show that, if arbitrary interconnection of qubits is possible, a machine with an application-level clock speed of as low as one-third of a (possibly encoded) gate per second could factor a 576-bit number in under one month, potentially outperforming a large network of classical computers. For nearest-neighbor-only architectures, a clock speed of around twenty-seven gates per second is required.

Affiliated with

Also associated with

No associations

Rating

Architecture-Dependent Execution Time of Shor's Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Architecture-Dependent Execution Time of Shor's Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Architecture-Dependent Execution Time of Shor's Algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-467828