research-article

QMDDs: Efficient Quantum Function Representation and Manipulation

Authors:

Philipp Niemann,

David Michael Miller,

Mitchell A. Thornton,

Rolf DrechslerAuthors Info & Claims

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 35, Issue 1

Pages 86 - 99

https://doi.org/10.1109/TCAD.2015.2459034

Published: 01 January 2016 Publication History

Abstract

Quantum mechanical phenomena such as phase shifts, superposition, and entanglement show promise in use for computation. Suitable technologies for the modeling and design of quantum computers and other information processing techniques that exploit quantum mechanical principles are in the range of vision. Quantum algorithms that significantly speed up the process of solving several important computation problems have been proposed in the past. The most common representation of quantum mechanical phenomena are transformation matrices. However, the transformation matrices grow exponentially with the size of a quantum system and, thus, pose significant challenges for efficient representation and manipulation of quantum functionality. In order to address this problem, first approaches for the representation of quantum systems in terms of decision diagrams have been proposed. One very promising approach is given by Quantum Multiple-Valued Decision Diagrams (QMDDs) which are able to efficiently represent transformation matrices and also inherently support multiple-valued basis states offered by many physical quantum systems. However, the initial proposal of QMDDs was lacking in a formal basis and did not allow, e.g., the change of the variable order—an established core functionality in decision diagrams which is crucial for determining more compact representations. Because of this, the full potential of QMDDs or decision diagrams for quantum functionality in general has not been fully exploited yet. In this paper, we present a refined definition of QMDDs for the general quantum case. Furthermore, we provide significantly improved computational methods for their use and manipulation and show that the resulting representation satisfies important criteria for a decision diagram, i.e., compactness and canonicity. An experimental evaluation confirms the efficiency of QMDDs.

References

[1]

M. Nielsen and I. Chuang, Quantum Computation and Quantum Information. New York, NY, USA: Cambridge Univ. Press, 2000.

[2]

P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,” in Proc. Found. Comput. Sci., Santa Fe, NM, USA, 1994, pp. 124–134.

[3]

L. M. K. Vandersypen et al., “Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance,” Nature, vol. 414, pp. 883–887, Dec. 2001.

[4]

L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proc. Theory Comput., Philadelphia, PA, USA, 1996, pp. 212–219.

[5]

A. Abdollahi and M. Pedram, “Analysis and synthesis of quantum circuits by using quantum decision diagrams,” in Proc. Design Autom. Test Europe, 2006, pp. 317–322.

[6]

M. Soeken, R. Wille, C. Hilken, N. Przigoda, and R. Drechsler, “Synthesis of reversible circuits with minimal lines for large functions,” in Proc. ASP Design Autom. Conf., Sydney, NSW, Australia, 2012, pp. 85–92.

[7]

P. Niemann, R. Wille, and R. Drechsler, “Efficient synthesis of quantum circuits implementing clifford group operations,” in Proc. ASP Design Autom. Conf., Singapore, 2014, pp. 483–488.

[8]

R. Wille, D. Große, D. M. Miller, and R. Drechsler, “Equivalence checking of reversible circuits,” in Proc. Int Symp. Mult.-Valued Logic, Naha, Japan, 2009, pp. 324–330.

[9]

G. Viamontes, I. Markov, and J. Hayes, “High-performance QuIDD-based simulation of quantum circuits,” in Proc. Design Autom. Test Europe, Paris, France, 2004, pp. 1354–1355.

[10]

R. E. Bryant, “Graph-based algorithms for Boolean function manipulation,” IEEE Trans. Comput., vol. C-35, no. 8, pp. 677–691, Aug. 1986.

Digital Library

[11]

G. F. Viamontes, M. Rajagopalan, I. L. Markov, and J. P. Hayes, “Gate-level simulation of quantum circuits,” in Proc. ASP Design Autom. Conf., Kitakyushu, Japan, 2003, pp. 295–301.

[12]

D. M. Miller and M. A. Thornton, “QMDD: A decision diagram structure for reversible and quantum circuits,” in Proc. Int. Symp. Mult.-Valued Logic, 2006, p. 6.

[13]

D. M. Miller and M. A. Thornton, Multiple-Valued Logic: Concepts and Representations. San Rafael, CA, USA: Morgan and Claypool, 2008.

[14]

D. Goodman, M. A. Thornton, D. Y. Feinstein, and D. M. Miller, “Quantum logic circuit simulation based on the QMDD data structure,” in Proc. Int. Reed-Muller Workshop, Oslo, Norway, 2007, pp. 99–105.

[15]

R. Rudell, “Dynamic variable ordering for ordered binary decision diagrams,” in Proc. Int. Conf. CAD, Santa Clara, CA, USA, 1993, pp. 42–47.

[16]

P. Niemann, R. Wille, and R. Drechsler, “On the ‘Q’ in QMDDs: Efficient representation of quantum functionality in the QMDD data-structure,” in Proc. Int. Conf. Revers. Comput., Victoria, BC, Canada, 2013, pp. 125–140.

[17]

C. G. Khatri and C. R. Rao, “Solutions to some functional equations and their applications to characterization of probability distributions,” Sankhya, vol. 30, no. 2, pp. 167–180, 1968.

[18]

