research-article

A fault tolerant, area efficient architecture for Shor's factoring algorithm

Authors:

Mark G. Whitney,

Nemanja Isailovic,

John KubiatowiczAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 37, Issue 3

Pages 383 - 394

https://doi.org/10.1145/1555815.1555802

Published: 20 June 2009 Publication History

Abstract

We optimize the area and latency of Shor's factoring while simultaneously improving fault tolerance through: (1) balancing the use of ancilla generators, (2) aggressive optimization of error correction, and (3) tuning the core adder circuits. Our custom CAD flow produces detailed layouts of the physical components and utilizes simulation to analyze circuits in terms of area, latency, and success probability. We introduce a metric, called ADCR, which is the probabilistic equivalent of the classic Area-Delay product. Our error correction optimization can reduce ADCR by order of magnitude or more. Contrary to conventional wisdom, we show that the area of an optimized quantum circuit is not dominated exclusively by error

correction. Further, our adder evaluation shows that quantum carry-lookahead adders (QCLA) beat ripple-carry adders in ADCR, despite being larger and more complex. We conclude with what we believe is one of most accurate estimates of the area and latency required for 1024-bit Shor's factorization: 7659 mm² for the smallest circuit and 6 x 10⁸ seconds for the fastest circuit.

References

[1]

Colt technical computing library in java.

[2]

S. Balensiefer, L. Kregor-Stickles, and M. Oskin. An evaluation framework and instruction set architecture for ion-trap based quantum micro-architectures. SIGARCH Comput. Archit. News, 33(2):186--196, 2005.

Digital Library

[3]

A.W. Cross, D.P. DiVincenzo, and B.M. Terhal. A comparative code study for quantum fault-tolerance. Arxiv preprint arXiv:0711.1556, 2007.

[4]

J. Darnauer and W.W.M. Dai. A method for generating random circuits and its application to routability measurement. In ACM Intl. Symp. on Field-Programmable Gate Arrays, 1996.

Digital Library

[5]

W.E. Donath. Wire length distribution for placements of computer logic. IBM Journal of Research and Development, 25(3):152--155, 1981.

Digital Library

[6]

T.G. Draper. Addition on a Quantum Computer. Arxiv preprint quant-ph/0008033, 2000.

[7]

T.G. Draper, S.A. Kutin, E.M. Rains, and K.M. Svore. A logarithmic-depth quantum carry-lookahead adder. Arxiv preprint quant-ph/0406142, 2004.

[8]

D.D. Thaker et al. Quantum Memory Hierarchies: Efficient Designs to Match Available Parallelism in Quantum Computing. Intl. Symp. on Computer Architecture, 2006.

Digital Library

[9]

K. Svore et al. Local fault-tolerant quantum computation. Phys. Rev. A, 72:022317, 2005.

[10]

M.J. Madsen et al. Planar ion trap geometry for microfabrication. Applied Phys. B: Lasers and Optics, 78:639 -- 651, 2004.

[11]

R. Ozeri et al. Hyperfine Coherence in the Presence of Spontaneous Photon Scattering. Phys. Rev. Lett., 95:030403.

[12]

S. Seidelin et al. Microfabricated surface-electrode ion trap for scalable quantum information processing. Phys. Rev. Lett., 96(25):253003, 2006.

[13]

T.S. Metodi et al. A Quantum Logic Array Microarchitecture: Scalable Quantum Data Movement and Computation. Intl. Symp. on Microarchitecture, 2005.

Digital Library

[14]

W.K. Hensinger et al. T-junction ion trap array for two-dimensional ion shuttling, storage, and manipulation. Appl. Phys. Lett., 88:034101, 2006.

[15]

A.G. Fowler and L.C.L. Hollenberg. Scalability of Shor's algorithm with a limited set of rotation gates. Phys. Rev. A, 70(3):32329, 2004.

[16]

