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

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: Peter J. Ashenden, The Designer's Guide to VHDL, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 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: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 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: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 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: Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
• 13: L. Hales , S. Hallgren, An improved quantum Fourier transform algorithm and applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.515, November 12-14, 2000
• 14: A. K. Lenstra , H. W. Lenstra, Jr. , M. S. Manasse , J. M. Pollard, The number field sieve, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.564-572, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100295]
• 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: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 18: Kevin M. Obenland , Alvin M. Despain, Simulating the Effect of Decoherence and Inaccuracies on a Quantum Computer, Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, p.447-459, February 17-20, 1998
• 19: Omer, B. Quantum Programming in QCL. Technical Report, Institute of Information Systems, Technical University of Vienna (2000).
• 20: Behrooz Parhami, Computer arithmetic: algorithms and hardware designs, Oxford University Press, Oxford, 1999
• 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).
• 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: Tommaso Toffoli, Reversible Computing, Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.632-644, July 14-18, 1980
• 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: George F. Viamontes , Manoj Rajagopalan , Igor L. Markov , John P. Hayes, Gate-level simulation of quantum circuits, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119829]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Languages, Performance, Theory

Keywords:
bubble logic, entanglement, hardware description languages, quantum algorithms, quantum circuits, simulation, views