Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

QMDDs: Efficient Quantum Function Representation and Manipulation

Philipp Niemann, Robert Wille, D. Michael Miller, Mitchell Aaron Thornton, Rolf Drechsler

Published Jul 21, 2015• 128 citations
Publisher

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.

DOI
10.1109/tcad.2015.2459034

Related papers

Quantum Multiple-Valued Decision Diagrams with Linear Transformations

Yonghong Li, Miao Hao

Due to the rapid development of quantum computing, the compact representation of quantum operations based on decision diagrams has been received more and more attraction. Since variable orders have a significant impact on the size of the decision diagram, identifying a good variable order is of paramount importance. In this paper, we integrate linear transformations into an efficient and canonical form of quantum computing: Quantum Multiple-Valued Decision Diagrams (QMDDs) and develop a novel canonical representation, namely linearly transformed QMDDs (LTQMDDs). We design a linear sifting algorithm for LTQMDDs that search a good linear transformation to obtain a more compact form of quantum function. Experimental results show that the linear sifting algorithm is able to generate decision diagrams that are significantly improved compared with the original sifting algorithm. Moreover, for certain types of circuits, linear sifting algorithm have good performance whereas sifting algorithm does not decrease the size of QMDDs.

arXiv:2207.11395•Jul 23, 2022•0 citations

QMDD: A Decision Diagram Structure for Reversible and Quantum Circuits

D. Michael Miller, Mitchell Aaron Thornton

In this paper, we present a novel structure, QuantumMultiple- valued Decision Diagrams (QMDD), specifically designed to represent and manipulate the matrices encountered in the specification of reversible and quantum gates and circuits, both binary and multiple-valued. QMDD use many common decision diagram techniques, ideas introduced in QuIDDPro and novel techniques introduced here. Building the QMDD for the matrices for individual gates and the subsequent construction of the QMDD for the matrix describing a circuit are discussed. A prototype C implementation is described and experimental results are given that show the new structure is a promising and compact representation for reversible and quantum logic circuits.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•Jan 1, 2006•164 citations

Efficient synthesis of quantum circuits implementing clifford group operations

Philipp Niemann, Robert Wille, Rolf Drechsler

Quantum circuits established themselves as a promising emerging technology and, hence, attracted considerable attention in the domain of computer-aided design. As a result, many approaches for synthesis of corresponding netlists have been proposed in the last decade. However, as the design of quantum circuits faces serious obstacles caused by phenomena such as superposition, entanglement, and phase shifts, automatic synthesis still represents a significant challenge. In this paper, we propose an automatic synthesis approach for quantum circuits that implement Clifford Group operations. These circuits are essential for many quantum applications and cover core aspects of quantum functionality. The proposed approach exploits specific properties of the unitary transformation matrices that are associated to quantum operations. Furthermore, Quantum Multiple-Valued Decision Diagrams (QMDDs) are employed for an efficient representation of these matrices. Experimental results confirm that this enables a compact realization of the respective quantum functionality.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2014•49 citations

How to Efficiently Handle Complex Values? Implementing Decision Diagrams for Quantum Computing

Alwin Zulehner, Stefan Hillmich, Robert Wille

Quantum computing promises substantial speedups by exploiting quantum mechanical phenomena such as superposition and entanglement. Corresponding design methods require efficient means of representation and manipulation of quantum functionality. In the classical domain, decision diagrams have been successfully employed as a powerful alternative to straightforward means such as truth tables. This motivated extensive research on whether decision diagrams provide similar potential in the quantum domain-resulting in new types of decision diagrams capable of substantially reducing the complexity of representing quantum states and functionality. From an implementation perspective, many concepts and techniques from the classical domain can be re-used in order to implement decision diagrams packages for the quantum realm. However, new problems-namely how to efficiently handle complex numbers-arise. In this work, we propose a solution to overcome these problems. Experimental evaluations confirm that this yields improvements of orders of magnitude in the runtime needed to create and to utilize these decision diagrams. The resulting implementation is publicly available as a quantum DD package at http://iic.jku.at/eda/research/quantum_dd.

arXiv:1911.12691•Nov 1, 2019•75 citations

Quantum Multiple-Valued Decision Diagrams Containing Skipped Variables.

David Y. Feinstein, Mitchell Aaron Thornton

Quantum multiple-valued decision diagrams (QMDD) are data structures that enable efficient representation and manipulation of unitary matrices representing reversible and quantum circuits. QMDDs are of the form of a rooted, directed, acyclic graph with initial and terminal vertices where each vertex is annotated with a variable name representing a circuit line. Directed paths from the intial to a terminal vertex can be represented as a sequence of variable names in the order in which they appear in the path. The existence of QMDD paths that do not contain all variable names, or “skipped variables”, has direct ramifications in the formula-tion of synthesis and other algorithms for reversible and quantum logic. Skipped variables are generally rare and tend to appear in quantum circuits that are intended to operate using superimposed values on the control lines. We have found that a unitary matrix representing a circuit whose QMDD contains skipped variables is likely to exhibit a specific anomaly when decomposed into a cascade of unitary matrices using the Reck-Zeilinger-Bernstein-Bertani algorithm.

•Jan 1, 2015•2 citations

Quantum Multiple-Valued Decision Diagrams in Graphical Calculi

