Article

Using HDLs for describing quantum circuits: a framework for efficient quantum algorithm simulation

Authors:

Mircea VlǎdutiuAuthors Info & Claims

CF '04: Proceedings of the 1st conference on Computing frontiers

Pages 96 - 110

https://doi.org/10.1145/977091.977107

Published: 14 April 2004 Publication History

Abstract

The quantum algorithms could efficiently solve problems having exponential classical solutions [8]. The circuit model is considered as the most feasible implementation of the quantum algorithms [17]. This paper tries to find common ground between classical circuit design techniques and quantum computation, by identifying quantum circuit specification and simulation tools under the form of Hardware Description Languages (HDLs). The HDL-based simulation approach could reduce the complexity of quantum circuit simulation, by considering entanglement as the main source of gate-level simulation complexity, and isolating it in an automated manner. This is possible by taking advantage of the HDL feature of describing a circuit with both structural and functional architectures. We also performed an analysis of our methodology effectiveness, for the arithmetic circuits involved in Shor's algorithm and the circuits implementing Grover's algorithm. Our method is further improved by an entangled representation avoidance technique called 'bubble logic insertion'.

References

[1]

Ashenden, P.J. The Designer's guide to VHDL (second edition). Morgan Kaufmann Publishers (2001).]]

Digital Library

[2]

Barenco, A., Bennett, C.H., Cleve R., DiVincenzo, D., Margolus N., Shor, P., Sleator T., Smolin J., and Weinfurter, H. Elementary gates for quantum computation. Phys. Rev. A 52, 3457--3467 (1995), quant-ph/9503016.]]

[3]

Bernstein E., Vazirani,U. Quantum Complexity Theory. SIAM J. Computing 26, 1411--73 (1997).]]

Digital Library

[4]

Boyer, M., Brassard, G., Hoyer, P., Tapp, A. Tight bounds on quantum searching. Fortsch. Phys. -- Prog.Phys., 46(4--5):493--505 (1998).]]

[5]

Bransden, B.H., Joachain, C.J. Introduction to Quantum Mechanics. Addison-Wesley Longman Ltd. (1989).]]

[6]

Coppersmith, D. An approximate Fourier transform useful in quantum factoring. IBM Research Report RC 19642 (1994).]]

[7]

De Micheli, G. Design and Optimization of Digital Circuits. McGraw-Hill, (1996).]]

Digital Library

[8]

Deutsch, D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400, 97 (1985).]]

[9]

Deutsch, D. Quantum computational networks. Proceedings Royal Society London A 425, 73 (1989).]]

[10]

Deutsch D., and Jozsa, R. Rapid Solution of Problems by Quantum Computation. Proc. R. Soc. London A, 439:553 (1992).]]

[11]

Ekert, A., Jozsa, R. Quantum Algorithms: Entanglement Enhanced Information Processing. Phil Trans Roy Soc Lond A, pages 1779--1782 (1998).]]

[12]

Grover, L.K. Proc. 28th Annual ACM Symposium on the Theory of Computation, pp.212--219, ACM Press, (1996).]]

Digital Library

[13]

Hales, L., and Hallgren, S. An Improved Quantum Fourier Transform Algorithm and Applications. 41st Annual Symposium on Foundations of Computer Science (FOCS) Redondo Beach CA (2000).]]

Digital Library

[14]

Lenstra, A.K., Lenstra, H.W., Manasse, M.S., and Pollard, J.M. The Number Field Sieve. In Proceedings of the 22nd Annual ACM Symposium on the Theory of Computation, pages 564--572, (1990).]]

Digital Library

[15]

Moore, C. Quantum Circuits: Fanout, Parity, and Counting. Los Alamos Preprint Archives (1999), quant-ph/9903046.]]

[16]

Nielsen, M.A., and Chuang, I.L. Programmable Quantum Gate Arrays. Phys. Rev. Lett. 79, 321--324 (1997).]]

[17]

Nielsen, M.A., and Chuang, I.L. Quantum Computation and Quantum Information. Cambridge University Press (2000).]]

