Abstract
The Quantum Multiple-valued Decision Diagram (QMDD) data-structure has been introduced as a means for an efficient representation and manipulation of transformation matrices realized by quantum or reversible logic circuits. A particular challenge is the handling of arbitrary complex numbers as they frequently occur in quantum functionality. These numbers are represented through edge weights which, however, represent a severe obstacle with respect to canonicity, modifiability, and applicability of QMDDs. Previously introduced approaches did not provide a satisfactory solution to these obstacles. In this paper, we propose an improved factorization scheme for complex numbers that ensures a canonical representation while, at the same time, allows for local changes. We demonstrate how the proposed solution can be exploited to improve the data-structure itself (e.g. through variable re-ordering enabled by the advanced modifiability) and how applications such as equivalence checking benefit from that.
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
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge Univ. Press (2000)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Theory of Computing, pp. 212–219 (1996)
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. Foundations of Computer Science, 124–134 (1994)
Dürr, C., Heiligman, M., Høyer, P., Mhalla, M.: Quantum query complexity of some graph problems. SIAM J. Comput. 35(6), 1310–1328 (2006)
Wang, S.A., Lu, C.Y., Tsai, I.M., Kuo, S.Y.: An XQDD-based verification method for quantum circuits. IEICE Transactions 91-A(2), 584–594 (2008)
Viamontes, G.F., Markov, I.L., Hayes, J.P.: Quantum Circuit Simulation. Springer, Heidelberg (2009)
Miller, D.M., Thornton, M.A.: QMDD: A decision diagram structure for reversible and quantum circuits. In: Int’l Symp. on Multi-Valued Logic, p. 6 (2006)
Wille, R., Große, D., Miller, D.M., Drechsler, R.: Equivalence checking of reversible circuits. In: Int’l Symp. on Multi-Valued Logic, pp. 324–330 (2009)
Seiter, J., Soeken, M., Wille, R., Drechsler, R.: Property checking of quantum circuits using quantum multiple-valued decision diagrams. In: Glück, R., Yokoyama, T. (eds.) RC 2012. LNCS, vol. 7581, pp. 183–196. Springer, Heidelberg (2013)
Soeken, M., Wille, R., Hilken, C., Przigoda, N., Drechsler, R.: Synthesis of Reversible Circuits with Minimal Lines for Large Functions. In: Asia and South Pacific Design Automation Conference (January 2012)
Bullock, S.S., O’Leary, D.P., Brennen, G.K.: Asymptotically optimal quantum circuits for d-level systems. Phys. Rev. Lett. 94, 230502 (2005)
Miller, D.M., Feinstein, D.Y., Thornton, M.A.: Qmdd minimization using sifting for variable reordering. Journal of Multiple-valued Logic and Soft Computing, 537–552 (2007)
Miller, D.M., Thornton, M.A.: Multiple-Valued Logic: Concepts and Representations. Morgan and Claypool (2008)
Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. on Comp. 35(8), 677–691 (1986)
Mermin, N.D.: Quantum computer science: an introduction, vol. 1. Cambridge University Press (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Niemann, P., Wille, R., Drechsler, R. (2013). On the “Q” in QMDDs: Efficient Representation of Quantum Functionality in the QMDD Data-Structure. In: Dueck, G.W., Miller, D.M. (eds) Reversible Computation. RC 2013. Lecture Notes in Computer Science, vol 7948. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38986-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-38986-3_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38985-6
Online ISBN: 978-3-642-38986-3
eBook Packages: Computer ScienceComputer Science (R0)