Investigating the practical implementation of Shor's alagorithm

Simon J. Devitt; Austin G. Fowler; Lloyd C. L. Hollenberg

doi:10.1117/12.583191

23 February 2005 Investigating the practical implementation of Shor's algorithm

Simon J. Devitt, Austin G. Fowler, Lloyd C. L. Hollenberg

Proceedings Volume 5650, Micro- and Nanotechnology: Materials, Processes, Packaging, and Systems II; (2005) https://doi.org/10.1117/12.583191
Event: Smart Materials, Nano-, and Micro-Smart Systems, 2004, Sydney, Australia

Abstract

The publication in 1994 of Shor's algorithm, which allows factorization of composite number N in a time polynomial in its binary length L has been the primary catalyst for the race to construct a functional quantum computer. However, it seems clear that any practical system that may be developed will not be able to perform completely error free quantum gate operations or shield even idle qubits from inevitable error effects. Hence, the practicality of quantum algorithms needs to be investigated to estimate what demands must be made of quantum error correction (QEC). Several different quantum circuits implementing the quantum period finding (QPF) subroutine, which lies at the heart of Shor's algorithm have been designed, but each tacitly assumes that arbitrary pairs of qubits can be interacted. While some architectures posses this property, many promising proposals are best suited to realizing a single line of qubits with nearest neighbor interactions only. This paper will present a circuit suitable for implementing the QPF subroutine for such linear nearest neighbor (LNN) designs. We will then present direct simulation results showing for both the LNN circuit and for a circuit utilizing arbitrary interactions, that the QPF subroutine is very sensitive to a small number of errors in the entire circuit. These results can then be used to briefly examine some of the practical issues to implementing such large scale quantum algorithms.

Citation Download Citation

Simon J. Devitt, Austin G. Fowler, and Lloyd C. L. Hollenberg "Investigating the practical implementation of Shor's algorithm", Proc. SPIE 5650, Micro- and Nanotechnology: Materials, Processes, Packaging, and Systems II, (23 February 2005); https://doi.org/10.1117/12.583191

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available