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 Computers

An Extended XQDD Representation for Multiple-Valued Quantum Logic

Chin-Yung Lu, Shiou-An Wang, Sy‐Yen Kuo

Published Jun 28, 2011• 7 citations
Publisher

Abstract

X-decomposition Quantum Decision Diagram (XQDD) can represent a quantum operation and perform matrix operations. It can be used to verify quantum and reversible circuits even if the reversible circuits have different number of garbage qubits. It is efficient in terms of space and time. In this paper, we extend the original XQDD to multiple-valued quantum logic. The extended XQDD can represent a multiple-valued quantum operation and perform matrix operations. It can be used to check the equivalence of two multiple-valued quantum or reversible circuits which are synthesized by different approaches. In this paper, we show that the space in multiple-valued XQDD is less than other representations and it is much better than multiple-valued QuIDD and very close to QMDD in terms of time.

DOI
10.1109/tc.2011.114

Related papers

An XQDD-Based Verification Method for Quantum Circuits

Sung-Wen Wang, Chin-Yung Lu, I.-M. Tsai +1 more

Synthesis of quantum circuits is essential for building quantum computers. It is important to verify that the circuits designed perform the correct functions. In this paper, we propose an algorithm which can be used to verify the quantum circuits synthesized by any method. The proposed algorithm is based on BDD (Binary Decision Diagram) and is called X-decomposition Quantum Decision Diagram (XQDD). In this method, quantum operations are modeled using a graphic method and the verification process is based on comparing these graphic diagrams. We also develop an algorithm to verify reversible circuits even if they have a different number of garbage qubits. In most cases, the number of nodes used in XQDD is less than that in other representations. In general, the proposed method is more efficient in terms of space and time and can be used to verify many quantum circuits in polynomial time.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Feb 1, 2008•105 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

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

Variable Reordering and Sifting for QMDD

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

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.

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

Generalizing the Concept of Scalable Reversible Circuit Synthesis for Multiple-Valued Logic

Alwin Zulehner, P. Mercy Nesa Rani, Kamalika Datta +2 more

Research on reversible circuits has gained significance due to its application in quantum computations and many further areas such as the design of encoders. At the same time, the use of multiple-valued logic gained importance since this reduces the number of required entities in physical systems (e.g. in a future quantum computer). While most research is still conducted in the Boolean domain, there exist only few approaches which realize reversible circuits for multiple-valued logic. Moreover, most of the previously proposed solutions for synthesis of multiple-valued reversible circuits are not scalable and consider ternary (i.e. 3-valued circuits) only. Instead of overcoming these issues by developing new synthesis approaches for multiple-valued reversible circuits from scratch, we propose to utilize the recent accomplishments in the design of Boolean reversible circuits and to generalize them for multiple-valued logic. To this end, we discuss how to generalize Quantum Multiple-valued Decision Diagram based (QMDD-based) synthesis - a synthesis approach for Boolean reversible circuits which has been proven to be scalable and which has been used in several recently developed design flows. The discussions eventually show how to bridge the development gap between Boolean and multiple-valued logic for reversible circuits.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2018•2 citations
X-decomposition Quantum Decision Diagram (XQDD) can represent a quantum operation and perform matrix operations. It can be used to verify quantum and reversible circuits even if the reversible circuits have different number of garbage qubits. It is efficient in terms of space and time. In this paper, we extend the original XQDD to multiple-valued quantum logic. The extended XQDD can represent a multiple-valued quantum operation and perform matrix operations. It can be used to check the equivalence of two multiple-valued quantum or reversible circuits which are synthesized by different approaches. In this paper, we show that the space in multiple-valued XQDD is less than other representations and it is much better than multiple-valued QuIDD and very close to QMDD in terms of time.
Synthesis of quantum circuits is essential for building quantum computers. It is important to verify that the circuits designed perform the correct functions. In this paper, we propose an algorithm which can be used to verify the quantum circuits synthesized by any method. The proposed algorithm is based on BDD (Binary Decision Diagram) and is called X-decomposition Quantum Decision Diagram (XQDD). In this method, quantum operations are modeled using a graphic method and the verification process is based on comparing these graphic diagrams. We also develop an algorithm to verify reversible circuits even if they have a different number of garbage qubits. In most cases, the number of nodes used in XQDD is less than that in other representations. In general, the proposed method is more efficient in terms of space and time and can be used to verify many quantum circuits in polynomial time.
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.
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.
Research on reversible circuits has gained significance due to its application in quantum computations and many further areas such as the design of encoders. At the same time, the use of multiple-valued logic gained importance since this reduces the number of required entities in physical systems (e.g. in a future quantum computer). While most research is still conducted in the Boolean domain, there exist only few approaches which realize reversible circuits for multiple-valued logic. Moreover, most of the previously proposed solutions for synthesis of multiple-valued reversible circuits are not scalable and consider ternary (i.e. 3-valued circuits) only. Instead of overcoming these issues by developing new synthesis approaches for multiple-valued reversible circuits from scratch, we propose to utilize the recent accomplishments in the design of Boolean reversible circuits and to generalize them for multiple-valued logic. To this end, we discuss how to generalize Quantum Multiple-valued Decision Diagram based (QMDD-based) synthesis - a synthesis approach for Boolean reversible circuits which has been proven to be scalable and which has been used in several recently developed design flows. The discussions eventually show how to bridge the development gap between Boolean and multiple-valued logic for reversible circuits.