© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

IEEE International Symposium on Multiple-Valued Logic (ISMVL)

Heterogeneous Decision Diagrams for Applications in Harmonic Analysis on Finite Non-Abelian Groups

Stanislav Stanković, Jaakko T. Astola, D. Michael Miller, Radomir S. Stanković

Published Jan 1, 2010• 4 citations

Abstract

Spectral techniques on Abelian groups are a well-established tool in diverse fields such as signal processing, switching theory, multi-valued logic and logic design. The harmonic analysis on finite non-Abelian groups is an extension of them, which has also found applications for particular tasks in the same fields. It takes advantages of the peculiar features of the domain groups and their dual objects. Representing unitary irreducible representations, that are kernels of Fourier transforms on non-Abelian groups, in a compact manner is a key task in this area. These representations are usually specified in terms of rectangular matrices with matrix entries. Therefore, the problem of their efficient representations can be viewed as handling large rectangular matrices with matrix-valued entries. Quantum Multiple-valued Decision Diagrams (QMDDs) and Heterogeneous Decision Diagrams (HDDs) have been used for representation of matrices with numerical values, under some restrictions to the order of matrices to be represented. In this paper, we present a generalization of this concept for the representation of rectangular matrices with matrix-valued entries. We also demonstrate an implementation of an XML-based software package aimed at handling such data structures.

DOI: 10.1109/ismvl.2010.63

Related papers

Fourier decision diagrams on finite non-Abelian groups with preprocessing

Ratko Stanković

This paper introduces a method for optimization of Fourier decision diagrams representations of discrete functions based on the preprocessing of the represented functions. Fourier decision diagrams are defined for matrix-valued-function on non-Abelian groups. Their application to number-valued functions is provided through a simple preprocessing of the represented functions.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•Nov 22, 2002•13 citations

QMDDs: Efficient Quantum Function Representation and Manipulation

Philipp Niemann, Robert Wille, D. Michael Miller +2 more

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.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Jul 21, 2015•128 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

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

On the Data Structure Metrics of Quantum Multiple-Valued Decision Diagrams

David Y. Feinstein, Mitchell Aaron Thornton, D. Michael Miller

This paper describes new metrics for the data structure referred to as quantum multiple-valued decision diagrams (QMDD) which are used to represent the matrices describing reversible and quantum gates and circuits. These metrics provide information about QMDD that allows for improvement of minimization techniques. We explore metrics related to the frequency of edges with non-zero weight for the entire QMDD data structure and their histograms with respect to each variable. We observe some unique regularity particular to the methodology of the QMDD. We develop new heuristics for QMDD dynamic variable ordering (DVO) that are guided by the proposed metrics. Experimental results show the effectiveness of the proposed techniques.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2008•4 citations

Using QMDD in Numerical Methods for Solving Linear Differential Equations via Walsh Functions

Radomir S. Stanković, D. Michael Miller

This paper discusses the acceleration of computations involved in methods for solving a certain class of differential equations by Walsh series. These methods are based on computations with matrices of relatively large dimensions but having a block structure and including also the dyadic convolution matrices. We propose to represent the involved matrices by Quantum multiple-valued decision diagrams (QMDDs) and perform the computations over them. The structure of the matrices means the QMDDs are reasonably compact and therefore offer possibilities to speed up the overall computations as well as to work with matrices of large dimension which improves accuracy of the approximation of the required solutions by finite Walsh series.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2015•3 citations

Spectral techniques on Abelian groups are a well-established tool in diverse fields such as signal processing, switching theory, multi-valued logic and logic design. The harmonic analysis on finite non-Abelian groups is an extension of them, which has also found applications for particular tasks in the same fields. It takes advantages of the peculiar features of the domain groups and their dual objects. Representing unitary irreducible representations, that are kernels of Fourier transforms on non-Abelian groups, in a compact manner is a key task in this area. These representations are usually specified in terms of rectangular matrices with matrix entries. Therefore, the problem of their efficient representations can be viewed as handling large rectangular matrices with matrix-valued entries. Quantum Multiple-valued Decision Diagrams (QMDDs) and Heterogeneous Decision Diagrams (HDDs) have been used for representation of matrices with numerical values, under some restrictions to the order of matrices to be represented. In this paper, we present a generalization of this concept for the representation of rectangular matrices with matrix-valued entries. We also demonstrate an implementation of an XML-based software package aimed at handling such data structures.

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.

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 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.

This paper describes new metrics for the data structure referred to as quantum multiple-valued decision diagrams (QMDD) which are used to represent the matrices describing reversible and quantum gates and circuits. These metrics provide information about QMDD that allows for improvement of minimization techniques. We explore metrics related to the frequency of edges with non-zero weight for the entire QMDD data structure and their histograms with respect to each variable. We observe some unique regularity particular to the methodology of the QMDD. We develop new heuristics for QMDD dynamic variable ordering (DVO) that are guided by the proposed metrics. Experimental results show the effectiveness of the proposed techniques.

This paper discusses the acceleration of computations involved in methods for solving a certain class of differential equations by Walsh series. These methods are based on computations with matrices of relatively large dimensions but having a block structure and including also the dyadic convolution matrices. We propose to represent the involved matrices by Quantum multiple-valued decision diagrams (QMDDs) and perform the computations over them. The structure of the matrices means the QMDDs are reasonably compact and therefore offer possibilities to speed up the overall computations as well as to work with matrices of large dimension which improves accuracy of the approximation of the required solutions by finite Walsh series.