Renaud Vilmart

Graphical calculi such as the ZH-calculus are powerful tools in the study and analysis of quantum processes, with links to other models of quantum computation such as quantum circuits, measurement-based computing, etc. A somewhat compact but systematic way to describe a quantum process is through the use of quantum multiple-valued decision diagrams (QMDDs), which have already been used for the synthesis of quantum circuits as well as for verification. We show in this paper how to turn a QMDD into an equivalent ZH-diagram, and vice-versa, and show how reducing a QMDD translates in the ZH-Calculus, hence allowing tools from one formalism to be used into the other.

arXiv:2107.01186•Leibniz international proceedings in informatics•Jan 1, 2021•0 citations
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.
Due to the rapid development of quantum computing, the compact representation of quantum operations based on decision diagrams has been received more and more attraction. Since variable orders have a significant impact on the size of the decision diagram, identifying a good variable order is of paramount importance. In this paper, we integrate linear transformations into an efficient and canonical form of quantum computing: Quantum Multiple-Valued Decision Diagrams (QMDDs) and develop a novel canonical representation, namely linearly transformed QMDDs (LTQMDDs). We design a linear sifting algorithm for LTQMDDs that search a good linear transformation to obtain a more compact form of quantum function. Experimental results show that the linear sifting algorithm is able to generate decision diagrams that are significantly improved compared with the original sifting algorithm. Moreover, for certain types of circuits, linear sifting algorithm have good performance whereas sifting algorithm does not decrease the size of QMDDs.
In this paper, we present a novel structure, QuantumMultiple- valued Decision Diagrams (QMDD), specifically designed to represent and manipulate the matrices encountered in the specification of reversible and quantum gates and circuits, both binary and multiple-valued. QMDD use many common decision diagram techniques, ideas introduced in QuIDDPro and novel techniques introduced here. Building the QMDD for the matrices for individual gates and the subsequent construction of the QMDD for the matrix describing a circuit are discussed. A prototype C implementation is described and experimental results are given that show the new structure is a promising and compact representation for reversible and quantum logic circuits.
Quantum circuits established themselves as a promising emerging technology and, hence, attracted considerable attention in the domain of computer-aided design. As a result, many approaches for synthesis of corresponding netlists have been proposed in the last decade. However, as the design of quantum circuits faces serious obstacles caused by phenomena such as superposition, entanglement, and phase shifts, automatic synthesis still represents a significant challenge. In this paper, we propose an automatic synthesis approach for quantum circuits that implement Clifford Group operations. These circuits are essential for many quantum applications and cover core aspects of quantum functionality. The proposed approach exploits specific properties of the unitary transformation matrices that are associated to quantum operations. Furthermore, Quantum Multiple-Valued Decision Diagrams (QMDDs) are employed for an efficient representation of these matrices. Experimental results confirm that this enables a compact realization of the respective quantum functionality.
Quantum computing promises substantial speedups by exploiting quantum mechanical phenomena such as superposition and entanglement. Corresponding design methods require efficient means of representation and manipulation of quantum functionality. In the classical domain, decision diagrams have been successfully employed as a powerful alternative to straightforward means such as truth tables. This motivated extensive research on whether decision diagrams provide similar potential in the quantum domain-resulting in new types of decision diagrams capable of substantially reducing the complexity of representing quantum states and functionality. From an implementation perspective, many concepts and techniques from the classical domain can be re-used in order to implement decision diagrams packages for the quantum realm. However, new problems-namely how to efficiently handle complex numbers-arise. In this work, we propose a solution to overcome these problems. Experimental evaluations confirm that this yields improvements of orders of magnitude in the runtime needed to create and to utilize these decision diagrams. The resulting implementation is publicly available as a quantum DD package at http://iic.jku.at/eda/research/quantum_dd.
Quantum multiple-valued decision diagrams (QMDD) are data structures that enable efficient representation and manipulation of unitary matrices representing reversible and quantum circuits. QMDDs are of the form of a rooted, directed, acyclic graph with initial and terminal vertices where each vertex is annotated with a variable name representing a circuit line. Directed paths from the intial to a terminal vertex can be represented as a sequence of variable names in the order in which they appear in the path. The existence of QMDD paths that do not contain all variable names, or “skipped variables”, has direct ramifications in the formula-tion of synthesis and other algorithms for reversible and quantum logic. Skipped variables are generally rare and tend to appear in quantum circuits that are intended to operate using superimposed values on the control lines. We have found that a unitary matrix representing a circuit whose QMDD contains skipped variables is likely to exhibit a specific anomaly when decomposed into a cascade of unitary matrices using the Reck-Zeilinger-Bernstein-Bertani algorithm.
Graphical calculi such as the ZH-calculus are powerful tools in the study and analysis of quantum processes, with links to other models of quantum computation such as quantum circuits, measurement-based computing, etc. A somewhat compact but systematic way to describe a quantum process is through the use of quantum multiple-valued decision diagrams (QMDDs), which have already been used for the synthesis of quantum circuits as well as for verification. We show in this paper how to turn a QMDD into an equivalent ZH-diagram, and vice-versa, and show how reducing a QMDD translates in the ZH-Calculus, hence allowing tools from one formalism to be used into the other.