Digital Library

[18]

Obenland, K.M., and Despain, A. Simulating the Effect of Decoherence and Inaccuracies on a Quantum Computer. Proc. 1st NASA Conference on Quantum Computation and Quantum Communication (1998).]]

Digital Library

[19]

Omer, B. Quantum Programming in QCL. Technical Report, Institute of Information Systems, Technical University of Vienna (2000).]]

[20]

Parhami, B. Computer Arithmetic. Algorithms and Hardware Designs. Oxford University Press, (2000).]]

Digital Library

[21]

Parker, S., and Plenio, M.B. Entanglement Simulations of Shor's Algorithm. J. Mod. Opt., Vol. 49, Nr. 8 pp. 1325--1353 (2002).]]

[22]

Preskill, J. Reliable Quantum Computers. Proc. Roy. Soc. London A for the Proc. of Santa Barbara Conference on Quantum Coherence and Decoherence (1996).]]

[23]

Preskill, J. Quantum Computation. Course Handouts, http://www.theory.caltech.edu/people/preskill/ph229/.]]

[24]

Shor, P.W. Algorithms for Quantum Computation: Discrete Logarithms and Factoring.", Proc. 35th Symp. on Foundations of Computer Science 124--134 (1994).]]

Digital Library

[25]

Svozil, K. Quantum computation and complexity theory. Course given at the Institut fur Informationssysteme, Abteilung fur Datenbanken und Expertensysteme, University of Technology Vienna (1994) hep-th/9412047]]

[26]

Toffoli, T. Reversible Computing. Automata, Languages and Programming, eds. J.W. de Bakker and J. van Leeuwen. Springer New York, (1980).]]

Digital Library

[27]

Udrescu, M., Prodan, L., and Vl?du?iu, M. A New Perspective in Simulating Quantum Circuits. LBP Proc. GECCO, pp 284--289 (Chicago, July 2003).]]

[28]

Vedral, V., Barenco, A., and Ekert, A. Quantum Networks for Elementary Arithmetic Operations. Online preprint quant-ph/9511018, (1996).]]

[29]

Viamontes, G., Rajagopalan, M., Markov, I., and Hayes, J.P. Gate-Level Simulation of Quantum Circuits. Proc. ASP Design Automation Conference, pp.295--301, (2003).]]

Digital Library

Cited By

Upadhyay L(2019)Quantum Cryptography: A SurveyInnovations in Bio-Inspired Computing and Applications10.1007/978-3-030-16681-6_3(20-35)Online publication date: 21-May-2019
https://doi.org/10.1007/978-3-030-16681-6_3
Elhoushi MEl-Kharashi MElrefaei H(2014)Model of a hybrid processor executing C++ with additional quantum functionsMicroprocessors & Microsystems10.5555/2948290.294838238:8(1000-1011)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.5555/2948290.2948382
Udrescu MProdan LVlăduţiu M(2012)Simulated fault injection methodology for gate-level quantum circuit reliability assessmentSimulation Modelling Practice and Theory10.1016/j.simpat.2012.01.00123(60-70)Online publication date: Apr-2012
https://doi.org/10.1016/j.simpat.2012.01.001
Show More Cited By

Index Terms

Using HDLs for describing quantum circuits: a framework for efficient quantum algorithm simulation
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies

Recommendations

T-count optimized quantum circuit for floating point addition and multiplication
Abstract
Quantum computers perform computations using quantum-mechanical phenomena such as superposition and entanglement. Floating-point operations are employed in almost all conventional digital signal processors which evinces that floating-point numbers ...
Visualization of the Quantum Fourier Transform Using a Quantum Computer Simulator

The quantum Fourier transform (QFT) is a key subroutine of quantum algorithms for factoring and simulation and is the heart of the hidden-subgroup problem, the solution of which is expected to lead to the development of new quantum algorithms. The QFT ...
Design of Quantum Circuits for Random Walk Algorithms
ISVLSI '12: Proceedings of the 2012 IEEE Computer Society Annual Symposium on VLSI

