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 International Symposium on Multiple-Valued Logic (ISMVL)

Variable Reordering and Sifting for QMDD

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

Published May 1, 2007• 6 citations
Publisher

Abstract

This paper considers variable reordering for quantum multiple-valued decision diagrams (QMDD) used to represent the matrices describing reversible and quantum gates and circuits. An efficient method for adjacent variable interchange is presented and this method is employed to implement sifting of QMDDs. Experimental results are presented showing the effectiveness of the proposed techniques.

DOI
10.1109/ismvl.2007.59

Related papers

QMDD Minimization using Sifting for Variable Reordering

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

This paper considers variable reordering for quantum multiplevalued decision diagrams (QMDDs) used to represent the matrices describing reversible/quantum gates and circuits. An efficient method for adjacent variable interchange is presented and this method is employed to implement a vertex reduction procedure for QMDDs using sifting. Experimental results are presented showing the effectiveness of the proposed technique.

•Jan 1, 2007•12 citations

Variable Reordering on the QMDD Representation of Quantum Circuits

Sharon Van Schaick, Kenneth Blair Kent

In [1], a novel structure was discussed for representing the matrices that can be built from an n-variable r-valued reversible/quantum circuit. This structure, called a QMDD, takes on a form similar to that of a reduced-orderedbinary-decision-diagram (ROBDD). It is known that the order of variables used for developing an ROBDD from a binary logic circuit is relevant to the size and structure of that ROBDD [3]. This paper determines what effect, if any, variable order has on the QMDD structure and proposes a simple heuristic for choosing a ‘good’ variable order.

•Jan 1, 2007•0 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

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

On the Guidance of Reversible Logic Synthesis by Dynamic Variable Reordering

David Y. Feinstein, Mitchell Aaron Thornton

This paper proposes a framework that improves reversible logic synthesis by employing a dynamically determined variable order for quantum multiple-valued decision diagrams (QMDD). We demonstrate our approach through augmentation of the Miller-Maslov-Dueck (MMD) algorithm that processes the complete function specification in lexicographical order with our technique. We represent and minimize the complete specification with the QMDD and then synthesize the function specification based on the minimized variable order. The framework produces significantly smaller reversible circuits in many cases. Experimental results also show the effectiveness of using the QMDD size as a measure of the complexity of MVL and binary reversible circuits.

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

Analysis of Variable Reordering on the QMDD Representation of Quantum Circuits

Sharon Van Schaick, Kenneth Blair Kent

In previous research, a novel structure was discussed for representing the matrices that can be built from an n-variable r-valued reversible/quantum circuit. This structure, called a QMDD, takes on a form similar to that of a reduced-ordered-binary-decision-diagram (ROBDD). It is known that the order of variables used for developing an ROBDD from a binary logic circuit is relevant to the size and structure of that ROBDD. This paper determines what effect, if any, variable order has on the QMDD structure and proposes a simple heuristic for choosing a 'good' variable order.

Euromicro Conference on Digital System Design (DSD)•Aug 1, 2007•2 citations
This paper considers variable reordering for quantum multiple-valued decision diagrams (QMDD) used to represent the matrices describing reversible and quantum gates and circuits. An efficient method for adjacent variable interchange is presented and this method is employed to implement sifting of QMDDs. Experimental results are presented showing the effectiveness of the proposed techniques.
In [1], a novel structure was discussed for representing the matrices that can be built from an n-variable r-valued reversible/quantum circuit. This structure, called a QMDD, takes on a form similar to that of a reduced-orderedbinary-decision-diagram (ROBDD). It is known that the order of variables used for developing an ROBDD from a binary logic circuit is relevant to the size and structure of that ROBDD [3]. This paper determines what effect, if any, variable order has on the QMDD structure and proposes a simple heuristic for choosing a ‘good’ variable order.
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.
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.
This paper proposes a framework that improves reversible logic synthesis by employing a dynamically determined variable order for quantum multiple-valued decision diagrams (QMDD). We demonstrate our approach through augmentation of the Miller-Maslov-Dueck (MMD) algorithm that processes the complete function specification in lexicographical order with our technique. We represent and minimize the complete specification with the QMDD and then synthesize the function specification based on the minimized variable order. The framework produces significantly smaller reversible circuits in many cases. Experimental results also show the effectiveness of using the QMDD size as a measure of the complexity of MVL and binary reversible circuits.
In previous research, a novel structure was discussed for representing the matrices that can be built from an n-variable r-valued reversible/quantum circuit. This structure, called a QMDD, takes on a form similar to that of a reduced-ordered-binary-decision-diagram (ROBDD). It is known that the order of variables used for developing an ROBDD from a binary logic circuit is relevant to the size and structure of that ROBDD. This paper determines what effect, if any, variable order has on the QMDD structure and proposes a simple heuristic for choosing a 'good' variable order.