N. Isailovic, Y. Patel, M. Whitney, and J. Kubiatowicz. Interconnection Networks for Scalable Quantum Computers. Intl. Symp. on Computer Architecture, 2006.

Digital Library

[17]

N. Isailovic, M. Whitney, Y. Patel, and J. Kubiatowicz. Running a quantum circuit at the speed of data. In Intl. Symp. on Computer Architecture, 2008.

Digital Library

[18]

L. Kreger-Stickles and M. Oskin. Microcoded Architectures for Ion-Tap Quantum Computers. In Intl. Symp. on Computer Architecture, 2008.

Digital Library

[19]

C.E. Leiserson, F.M. Rose, and J.B. Saxe. Optimizing synchronous circuitry by retiming. In 3rd Caltech Conference on VLSI, 1983.

[20]

M. Oskin, F.T. Chong, and I.L. Chuang. A practical architecture for reliable quantum computers. Computer, 35(1):79--87, 2002.

Digital Library

[21]

J. Preskill. Fault-tolerant quantum computation. Arxiv preprint quant-ph/9712048, 1997.

[22]

V.V. Shende, S.S. Bullock, and I.L. Markov. Synthesis of quantum-logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(6):1000--1010, 2006.

Digital Library

[23]

P.W. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52(4):2493, 1995.

[24]

A.M. Steane. Space, Time, Parallelism and Noise Requirements for Reliable Quantum Computing. Quantum Computing: Where Do We Want to Go Tomorrow?, 1999.

[25]

A.M. Steane. Overhead and noise threshold of fault-tolerant quantum error correction. Phys. Rev. A, 68(4):42322, 2003.

[26]

A.M. Steane. How to build a 300 bit, 1 Gop quantum computer. Arxiv preprint quant-ph/0412165, 2004.

[27]

R. Van Meter and K.M. Itoh. Fast quantum modular exponentiation. Arxiv preprint quant-ph/0408006, 2004.

[28]

V. Vedral, A. Barenco, and A. Ekert. Quantum networks for elementary arithmetic operations. Phys. Rev. A, 54(1):147--153, 1996.

[29]

G.F. Viamontes, M. Rajagopalan, I.L. Markov, and J.P. Hayes. Gate-level simulation of quantum circuits. In Conf. on Asia South Pacific Design Automation, 2003.

Digital Library

[30]

M. Whitney, N. Isailovic, Y. Patel, and J. Kubiatowicz. Automated Generation of Layout and Control for Quantum Circuits. In Intl. Conf. on Computing Frontiers, 2007.

Digital Library

[31]

C. Zalka. Simulating quantum systems on a quantum computer. Mathematical, Physical and Engineering Sciences, 454(1969):313--322, 1998.

[32]

B. Zeng, A. Cross, and I.L. Chuang. Transversality versus Universality for Additive Quantum Codes. Arxiv preprint arXiv: 0706.1382, 2007.

Cited By

Sargaran SMohammadzadeh N(2019)SAQIPACM Transactions on Architecture and Code Optimization10.1145/331187916:2(1-21)Online publication date: 18-Apr-2019
https://dl.acm.org/doi/10.1145/3311879
Nagayama SFowler AHorsman DDevitt SMeter R(2017)Surface code error correction on a defective latticeNew Journal of Physics10.1088/1367-2630/aa591819:2(023050)Online publication date: 23-Feb-2017
https://doi.org/10.1088/1367-2630/aa5918
Dousti MShafaei APedram M(2016)Squash 2Quantum Information & Computation10.5555/3179448.317945616:3-4(332-356)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.5555/3179448.3179456
Show More Cited By

Index Terms

A fault tolerant, area efficient architecture for Shor's factoring algorithm
1. Computer systems organization
  1. Architectures
  2. Dependable and fault-tolerant systems and networks
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

A fault tolerant, area efficient architecture for Shor's factoring algorithm
ISCA '09: Proceedings of the 36th annual international symposium on Computer architecture

