Gate-level simulation of quantum circuits

ABSTRACT

Simulating quantum computation on a classical computer is a difficult problem. The matrices representing quantum gates, and vectors modeling qubit states grow exponentially with an increase in the number of qubits. However, by using a new data structure called the Quantum Information Decision Diagram (QuIDD) that exploits the structure of quantum operators, many of these matrices and vectors can be represented in a form that grows polynomially. Using QuIDDs, we implemented a general-purpose quantum computing simulator in C++ called QuIDDPro and tested it on Grover's algorithm. Our QuIDD technique asymptotically outperforms other known simulation techniques.

REFERENCES

• 1: C. Y. Lee, "Representation of switching circuits by binary decision diagrams," Bell System Tech. J., Vol. 38, pp. 985--999, 1959.
• 2: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 3: Anthony J. G. Hey, Feynman and computation: exploring the limits of computers, Perseus Books, Cambridge, MA, 1999
• 4: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 5: E. Clarke et al., "Multi-terminal binary decision diagrams and hybrid decision diagrams," in T. Sasao and M. Fujita, eds, Representations of Discrete Functions, pp. 93--108, Kluwer, 1996.
• 6: R. Iris Bahar , Erica A. Frohm , Charles M. Gaona , Gary D. Hachtel , Enrico Macii , Abelardo Pardo , Fabio Somenzi, Algebraic decision diagrams and their applications, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.188-191, November 07-11, 1993, Santa Clara, California, United States
• 7: D. Greve, "QDD: a quantum computer emulation library," 1999 http://home.plutonium.net/~dagreve/qdd.html
• 8: A. N. Al-Rabadi et al., "Multiple-Valued Quantum Logic," 11th International Workshop on Post Binary ULSI, Boston, MA., May 2002.
• 9: D. Gottesman, "The Heisenberg representation of quantum computers," Plenary speech at the 1998 International Conference on Group Theoretic Methods in Physics, quant-ph/9807006.
• 10: G. Viamontes, M. Rajagopalan, I. Markov, J. Hayes, "Gate-level simulation of quantum circuits," Los Alamos Quantum Physics Archive, Aug. 2002 http://xxx.lanl.gov/abs/quant-ph/0208003
• 11: "GNU MP (GMP): Arithmetic Without Limitations," http://www.swox.com/gmp/
• 12: G. Hachtel et al., "Markovian analysis of large finite state machines," IEEE Trans. on Computer-Aided Design, Vol. 15, pp. 1479--1493, Dec. 1996.
• 13: F. Somenzi, "CUDD: CU Decision Diagram Package," release 2.3.0, Univ. of Colorado at Boulder, 1998.
• 14: L. Grover, "Quantum Mechanics Helps In Searching For A Needle In A Haystack," Phys. Rev. Lett. (79), pp. 325--8, 1997.
• 15: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 16: M. Boyer, G. Brassard, P. Hoyer and A. Tapp, "Tight bounds on quantum searching," 4th Workshop on Physics and Computation, Nov. 1996.
• 17: A. Barenco et al., "Elementary gates for quantum computation", Los Alamos Quantum Physics Archive, quant-ph/9503016, Mar. 1995.