A quantum algorithm is defined by a sequence of operations that runs on a realistic model of quantum computation. Since the first quantum algorithm proposed by David Deutsch(1985), a large number of impressive quantum algorithms have been developed. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CF '04: Proceedings of the 1st conference on Computing frontiers

April 2004

522 pages

ISBN:1581137419

DOI:10.1145/977091

General Chair:
Stamatis Vassiliadis
Delft University of Technology, The Netherlands
,
Program Chairs:
Jean-Luc Gaudiot
University of California at Irvine, USA
,
Vincenzo Piuri
University of Milan, Italy

Copyright © 2004 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 April 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CF04

Sponsor:

CF04: Computing Frontiers Conference

April 14 - 16, 2004

Ischia, Italy

Acceptance Rates

Overall Acceptance Rate 273 of 785 submissions, 35%

Upcoming Conference

CF '25

Sponsor:
sigmicro

22nd ACM International Conference on Computing Frontiers

May 28 - 30, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
812
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Upadhyay L(2019)Quantum Cryptography: A SurveyInnovations in Bio-Inspired Computing and Applications10.1007/978-3-030-16681-6_3(20-35)Online publication date: 21-May-2019
https://doi.org/10.1007/978-3-030-16681-6_3
Elhoushi MEl-Kharashi MElrefaei H(2014)Model of a hybrid processor executing C++ with additional quantum functionsMicroprocessors & Microsystems10.5555/2948290.294838238:8(1000-1011)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.5555/2948290.2948382
Udrescu MProdan LVlăduţiu M(2012)Simulated fault injection methodology for gate-level quantum circuit reliability assessmentSimulation Modelling Practice and Theory10.1016/j.simpat.2012.01.00123(60-70)Online publication date: Apr-2012
https://doi.org/10.1016/j.simpat.2012.01.001
Metodi TFaruque AChong F(2011)Quantum Computing for Computer Architects, Second EditionSynthesis Lectures on Computer Architecture10.2200/S00331ED1V01Y201101CAC0136:1(1-203)Online publication date: 14-Mar-2011
https://doi.org/10.2200/S00331ED1V01Y201101CAC013
Elhoushi MEl-Kharashi MElrefaei H(2011)Modeling a quantum processor using the QRAM modelProceedings of 2011 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing10.1109/PACRIM.2011.6032928(409-415)Online publication date: Aug-2011
https://doi.org/10.1109/PACRIM.2011.6032928
Saeedi MSedighi MSaheb Zamani M(2010)A library-based synthesis methodology for reversible logicMicroelectronics Journal10.1016/j.mejo.2010.02.00241:4(185-194)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1016/j.mejo.2010.02.002
Gutiérrez ERomero STrenas MZapata E(2010)Quantum computer simulation using the CUDA programming modelComputer Physics Communications10.1016/j.cpc.2009.09.021181:2(283-300)Online publication date: Feb-2010
https://doi.org/10.1016/j.cpc.2009.09.021
Gutierrez ERomero STrenas MZapata E(2008)Parallel Quantum Computer Simulation on the CUDA ArchitectureProceedings of the 8th international conference on Computational Science, Part I10.1007/978-3-540-69384-0_75(700-709)Online publication date: 23-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-69384-0_75
Prodan LUdrescu MBoncalo OVladutiu M(2007)Design for dependability in emerging technologiesACM Journal on Emerging Technologies in Computing Systems10.1145/1265949.12659523:2(6-es)Online publication date: 1-Jul-2007
https://dl.acm.org/doi/10.1145/1265949.1265952
Boncalo OUdrescu MProdan LVladutiu MAmaricai A(2007)Simulated Fault Injection for Quantum Circuits Based on Simulator Commands2007 4th International Symposium on Applied Computational Intelligence and Informatics10.1109/SACI.2007.375519(245-250)Online publication date: May-2007
https://doi.org/10.1109/SACI.2007.375519
Show More Cited By

View Options

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 Table of Contents