We optimize the area and latency of Shor's factoring while simultaneously improving fault tolerance through: (1) balancing the use of ancilla generators, (2) aggressive optimization of error correction, and (3) tuning the core adder circuits. Our custom ...
Automated generation of layout and control for quantum circuits
CF '07: Proceedings of the 4th international conference on Computing frontiers

We present a computer-aided design flow for quantum circuits, complete with automatic layout and control logic extraction. To motivate automated layout for quantum circuits, we investigate grid-based layouts and show a performance variance of four times ...
Fast quantum modular exponentiation architecture for Shor's factoring algorithm

We present a novel and efficient, in terms of circuit depth, design for Shor's quantum factorization algorithm. The circuit effectively utilizes a diverse set of adders based on the Quantum Fourier transform (QFT) Draper's adders to build more complex ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 37, Issue 3

June 2009

495 pages

ISSN:0163-5964

DOI:10.1145/1555815

Issue’s Table of Contents

ISCA '09: Proceedings of the 36th annual international symposium on Computer architecture
June 2009
510 pages
ISBN:9781605585260
DOI:10.1145/1555754
General Chair:
Steve Keckler
University of Texas at Austin
,
Program Chair:
Luiz André Barroso
Google Inc.

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2009

Published in SIGARCH Volume 37, Issue 3

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
502
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sargaran SMohammadzadeh N(2019)SAQIPACM Transactions on Architecture and Code Optimization10.1145/331187916:2(1-21)Online publication date: 18-Apr-2019
https://dl.acm.org/doi/10.1145/3311879
Nagayama SFowler AHorsman DDevitt SMeter R(2017)Surface code error correction on a defective latticeNew Journal of Physics10.1088/1367-2630/aa591819:2(023050)Online publication date: 23-Feb-2017
https://doi.org/10.1088/1367-2630/aa5918
Dousti MShafaei APedram M(2016)Squash 2Quantum Information & Computation10.5555/3179448.317945616:3-4(332-356)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.5555/3179448.3179456
Fu XRiesebos LLao LAlmudever CSebastiano FVersluis RCharbon EBertels KPalermo GFeo JTumeo AFranke H(2016)A heterogeneous quantum computer architectureProceedings of the ACM International Conference on Computing Frontiers10.1145/2903150.2906827(323-330)Online publication date: 16-May-2016
https://dl.acm.org/doi/10.1145/2903150.2906827
(2016)Quantum circuit physical design flow for the multiplexed trap architectureMicroprocessors & Microsystems10.1016/j.micpro.2016.02.01845:PA(23-31)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.micpro.2016.02.018
Mohammadzadeh N(2016)Physical design of quantum circuits in ion trap technology - A surveyMicroelectronics Journal10.1016/j.mejo.2016.07.00155:C(116-133)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.mejo.2016.07.001
Mirkhani ZMohammadzadeh N(2016)Physical synthesis of quantum circuits using templatesQuantum Information Processing10.1007/s11128-016-1377-x15:10(4117-4135)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s11128-016-1377-x
Ahsan MKim JNebel WAtienza D(2015)Optimization of quantum computer architecture using a resource-performance simulatorProceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition10.5555/2755753.2757070(1108-1113)Online publication date: 9-Mar-2015
https://dl.acm.org/doi/10.5555/2755753.2757070
Ahsan MMeter RKim J(2015)Designing a Million-Qubit Quantum Computer Using a Resource Performance SimulatorACM Journal on Emerging Technologies in Computing Systems10.1145/283057012:4(1-25)Online publication date: 28-Dec-2015
https://dl.acm.org/doi/10.1145/2830570
Bahreini TMohammadzadeh N(2015)An MINLP Model for Scheduling and Placement of Quantum Circuits with a Heuristic Solution ApproachACM Journal on Emerging Technologies in Computing Systems10.1145/276645212:3(1-20)Online publication date: 21-Sep-2015
https://dl.acm.org/doi/10.1145/2766452
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents