Abstract
In this paper we develop novel algorithms for the simulation of quantum circuits on classical computers. The most efficient techniques previously studied, represent both quantum state vectors and quantum operator matrices as Multi-Terminal Binary Decision Diagrams (MTBDDS). This paper shows how to avoid representing quantum operators as matrices. Instead, we introduce a class of quantum operators that can be represented more compactly using a symbolic, BDD-based representation. We propose algorithms that apply operators on quantum states, using the symbolic representation. Our algorithms are shown to have superior performance over previous techniques, both asymptotically and experimentally.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdollahi, A., Pedram, M.: Analysis and synthesis of quantum circuits by using quantum decision diagrams. In: DATE 2006: Proc. of the Conf. on Design, Automation and Test in Europe, 3001 Leuven, Belgium, pp. 317–322. European Design and Automation Association (2006)
Beckman, D., Chari, A.N., Devabhaktuni, S., Preskill, J.: Efficient networks for quantum factoring. Phys. Rev. A 54(2), 1034–1063 (1996)
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35(8), 677–691 (1986)
Fujita, M., McGeer, P.C., Yang, J.C.-Y.: Multi-terminal binary decision diagrams: An efficient data structure for matrix representation. Form. Methods Syst. Des. 10(2-3), 149–169 (1997)
Minato, S.i.: Zero-suppressed BDDs for set manipulation in combinatorial problems. In: DAC 1993: Proceedings of the 30th international conference on Design automation, pp. 272–277. ACM Press, New York (1993)
Koufogiannakis, C.: Techniques for simulating quantum computers. Master’s thesis, Technical U. of Crete (2004)
Miller, D.M., Thornton, M.A., Goodman, D.: Qmdd: A decision diagram structure for reversible and quantum circuits. In: IEEE Int’l Symp. on Multiple-Valued Logic (ISMVL), pp. 30–30 (2006)
Misra, J.: Powerlist: a structure for parallel recursion. ACM Trans. Program. Lang. Syst. 16(6), 1737–1767 (1994)
Niwa, J., Matsumoto, K., Imai, H.: General-purpose parallel simulator for quantum computing. Phys. Rev. A 66(6), 062317 (2002)
Viamontes, G., Markov, I., Hayes, J.: Improving gate-level simulation of quantum circuits. Quantum Information Processing 2(5), 347–380 (2003)
Viamontes, G.F., Markov, I.L., Hayes, J.P.: Graph-based simulation of quantum computation in the density matrix representation. Quantum Information Processing 5(2), 113–130 (2005)
Viamontes, G.F.: Gate-level simulation of quantum circuits. In: Proc. of the 6th Intl. Conference on Quantum Communication, Measurement, and Computing, pp. 311–314 (2002)
Viamontes, G.F.: Efficient Quantum Circuit Simulation. PhD thesis, University of Michigan (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Samoladas, V. (2008). Improved BDD Algorithms for the Simulation of Quantum Circuits. In: Halperin, D., Mehlhorn, K. (eds) Algorithms - ESA 2008. ESA 2008. Lecture Notes in Computer Science, vol 5193. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87744-8_60
Download citation
DOI: https://doi.org/10.1007/978-3-540-87744-8_60
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87743-1
Online ISBN: 978-3-540-87744-8
eBook Packages: Computer ScienceComputer Science (R0)