X. Zhang, Z. Yang, and C. Cao, “Inequalities involving Khatri-Rao products of positive semi-definite matrices,” Appl. Math. E-notes, vol. 2, pp. 117–124, 2002.

[19]

D. M. Miller, D. Y. Feinstein, and M. A. Thornton, “QMDD minimization using sifting for variable reordering,” Mult.-Valued Logic Soft Comput., vol. 13, nos. 4–6, pp. 537–552, 2007.

[20]

D. Y. Feinstein, M. A. Thornton, and D. M. Miller, “Minimization of quantum multiple-valued decision diagrams using data structure metrics,” Mult.-Valued Logic Soft Comput., vol. 15, no. 4, pp. 361–377, 2009.

[21]

D. Y. Feinstein and M. A. Thornton, “On the skipped variables of quantum multiple-valued decision diagrams,” in Proc. Int. Symp. Mult.-Valued Logic, Tuusula, Finland, 2011, pp. 164–169.

[22]

N. D. Mermin, Quantum Computer Science: An Introduction. New York, NY, USA: Cambridge Univ. Press, 2007.

Cited By

Burgholzer LJimenez-Pastor ALarsen KTribastone MTschaikowski MWille R(2025)Forward and Backward Constrained Bisimulations for Quantum Circuits Using Decision DiagramsACM Transactions on Quantum Computing10.1145/37127116:2(1-21)Online publication date: 18-Jan-2025
https://dl.acm.org/doi/10.1145/3712711
Lopez-Oliva VBadia JCastillo M(2025)Efficient quantum circuit contraction using tensor decision diagramsThe Journal of Supercomputing10.1007/s11227-024-06836-w81:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06836-w
Sistla MChaudhuri SReps T(2024)Weighted Context-Free-Language Ordered Binary Decision DiagramsProceedings of the ACM on Programming Languages10.1145/36897608:OOPSLA2(1390-1419)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689760
Show More Cited By

Index Terms

QMDDs: Efficient Quantum Function Representation and Manipulation
1. Theory of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Efficient Representation and Learning of Quantum Many-Body States
Duality quantum computer and the efficient quantum simulations

Duality quantum computing is a new mode of a quantum computer to simulate a moving quantum computer passing through a multi-slit. It exploits the particle wave duality property for computing. A quantum computer with n qubits and a qudit simulates a ...
Quantum correlation swapping

Quantum correlations (QCs), including quantum entanglement and those different, are important quantum resources and have attracted much attention recently. Quantum entanglement swapping as a kernel technique has already been applied to quantum repeaters ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Volume 35, Issue 1

Jan. 2016

170 pages

ISSN:0278-0070

Issue’s Table of Contents

Copyright © 2015.

Publisher

IEEE Press

Publication History

Published: 01 January 2016

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Burgholzer LJimenez-Pastor ALarsen KTribastone MTschaikowski MWille R(2025)Forward and Backward Constrained Bisimulations for Quantum Circuits Using Decision DiagramsACM Transactions on Quantum Computing10.1145/37127116:2(1-21)Online publication date: 18-Jan-2025
https://dl.acm.org/doi/10.1145/3712711
Lopez-Oliva VBadia JCastillo M(2025)Efficient quantum circuit contraction using tensor decision diagramsThe Journal of Supercomputing10.1007/s11227-024-06836-w81:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06836-w
Sistla MChaudhuri SReps T(2024)Weighted Context-Free-Language Ordered Binary Decision DiagramsProceedings of the ACM on Programming Languages10.1145/36897608:OOPSLA2(1390-1419)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689760
Fang WYing M(2024)Symbolic Execution for Quantum Error Correction ProgramsProceedings of the ACM on Programming Languages10.1145/36564198:PLDI(1040-1065)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656419
Beaumont JWakevainen KMonga MLonati VBarendsen ESheard JPaterson J(2024)Scalable Autograding for Quantum Programming AssignmentsProceedings of the 2024 on Innovation and Technology in Computer Science Education V. 110.1145/3649217.3653619(457-463)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1145/3649217.3653619
Matsuo RRaymond RYamashita SMinato SKim T(2024)Optimizing Decision Diagrams for Measurements of Quantum CircuitsProceedings of the 29th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC58780.2024.10473869(134-139)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1109/ASP-DAC58780.2024.10473869
Dai AYing M(2024)QReach: A Reachability Analysis Tool for Quantum Markov ChainsComputer Aided Verification10.1007/978-3-031-65633-0_23(520-532)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-65633-0_23
Chen YChung KLengál OLin JTsai WYen D(2023)An Automata-Based Framework for Verification and Bug Hunting in Quantum CircuitsProceedings of the ACM on Programming Languages10.1145/35912707:PLDI(1218-1243)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591270
Liu HLi YChen YWang CTakahashi A(2023)A Robust Approach to Detecting Non-Equivalent Quantum Circuits Using Specially Designed StimuliProceedings of the 28th Asia and South Pacific Design Automation Conference10.1145/3566097.3567935(696-701)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1145/3566097.3567935
Burgholzer LPloier AWille R(2023)Simulation Paths for Quantum Circuit Simulation With Decision Diagrams What to Learn From Tensor Networks, and What NotIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.319796942:4(1113-1122)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TCAD.2022.3197969
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents