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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (479 KB)

Source

International Symposium on Computer Architecture archive
Proceedings of the 36th annual international symposium on Computer architecture table of contents

Austin, TX, USA

SESSION: Potpourri table of contents

Pages 383-394

Year of Publication: 2009

ISBN:978-1-60558-526-0

Also published in ...

Authors

Mark G. Whitney	University of California, Berkeley, Berkeley, CA, USA
Nemanja Isailovic	University of California, Berkeley, Berkeley, CA, USA
Yatish Patel	University of California, Berkeley, Berkeley, CA, USA
John Kubiatowicz	University of California, Berkeley, Berkeley, CA, USA

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 20, Downloads (12 Months): 74, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1555754.1555802 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Colt technical computing library in java.
	2	Steven Balensiefer , Lucas Kregor-Stickles , Mark Oskin, An Evaluation Framework and Instruction Set Architecture for Ion-Trap Based Quantum Micro-Architectures, ACM SIGARCH Computer Architecture News, v.33 n.2, p.186-196, May 2005
	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	Joel Darnauer , Wayne Wei-Ming Dai, A method for generating random circuits and its application to routability measurement, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.66-72, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228380]
	5	W.E. Donath. Wire length distribution for placements of computer logic. IBM Journal of Research and Development, 25(3):152--155, 1981.
	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	Darshan D. Thaker , Tzvetan S. Metodi , Andrew W. Cross , Isaac L. Chuang , Frederic T. Chong, Quantum Memory Hierarchies: Efficient Designs to Match Available Parallelism in Quantum Computing, Proceedings of the 33rd annual international symposium on Computer Architecture, p.378-390, June 17-21, 2006
	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	Tzvetan S. Metodi , Darshan D. Thaker , Andrew W. Cross, A Quantum Logic Array Microarchitecture: Scalable Quantum Data Movement and Computation, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.305-318, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.9]
	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	Nemanja Isailovic , Yatish Patel , Mark Whitney , John Kubiatowicz, Interconnection Networks for Scalable Quantum Computers, Proceedings of the 33rd annual international symposium on Computer Architecture, p.366-377, June 17-21, 2006
	17	Nemanja Isailovic , Mark Whitney , Yatish Patel , John Kubiatowicz, Running a Quantum Circuit at the Speed of Data, Proceedings of the 35th International Symposium on Computer Architecture, p.177-188, June 21-25, 2008
	18	Lucas Kreger-Stickles , Mark Oskin, Microcoded Architectures for Ion-Tap Quantum Computers, Proceedings of the 35th International Symposium on Computer Architecture, p.165-176, June 21-25, 2008
	19	C.E. Leiserson, F.M. Rose, and J.B. Saxe. Optimizing synchronous circuitry by retiming. In 3rd Caltech Conference on VLSI, 1983.
	20	Mark Oskin , Frederic T. Chong , Isaac L. Chuang, A Practical Architecture for Reliable Quantum Computers, Computer, v.35 n.1, p.79-87, January 2002 [doi>10.1109/2.976922]
	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.
	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	George F. Viamontes , Manoj Rajagopalan , Igor L. Markov , John P. Hayes, Gate-level simulation of quantum circuits, Proceedings of the 2003 Asia and South Pacific Design Automation Conference, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119829]
	30	Mark Whitney , Nemanja Isailovic , Yatish Patel , John Kubiatowicz, Automated generation of layout and control for quantum circuits, Proceedings of the 4th international conference on Computing frontiers, May 07-09, 2007, Ischia, Italy [doi>10.1145/1242531.1242546]
	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.