TCS -TR-A-07-33

TCS Technical Report

An Efficient Decision Diagram Structure
for Design Verification of Quantum Circuits
under a Practical Restriction
byShigeru Yamashita, Shin-ichi Minato, and
D. Michael Miller

Division of Computer Science
Report Series A
December 30, 2007

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

An Efficient Decision Diagram Structure
for Design Verification of Quantum Circuits under a Practical Restriction
S HIGERU YAMASHITAS HIN - ICHI M INATO

D. M ICHAEL M ILLER

Graduate School of Information Science
Nara Institute of Science and Technology
Ikoma, Nara 630-0192, Japan.

Division of Computer Science
Hokkaido University
Sapporo 060-0814, Japan

Faculty of Engineering
University of Victoria
Victoria, BC, V8W 3P6, Canada

December 30, 2007

(hence, practical) size problems since they need to express matrices explicitly and thus they need exponential
time and memory. (Note that a matrix for an n-bit quantum circuit is 2n × 2n , which will be explained later.)(Abstract) Recently much attentions have been paid toquantum circuit design to prepare for the future “quantum computation era.” Like the conventional logic synthesis, it should be important to verify and analyze thefunctionalities of generated quantum circuits. Therefore, we propose an efficient verification method forquantum circuits under a practical restriction. Thanks
to the restriction, we can introduce an efficient verification scheme based on decision diagrams called Decision Diagrams for Matrix Functions (DDMFs). Then,
we show analytically what are the advantages of ourapproach based on DDMFs over the previous techniques. In order to introduce DDMFs, we also introduce new concepts, quantum functions and matrix functions, which may also be interesting and useful on theirown for designing quantum circuits.

1

There is a different approach for quantum circuit design [6, 12, 7, 1, 8, 5]. The approach is to focus on
quantum circuits calculating only (classical) Booleanfunctions by the following observation [6]: A quantum
circuit for a standard quantum algorithm essentially differs in the part of the circuit that calculates (classical)
Boolean functions depending on the specification of agiven problem instance (e.g., so called oracles in thecase of Grover Search). Thus, we focus on designinga Boolean function in the model of quantum computation. Then, we may borrow many ideas from (classical) logic synthesis, especially reversible logic synthesis, and indeed there have been many researches
in the conventional logic synthesis research community [6, 12, 7, 1, 8, 5]. Thus, to focus on such quantum
circuits for Boolean functions, we may have a design
method to handle practical size problems. This paper
considers this type of quantum circuits.

Introduction

Recently quantum computing has attracted great attention by its potential abilities [11]. To realize a quantum algorithm, it is necessary to design the corresponding quantum circuit as small as possible. Thus, it
should be very important to study quantum circuit design methods even before quantum computing is physically realized. Indeed, there have been many researches [6, 12, 7, 1, 8, 5, 13, 10] for quantum circuitdesign.

Recently a paper [16] discussed an problem of theequivalence check of general quantum circuits andquantum states with considering so-called phase equivalence property of quantum states. Even for quantum
circuits calculating only Boolean functions, it should bevery important to verify and analyze the functionalitiesof designed circuits as the case of classical logic synthesis. For example, we may consider the following situation: One of the possible realizations of quantum computation is considered to be so called a linear-nearestneighbor (LNN) architecture in which the quantum bits

Typical quantum circuit design methods are basedon matrix decomposition [13, 10] since a quantum algorithm is expressed by a matrix. They can treat any
kind of quantum circuits, but they cannot treat large
12

Shigeru Yamashita, Shin-ichi Minato, and D. Michael Miller(qubits) are arranged on a line, and only operations toneighboring qubits are allowed. Thus, we need to modify a designed quantum circuit so that it uses only gatesthat operate to two adjacent qubits. In such a case, we
may use some tricky transformations, and it is very convenient if we have a verification tool to confirm that theoriginal and the modified quantum circuits are functionally equivalent.
If we consider only the classical type gates, it isenough to use the conventional technique such as Binary Decision Diagrams (BDDs) [2] for the verification. However, even if we consider quantum circuits
calculating only Boolean functions, it is known that
non-classical (quantum specific) gates are useful to reduce the circuit size [1, 8, 5, 4]. Thus we need to verify quantum circuits with non-classical gates. In suchcases, a classical technique is not obviously enough.
As for simulating quantum circuits, there havebeen proposed efficient techniques using decision diagrams (called Quantum Information Decision Diagrams (QuIDDs) [15] and Quantum Multiple-valued
Decision Diagrams (QMDDs) [9]) to represent matrices for quantum circuits. By using these efficient diagrams, we can express the functionalities of two quantum circuits, and then verify the equivalence of the twocircuits. However, they are originally proposed to simulate general quantum circuits, and thus there may be
a more efficient method that is suitable for verifying
the functionalities of quantum circuits only for Booleanfunctions.
Our contribution described in this paper. Considering the above discussion, we introduce a newquantum circuit class: Semi-Classical Quantum Circuits (SCQCs). Although SCQCs have a restriction,
the class of SCQCs covers all the useful quantum circuits (for calculating Boolean functions) as will be
explained later. Moreover, because of the restrictionof SCQCs, we can express the functionalities of SCQCs very efficiently as the conventional techniques by
BDDs. For that purpose, we introduce a new decision
diagram structure called a Decision Diagram for a Matrix Function (DDMF). Then, we show that the verification method based on DDMFs are much more efficient than the above mentioned methods based on previously known techniques. We provide an analyticalcomparison between DDMFs and QuIDDs, and reveal
the essential difference: (1) We show that their abil-

ity to express the functionality of one quantum gate
is essentially the same, but (2) we also show that ourapproach is much more efficient for the verificationof SCQCs than a method based on known techniques.
(Note that this does not mean that DDMFs are better
than QuIDDs: DDMFs are only for SCQCs, whereas
QuIDDs can treat all kinds of quantum circuits.) Moreover, we show by preliminary experiments that DDMFs
can be used to verify SCQCs of practical size (60 inputs
and 400 gates). In order to introduce DDMFs, we also
introduce new concepts, quantum functions and matrix
functions, which may be interesting and useful on theirown for designing quantum circuits with quantum specific gates.

2

Semi-Classical Quantum Circuits
and Their Representations by Decision Diagrams

This section introduces new concepts: SCQCs together
with quantum functions, matrix functions and DDMFs.

2.1 Quantum States and Quantum Gates
Before introducing our new concepts, let us briefly explain the basics of quantum computation.
In quantum computation, it is assumed that we canuse a qubit which is an abstract model of a quantum
state. A qubit can be described as α |0 + β |1, where|0 and |1 are two basic states, and α and β are complex numbers such that |α|2 + |β|2 = 1. It is convenient to use the following vectors to denote  |0 and
10and, |1 =. Thus,|1, respectively: |0 =01
α |0 + 
β |1
 can be described as a vector: α |0 +α. Accordingly, any quantum operation on
β |1 =
βa qubit can be described as a 2x2 matrix. By the lawsof quantum mechanics, the matrix must be unitary. We
call such a quantum operation a quantum gate. For example, the operation which transforms |0 and |1 to|1 and |0, respectively, is called a N OT gate whose
matrix representation is as shown in Fig. 1.
In addition to the above N OT gates, we can also
use any quantum specific unitary matrix in quantum circuits. For example, rotation gates denoted by R(θ) are3

An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction

often used in quantum computation. The matrix for thegates is as shown in Fig. 1. Although the functionality of rotation gates is not classical, they are useful todesign quantum circuits for (classical) Boolean functions [1]. Another quantum specific gate called a V gateis also utilized to design quantum circuits for Booleanfunctions [8, 5]. The matrix for the gate is as shownin Fig. 1. This gate has the interesting property thatV 2 = N OT .
In the following, our primitive gates are (generalized) controlled-U gates which are defined as follows:

Definition 1 A controlled-U gate has (possibly many)
positive and negative control bits, and one target bit.
It applies a 2×2 unitary matrix U to the target qubit
when the states of all the positive control bits are thestates |1 and the states of all the negative control bits
are the state |0. A controlled-U gate may not have acontrol bit. In such a case, it always applies U to thetarget qubit.
See an example of a quantum circuit consisting of
two controlled-NOT gates in Fig. 2. In quantum circuits, each gate works one by one from the left to theright. For the first gate, the target bit is x3 and the symbol ⊕ means the N OT operation. The positive control bits are x1 and x2 denoted by black circles. Thisgate performs N OT on |x3  only when both |x1  and|x2  are the state |1. Consider the second gate in thesame figure. The white circles denote negative controls,
which means the gate performs N OT only when both|x1  and |x2  are the states |0.
In addition to controlled-NOT gates which are essentially classical gates, we can consider any (quantum
specific) unitary operation for controlled gates. For example, the functionalities of controlled gates in Figs. 3
and 4 are various (e.g., NOT, V , V −1 , R( 12 π) andR( 14 π)).

2.2

Semi-Classical Quantum Circuit (SCQC)

Consider Fig. 2 again. This circuit transforms thestate of the third bit |x3  into |x3 ⊕ f (x1 , x2 ), wheref (x1 , x2 ) = x1 · x2 + x1 · x2 . Thus, we can use thiscircuit (as a part of a quantum algorithm) to calculates
the Boolean function f (x1 , x2 ) = x1 · x2 + x1 · x2 .

⎛0
NOT = ⎜⎜
⎝1

1⎞
⎟
0 ⎟⎠

⎛1+ i
⎜
V =⎜ 2⎜⎜ 1 − i⎝ 2⎛ cos( θ / 2 )R (θ ) = ⎜⎜⎝ − i sin( θ / 2 )1− i ⎞⎟
2 ⎟1+ i ⎟⎟
2 ⎠− i sin( θ / 2 ) ⎞cos( θ / 2 ) ⎠Figure 1: Unitary matrices

|x1〉
|x2〉
|x3〉
first gatesecond gate

Figure 2: A quantum circuit

As mentioned before, although our goal is to construct
such a quantum circuit that calculates a Boolean function, quantum specific gates (such as R(θ) and V ) areuseful [1, 8, 5, 4] to make the circuit size smaller. For
example, the circuit as shown in Fig. 3 (reported in [5])utilizes controlled-V and controlled-V −1 gates to become much smaller than the one we can do the bestwith only classical type gates, i.e., controlled-NOT
gates. (That was confirmed by an essentially exhaustive search [5].)In order to characterize such a quantum circuitthat calculates a classical Boolean function with nonclassical gates, we introduce a Semi-Classical Quantum
Circuit (SCQC) whose definition is as follows.
Definition 2 A Semi-Classical Quantum Circuit(SCQC) is a quantum circuit consisting of controlled-U

|x1〉
|x2〉
|x3〉 V − 1VV

Figure 3: A quantum circuit for half-adder4

Shigeru Yamashita, Shin-ichi Minato, and D. Michael Miller

|x1〉
|x2〉
|x3〉 V − 1

V
⎛π ⎞
R⎜ ⎟
⎝2⎠

⎛π ⎞
R⎜ ⎟
⎝4⎠

Figure 4: A non-SCQC

gates with the following restriction.
Restriction. If all the initial input quantum states of
the circuit are |1 or |0 (i.e., just classical values), thequantum states of the control qubits of any gate in thecircuit should be |1 or |0 at the time when the gate is
being operated.
The circuit in Fig. 3 is an SCQC. This is because
the quantum states of the control qubits of any gate are
either |1 or |0 when the gate is being operated if theinitial input state |x1 , |x2  and |x3  are either |1 or|0. It is not trivial to see the condition for the quantum
state of the control qubit of the last gate (|x3 ) in Fig. 3.
However, by using our new concepts (explained in thenext section), it is easy to verify that the state is indeed
the classical value if the input states of the circuit areclassical values.
On the contrary, the circuit as shown in Fig. 4 is
not an SCQC. Again, by using our new concept it iseasily verified that the condition is not satisfied for thequantum state of the control qubit of the last gate (|x3 )
in Fig. 4.
Our motivation to introduce SCQCs is based on thefollowing observations.
• Although SCQCs are in a subset of all the possible
quantum circuits, quantum circuits (for calculating a Boolean function) designed by the existing
methods are all SCQCs to the best of our knowledge.
• Even in the future it is very unlikely that we comeup with a tricky design method that produces a
non-SCQC to calculate (classical) Boolean functions. The reason is as follows. If the circuit is
not a SCQC, there is a gate such that the quantum
state of its control bit is not a simple classical value(|0 nor |1). In such a case, the quantum statesof the control bit and the target bit after the gatecannot be considered separately: their states are
not only non-classical values but also correlatedwith each other. Such a situation is called quantum
superposition and entanglement [11]. Since thewhole circuit should calculate a Boolean function,
all of the final output quantum states should beagain restored to simple classical values (i.e., |0
or |1). The reverse operations of creating quantum superposition and entanglement seems to be
only one method to restore to a simple classicalvalue. Thus, it seems nonsense to consider nonSCQC circuit when we discuss practical design
method of a quantum circuit to calculate a Booleanfunction.
Important Note: The restriction of SCQCs meansthat we cannot make entanglement if all the initial input
quantum states of a SCQC are just classical values. It is
well-known that quantum computation without entanglement has no advantage over classical computation.
However, this does not mean that SCQCs are meaningless by the following reason: As mentioned, a SCQC
is used as a sub-circuit to calculate a Boolean function
for some quantum algorithms. Thus, in the real situation where a SCQC is used as a sub-circuit, the inputs
to the SCQC are not simple classical values,and so it indeed creates entanglement which should give us a quantum computation advantage. In other words, the restriction of SCQCs in the definition is considered when we
suppose the inputs of SCQCs are just classical values,
which may not be a real situation where SCQCs are really used.
Therefore, SCQCs should be enough if we consider
to design a quantum circuit to calculate a Boolean function from the practical point of view. Moreover, the restriction of SCQCs provide us an efficient method toanalyze and verify quantum circuit as we will see inSec. 3. That is our motivation to introduce the new concept in this paper.

2.3 Quantum Functions and Matrix Functions
Before introducing our new representation of the functionalities of SCQCs, we need the following definitions.

5

An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction

Table 1: A truth tables for quantum, classical and matrix functions
x1 , x2
0, 0
0, 1
1, 0
1, 1

qf1
|0
V −1 |0|0
V −1 |0

qf2
|1
|0
|0
|1

mf1
I
V −1
I
V −1

mf2
N OT
I
I
N OT

CM (I)I
I
I
I

CM (R( 12 π))R( 12 π)R( 12 π)R( 12 π)R( 12 π)Definition 3 A quantum function with respect to n
Boolean variables x1 , x2 , · · · , xn is a mapping from{0, 1}n to a qubit state.
See the third bit after the first gate in the circuit inFig. 3 again. If the initial state of |x3  is |0, the resultant state of the third bit can be seen as a quantum
function described as qf1 (x1 , x2 ) in the second columnof Table 1. For example, the resultant quantum state becomes V −1 |0 when x1 = 0, x2 = 1. Thus, qf1 (0, 1)
is defined as V −1 |0 as shown in the table.
Note that a Boolean function can be seen as a special case of quantum functions. For example, the thirdcolumn (qf2 ) of Table 1 shows the quantum function of
the resultant third qubit after the two gates of the circuitin Fig. 2 when the initial state of |x3  is |0. This canbe considered as the output of a Boolean function when|0 and |1 are considered as Boolean values 0 and 1, respectively. (As mentioned before, the circuit is considered to calculate the Boolean function: x1 · x2 + x1 · x2 ,which we consider essentially the same as (qf2 ) in Table 1.)
The value of a quantum function q(x1 , x2 , · · · , xn )can always be expressed as mf (x1 , x2 , · · · , xn ) |0,
where mf (x1 , x2 , · · · , xn ) is a mapping from {0, 1}nto 2 × 2 unitary matrices. It is convenient to consider mf (x1 , x2 , · · · , xn ) instead of q(x1 , x2 , · · · , xn )itself, thus we introduce the following definition.
Definition 4 A matrix function with respect to n
Boolean variables x1 , x2 , · · · , xn is a mapping from{0, 1}n to a 2 × 2 (unitary) matrix.
The fourth and the fifth columns of Table 1 show thematrix function mf1 and mf2 for the quantum function
qf1 and qf2 , respectively, in the same table. In this paper, we treat a matrix function whose output values are
only I or N OT as a classical Boolean function by considering that N OT and I of the matrix function correspond to 1 and 0, respectively, of the Boolean function.

Table 2: Operators ⊕ and ∗.
x1 , x2
0, 0
0, 1
1, 0
1, 1

mf1
R( 12 π)I
I
R( 12 π)mf2
R( 12 π)I
R( 14 π)R( 14 π)mf1 ⊕ mf2
R(π)
I
R( 14 π)R( 34 π)mf3
R( 12 π)
I
R(π)
R(π)

f
1
0
1
0

f ∗ mf3
R( 12 π)I
R(π)
I

In other words, we represent a Boolean function by amatrix function as a special case.
We define a special type of matrix function called
constant matrix function as follows.
Definition 5 A matrix function mf (x1 , x2 , · · · , xn )is called a constant matrix function if
mf (x1 , x2 , · · · , xn ) are the same for all the assignments to x1 , x2 , · · · , xn . CM (M ) denotes aconstant matrix function that always equals to thematrix M .
The sixth and the seventh columns of Table 1 show thetruth tables for constant matrix functions, CM (I) andCM (R( 12 π)), respectively.
By using the matrix function mf1 in the fourth column of Table 1, we can easily see how the first gate in
Fig. 3 transforms the third qubit |w: |w is transformed
to mf1 (x1 , x2 ) |w. For example, when x1 = 0, x2 =1, |w is transformed to V −1 |w.
Important Note: The above means that the representation (and so the analysis) by matrix functions
works even when |w is any general quantum state. Indeed, we can use a SCQC even when the input states
are not simple classical values, i.e., the restriction of
SCQCs does not say that SCQCs cannot be used when
the inputs are not classical. (If so, we may not be able
to use an SCQC for a part of a quantum algorithm.)
For matrix functions, we introduce two operators“⊕” and ‘∗,” which are used to construct DDMFs fora quantum circuit in the following sections.
Definition 6 Let mf1 , mf2 and mf3 be maThen
trix functions with respect to x1 to xn .
mf1 ⊕ mf2 is defined as a matrix function mf
such that mf (x1 , · · · , xn ) = mf1 (x1 , · · · , xn ) ·mf2 (x1 , · · · , xn ) where · means normal matrix
multiplication. Let also f be a Boolean function

6

Shigeru Yamashita, Shin-ichi Minato, and D. Michael Miller

with respect to x1 to xn . Then f ∗ mf3 is a matrix function which equals to mf3 (x1 , x2 , · · · , xn )when f (x1 , x2 , · · · , xn ) = 1, and equals to I whenf (x1 , x2 , · · · , xn ) = 0.

M
xi

See examples in Table 2. Note that if mf1 and mf2 areconsidered to be Boolean functions like mf2 in Table 1,
the operator ⊕ corresponds to the EXOR of the two
Boolean functions. Note also that if mf3 is essentiallya Boolean function like mf2 in Table 1, the operator ∗corresponds to the AND of the two Boolean functions.

2.4

Definition 7 A Decision Diagram for a Matrix Function (DDMF) is a directed acyclic graph with three
types of nodes: (1) A single terminal node corresponding to the identity matrix I, (2) a root node with anincoming edge having a weighted matrix M , and (3) aset of non-terminal (internal) nodes.
Each internal and the root node are associated witha Boolean variable xi , and have two outgoing edges
which are called 1-edge (solid line) leading to anothernode (the 1-child node) and 0-edge (dashed line) leading to another node (the 0-child node). Every edge has
an associated matrix.
The matrix function represented by a node is definedrecursively by the following three rules.
(1) The matrix function represented by the terminal
node is the constant matrix function CM (I).
(2) The matrix function represented by an internal
node (or the root node) whose associated variable is xi
is defined as follows: xi ∗ (CM (M1 ) ⊕ mf1 ) ⊕ xi ∗(CM (M0 ) ⊕ mf0 ), where mf1 and mf0 are the matrix functions represented by the 1-child node and the
0-child node, respectively, and M1 and M0 are the matrices of the 1-edge and the 0-edge, respectively. (Seean illustration of this structure in Fig. 5.)(3) The root node has one incoming edge that has amatrix M . Then the matrix function represented by thewhole DDMF is CM (M ) ⊕ mf , where mf is a matrix
function represented by the root node.

M0

mf1
xi+1

xi+1

mf0

Figure 5: An internal DDMF nodeDecision Diagrams for Matrix Functions

A matrix function for a quantum function can be expressed efficiently by using an edge-valued binary decision diagram structure, which we call a DDMF whose
definition is as follows:

M1

M

x1

x2
M 1 M0
x3

1

I

MM 0
−1
0

M 1M
x3
1

x1

x2

I

Figure 6: Conversion to the canonical form

Like conventional BDDs, we achieve the canonicalform for a DDMF if we impose the following restriction
on the matrices on all the edges.
Definition 8 A (DDMF) is canonical when (1) all thematrices on 0-edges are I, (2) there are no redundantnodes: No node has 0-edge and 1-edge pointing to thesame node with I as the 1-edge matrix, and (3) common
sub-graphs are shared: There are no two sub-graphs.
Any DDMF can be converted to its canonical form byusing the following transformation from the terminal
node to the root node: Suppose the matrices on incoming edge, 0-edge and 1-edge of a node be M , M0 and
M1 , respectively. Then, if M0 is not I, we modify thesethree matrixes as follows: (1) The matrix on the incoming edge changed to be M M0 . (2) The matrix on the
1-edge changed to be M1 M0−1 . (3) The matrix on the0-edge changed to be I. It is easily verified that thistransformation does not change the matrix function represented by the DDMF. See the example in Fig. 6 where
the matrix on 0-edge of the node x2 is converted to I.
In the example, the matrices I on edges are omitted.

An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction|x1〉|x2〉 V|x3〉

Step 1. We construct a DDMF to represent the matrix
function that expresses the functionality for each qubit
state at the end of each circuit.

Figure 7: An SCQC (1)

|x1〉
|x2〉
|x3〉

V

Figure 8: An SCQC (2)Note: The concepts of quantum functions and matrix functions may be used implicitly in the design
method of [1], and the decision diagram structure issimilar between DDMFs and the quantum decision diagrams used in [1]. However, the quantum decision diagrams in [1] are used to represent conventional Booleanfunctions whereas DDMFs are used for representing
matrix functions: the terminal node of a DDMF is amatrix I. Also a weight on an edge in DDMFs is generalized to any matrix. Thus, DDMFs can be considered as a generalization of quantum decision diagrams
to treat matrix functions rather than Boolean functions.
(As we have seen in Table 1, Boolean functions can beseen as a special case of quantum functions.)
We will use the same operators, ⊕ and ∗, for
DDMFs as for matrix functions: (1) (DDMF for mf )= (DDMF for mf1 ) ⊕ (DDMF for mf2 ) if mf =mf1 ⊕ mf2 , and (2) (DDMF for mf ) = (DDMF formf1 ) ∗ (DDMF for mf2 ) if mf = mf1 ∗ mf2 .

3

7

Verification of SCQCs by using
DDMFs

See two SCQCs in Fig. 7 and Fig. 8. It is easy to see that
their functionality are the same. However, the problem
is how to verify the equality for much larger circuits.
Thanks to the introduction of DDMFs, we propose amethod to verify the equality of given two n-qubit SCQCs in the following.

Step 2. We compare two DDMFs for the corresponding qubits of the two circuits. The comparison of two
DDMFs can be done in O(1) time as in the case of
BDDs.
Step. 1 is performed as follows. In the below, we
use a notation Dij to express the DDMF for the i-th
quantum qubit state right after the j-th gate. We also
use a notation F (D) to denote the matrix function (orthe Boolean function in a special case) represented by
a DDMF D.
Initialization. For each input xi , we construct a Di0
as a DDMF for xi . This is the DDMF for the matrix
function (essentially Boolean function) which is N OT
when xi = 1.
Construction of the DDMFs right after the j-th gate.
From the first gate to the last gate, we construct Dij
from Dij−1 as follows. If the i-th bit is not the target bitof the j-th gate, Dij = Dij−1 . If the i-th bit is the target
bit of the j-th gate Dij = Dij−1 ⊕ Dgate where Dgate isconstructed by the following two steps.
(1) For the j-th gate, let us suppose that the positive control bits be the p1 , p2 , · · · , pk -th bits, andthe negative control bits be the n1 , n2 , · · · , nl -th bits.
Then, by the restriction of SCQCs, all the matrix funcj−1 ) for m = p , p , · · · , p , n , n , · · · , ntions F (Dm
1 2
1 2
k
l
are classical Boolean functions. Thus we can cal) ·culate a logical AND of them: g = F (Dpj−1
1
j−1
j−1
) · · · F (Dpj−1) · F (Dnj−1
F (Dpj−1
1 ) · F (Dn2 ) · · · F (Dnl ).
2kNote that this Boolean function can be obtained by
DDMF operations since a DDMF represents a Booleanfunction in a special case.
(2) We construct Dgate = (DDMF for g)∗(DDMF for CM (U )), where U is a unitary matrix
associated with the j-th gate.
Note that all the DDMF operations in the above
should be performed efficiently by using Apply operations and operation and node hash tables as the conventional BDD operations [2].
We show an example of DDMFs for the quantum
circuit as shown in Fig. 7. At the initialization step, weconstruct DDMFs for functions, x1 , x2 and x3 , which
are D10 , D20 and D30 as shown in Fig. 9. Then we8Shigeru Yamashita, Shin-ichi Minato, and D. Michael Miller

Table 3: A truth table for Dcontrol
x1 , x2 , x3 F (Dcontrol )0, 0, 0I0, 0, 1V
0, 1, 0I
0, 1, 1V
1, 0, 0I
1, 0, 1I
1, 1, 0I
1, 1, 1
I

x2

x1
1

x3

1

I

1

I

DDMF

0
1

I

DDMF

DDMF 30

02Figure 9: DDMFs after the initialization

x1
Table 4: A truth table for D21
x1 , x2 , x3 F (D21 )0, 0, 00, 0, 10, 1, 00, 1, 1
1, 0, 01, 0, 1
1, 1, 01, 1, 1

x2

I
V
N
VN
I
I
N
NN

x1

x2
1

1

V

1

x3

x3
1

I

I

I

DDMF 10

DDMF 02

DDMF 30

Figure 10: DDMFs after a gate
construct the DDMFs for the quantum states right after the first gate. Since the target bit is the second
bit for the first gate, D11 = D10 , and D31 = D30 . To
construct D21 , we first calculate a Boolean function
g = F (D10 ) · D30 = x1 · x3 . Note that this Booleanfunction can be obtained by DDMF operations since a
DDMF represents a Boolean function as a special case.
This is because the first bit and the third bit are negative and positive control, respectively. Then we construct Dgate = g ∗ (DDMF for CM (V )), whose matrix function is shown in Table 3. Finally, we construct
D21 = D20 ⊕ Dgate whose matrix function is as shownin Table 4. The constructed DDMFs after the first gate
are shown in Fig. 10.

4Comparison
methodswiththepreviousIn this section we compare our method with the previous methods to show the advantage of our method.

4.1 Verification method based on previous
techniques
A gate (or a circuit) of n qubits can be described by a
2n × 2n unitary matrix. For example, the unitary matrix
that expresses the functionality of the last gate in Fig. 4
can be shown as in Fig. 11. (We will explain this briefly
in Appendix.)
Since the same structure (sub-matrices) are often repeated in such a 2n × 2n unitary matrices (like Fig. 11),
there have been proposed data compression scheme
based on decision diagram structures: QuIDDs [15]based on multi-terminal binary decision diagrams, and
QMDDs [9] based on multiple-valued decision diagrams (MTBDDs) [3]. Here we explain how thedata compression works for QuIDDs. QMDDs havea slightly different approach: They use multi-valued
logic instead of binary logic, and the strategy of selecting decision variables is a bit different. However,it should be noted that the two approaches are essentially the same when (1) the target circuit is binary logic

9

An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction

R 0 R1 R 2
0 0 0 ⎛1⎜
0 0 1 ⎜0⎜0 1 0 ⎜0

⎜0
⎜
⎜0
⎜
⎜0
⎜0
⎜⎜
1 1 1 ⎝0

0 11
1 0 0
1 0 1
11 0

0
1+ i
2
0
1− i
2
0
0
0
0

0

0
0

0
1− i
2
0
1+ i
2
0
0

0
0

0
0

0
1
0

0

0

0

0

0

0

0⎞
⎟
0⎟

0

0

0

0

0

0

0

1
0

0
1

0
0

0
0

0
0

1
0

0⎟
⎟
0⎟
⎟
0⎟
0⎟
⎟
1 ⎟⎠

000 001 010 011 100 101 110 111
C 0 C 1C 2

R0
C0

C0

R1

R1

C1 C1

C1 C1

R2

R2

R2

C2 C 2C2 C 2

C2

1+ i
2

1− i
2

Figure 11: A Unitary Matrix for a 3-qubit gate(|0 or |1) valued (which is our case), and (2) the variable ordering is appropriately chosen for QuIDDs (asexplained below).
A QuIDD for the matrix in Fig. 11 can be constructed as shown in Fig. 12. In a QuIDD representing
a matrix, we have decision variables to specify rows
(R0 , R1 , R2 ) and columns (C0 , C1 , C2 ) of the matrix asshown in Fig. 11. For example, the variable assignment
to R0 = 0, R1 = 1, R2 = 1, C0 = 0, C1 = 0, C2 = 1)
leads to the forth row and the second column element,
1−i
2 . We can construct a binary decision diagram where
each variable assignment corresponds to one elementof the matrix as shown in Fig. 12. If there are some repeated structures in a matrix, this diagram can reduce
the necessary memory space to store the matrix information.
It is known that interleaving the row and the column
variables (i.e., the order of R0 , C0 , R1 , C1 , · · · ) would
be a good variable order [14]. In such a case, the variable order becomes the same as the case of QMDDs. In
this paper, we also consider such a variable order.
As the conventional decision diagrams, we can implement any operations (such as addition and multiplication) between two QuIDDs based on Apply operations and operation and node hash tables. Usually,
QuIDDs can reduce the necessary memory, and thenecessary computational time for matrix operations forquantum circuit simulations [15].

10Figure 12: A QuIDD (1)4.2 Advantages of the Proposed Approach
First we compare the number of nodes to represent
the functionality of a single gate between DDMFs and
QuIDDs. Let us use the last gate in Fig. 4 for our explanation. As explained before, the QuIDD shown in
Fig. 12 represents the matrix corresponding to the gate.
A DDMF for the same purpose can be shown as inFig. 13. In the DDMF, V is attached on the path corresponding to the variable assignment x1 = 0, x3 = 1.
This is because the gate applies V only when x1 =

x1

x3
V

I
Figure 13: A DDMF

10

Shigeru Yamashita, Shin-ichi Minato, and D. Michael Miller

G1
C0

G2

which is not on the bottom (e.g., G1 , G2 , G3 in Fig. 14),the two paths corresponding to (Ri = 1, Ci = 0) and(Ri = 0, Ci = 1) always go to 0 terminal node. (This isbecause the matrix is a diagonal matrix, and thus the elements in the right upper and the left lower parts of thematrix are all 0.) Thus, we can essentially omit suchpaths, and then only two paths are essentially necessary
for the group of nodes, which means that we can replaceeach group of nodes by one node. (Of course, to do so,
we need more operations than the standard QuIDD operations.)

R0
C0

R2

R2

C2 C 2

C2 C2

R1

R1

C1 C1

C1 C1

G3

G5

G4
1

0

1+ i
2

1− i
2

Figure 14: A QuIDD (2)0, x3 = 1.
From the two figures, DDMFs seem to be better
than QuIDDs. However, this is a bit unfair comparison because the DDMF implicitly utilizes the fact thatx2 is the target bit. (Thus, x2 does not appear in the
DDMF.) On the other hand, the QuIDD does not use
such knowledge. Although the explanation is omitted
due to the space limitation (again see the details in astandard text), (R1 , C1 ) corresponds to the input (andthe output) line on x2 in the original quantum circuit.
Thus, if we know that x2 is the target bit, we can alsochoose the appropriate variable order for the QuIDD
such that the pairs of variables (R1 , C1 ) are put on thebottom. Then, the QuIDD becomes smaller as shownin Fig. 14.
Although there still seems to be a big difference between two diagrams in Figs. 13 and 14, the essential
difference is only a constant factor since we can decrease the number of nodes of the QuIDD in Fig. 14 if
we consider the following two issues.
(1) If we choose the appropriate variable orderingof (Ri , Ci ) as described above, the corresponding matrix can be considered as one such that there are only
2x2 matrices on the diagonal. (Again we omit the explanation.) Thus, for each group of nodes, (Ri , Ci ),(2) If we note that the terminal nodes of a DDMF
are 2x2 matrices (which has 4 elements), the last groupof nodes (G4 and G5 in Fig. 14) should not be counted
for the fair comparison.
To sum up, in this example, G2 , G4 and G5 should
not be counted since each group leads to only the elements of a single 2x2 matrix (I or V ), and G1 andG3 should be considered as one node; thus there is no
essential difference between two diagrams. Of course,
it is apparent that DDMFs are much more straight forward and easy to implement (hence should be faster)than QuIDD based approaches for our purpose. However, the above discussion makes it clear that there is
only a constant factor difference.
Nevertheless, there is a good reason for us to introduce DDMFs: If we consider the verification of the twoquantum circuits, the difference may become exponential in some cases, which will be explained below.
As mentioned in Sec. 3, when we construct Dij fromthe previous step, we always implicitly choose the appropriate variable order: We implicitly put the target
bit (the i-th bit) on the bottom (more precisely, we ignore the target bit) when we calculate Dij . On the other
hand, we cannot choose an appropriate variable ordering for the QuIDD approach since the verification by
QuIDDs are performed as follows: We can verify theequality of the two quantum circuits by comparing thetwo QuIDDs representing the two quantum circuits. To
construct the QuIDD for a circuit, we simply multiply matrices corresponding to gates in the circuit fromthe left to the right. This can be done by representing
each matrix into a QuIDD. For the first gate, we canchose the appropriate variable order. However, if thetarget bits are different between the first and the second gates, we cannot choose the appropriate variable
ordering when we construct the QuIDD for the second

An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction

gate. This is because the same variable order should beapplied for the two QuIDDs when we perform the multiplication. Thus, at least one of QuIDDs may becomemuch larger compared to the DDMF approach. Anotherimportant observation is that the resultant QuIDD after
the multiplication may be larger than the corresponding
DDMF approach by the following reason. We constructeach DDMF for each qubit, and thus we can implicitly
choose the best variable order (i.e., putting the target bit
to the bottom) for each qubit. This can be done becauseof the restriction of SCQCs. On the other hand, unitarymatrix based approaches (such as QuIDD and QMDD
based verifications) do not assume such a restriction,and thus they do not treat each qubit separately, andthus they represent the functionalities for all qubits atthe same time as one unitary matrix corresponding to apart of quantum circuit. Therefore, we cannot choose
the best variable if the appropriate variable order differs for different qubits. (This occurs when we multiply
several matrices corresponding to quantum gates withdifferent target bits.) Thus, in the worst case, QuIDDs
becomes much bigger than DDMFs during the verification procedures. It is obvious that the necessary memory and the necessary time for Apply operations becomeless if the number of nodes is few. Thus it is apparent
our approach is much more efficient than previous approaches for the purpose of the verification of SCQCs.
It should be noted that there is also an apparent advantage of DDMFs in terms of operation and node hashtables as follows. The variables for DDMFs during theverification is always the inputs of the circuits (i.e., x1
to xn ). In other words, we always represent matrix
functions with respect to the inputs of the circuits. Thus
we are always working on the the input variables of thecircuits. On the other hands, the variables for QuIDDs
differs depending on the gates. More precisely, a unitary matrix corresponding to a gate (or a part of the circuit) represents a relation between the inputs of the gate
(or the part of the circuit) and the outputs of that. Thatis, the variables for QuIDD are always local: The meaning of variables Ri and Ci for a QuIDD changes during
the matrix multiplication. (Even though we work on
the same variables Ri and Ci , the logical meaning of
the variables changes depending on the corresponding
quantum gates.) This apparently makes it difficult toshare the previously computed results in the hash tables. Thus, it is apparent that hash tables work much

11

Table 5: Experimental result
 variables  gates  nodes time (sec.)
30
100
418
0.0050
30
200
2509
0.035
30
400
16681
16.23
60
100
1568
0.017
60
200
12984
10.7664
60
400
24681
99.58

better for DDMFs.
The above discussion reveals why our verification
method based on DDMFs should work more efficiently
than the previous approaches.
We have implemented a DDMF library by C++, andperformed a preliminary experiment. Unfortunately,
we did not have large SCQC benchmarks, and thus we
randomly generated SCQCs and constructed DDMFs
for the generated circuits. Then the average (of 10 trials) of the total number of used nodes and the CPU time
(on a Linux system running at 3.0 GHz with 256 MB
memory) for various settings (i.e., the numbers of inputs and the gates) are reported in Table 5. From the table, we can expect our verification method should workfor quantum circuits of practical size.

5

Conclusions and Future WorkIn this paper, we introduced new concepts: SCQCs together with DDMFs. As described, they should be useful for the analysis and the verification of quantum circuits with a practical restriction. It should be noted that
DDMFs are provably useful even for quantum circuitdesign methods since DDMFs can be considered as a
generalization of the data structure used in the design
method in [1].
We also revealed the essential difference between
DDMFs and QuIDDs for representing the functionalities of SCQCs. From our discussion, we can say that
our approach is much more efficient for the verificationof SCQCs than a method based on known techniques.
Note that this does not mean that DDMFs are better
than QuIDDs: DDMFs are only for SCQCs, whereas
QuIDDs can treat all kinds of quantum circuits. In other12

Shigeru Yamashita, Shin-ichi Minato, and D. Michael Miller

words, in some sense, our approach stands in the middle of classical Boolean function (BDDs) and generalquantum circuit specification (QuIDDs or QMDDs).
As described, this standpoint can be considered as agood trade-off point if we consider to design and analyze quantum circuits from the practical view point,i.e., when we focus on sub-circuits to calculate Booleanfunctions for quantum algorithms. Lastly we would
like to add one more issue: Since DDMFs are edgevalued decision diagrams, it should be much easier toverify quantum phase-equivalence checking of SCQCs
by DDMFs than the method based on QuIDDs [16]. Although we cannot discuss this point due to the space
limitation, such a comparison would also be interestingin future work.

[6] K. Iwama, Y. Kambayashi, and S. Yamashita.
Transformation Rules for Designing CNOT-based
Quantum Circuits. In Proceedings of the Design
Automation Conference, pages 419–424, June
2002.

In conclusion, we can expect the introduction of
SCQCs and DDMFs would promote researches towardpractical and efficient quantum circuit design methodology.

[9] D. M. Miller and M. A. Thornton. QMDD: A decision diagram structure for reversible and quantum circuits. In Proc. of the IEEE International
Symposium on Multiple-Valued Logic, page 30,
May 2006.

References[10] Mikko Möttönen, Juha J. Vartiainen, Villa
Bergholm, and Martti Salomaa. Quantum circuits for general multiqubit gates. Phys. Rev. Lett.,
93(13):130502, 2004.

[1] A. Abdollahi and M. Pedram. Analysis and synthesis of quantum circuits by using quantum decision diagrams. In Proc. of the Design, Automation
and Test in Europe (DATE’06), pages 317–322,
2006.
[2] R. E. Bryant. Graph-based algorithm for Booleanfunction manipulation. IEEE Transactions on
Computers, C-35(8):667–691, August 1986.
[3] E. M. Clarke, M. Fujita, and X. Zhao. Multiterminal binary decision diagrams and hybrid decision diagrams. In Sasao and Fujita, editors, Representations of Discrete Functions, pages 93–108.
Kluwer Academic Publishers, 1996.
[4] Steven A. Cuccaro, Thomas G. Draper, Samuel A.
Kutin, and David Petrie Moulton. A new quantum
ripple-carry addition circuit, 2004. Available online as http://arxiv.org/abs/quant-ph/0410184.
[5] W. N. N. Hung, X. Song, G. Yang, J. Yang, and
M. Perkowski. Quantum logic synthesis by symbolic reachability analysis. In Proceedings of the
Design Automation Conference, pages 838–841,
June 2004.

[7] D. Maslov, G. W. Dueck, and D. M. Miller. Toffoli
Network Synthesis with Templates. IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, 24(6):807–817, June 2005.
[8] D. Maslov, C. Young, M. Miller, and G. Dueck.
Quantum Circuit Simplification Using Templates.
In Proc. of the Design, Automation and Test in Europe (DATE’05), pages 1208–1213, 2005.

[11] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge
University Press, 2000.
[12] V. V. Shende, A. K. Prasad, I. L. Markov,
and J. P. Hayes.
Reversible logic circuit
synthesis. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems,
22(6):710–722, June 2003. Available online as
http://xxx.lanl.gov/abs/quant-ph/0207001.
[13] Vivek V. Shende, Igor L. Markov, and Stephen S.
Bullock.
Synthesis of quantum logic circuits. IEEE Trans. on Computer-Aided Design,25(6):1000–1010, 2006.
[14] G. F. Viamontes, I. L. Markov, and J. P.
Hayes. Improving gate-levelsimulation of quantum circuits. Quantum Information Processing,2(5):347–380, 2003.
[15] G. F. Viamontes, I. L. Markov, and J. P. Hayes.
Graph-based Simulation of Quantum Computation in the Density Matrix Representation. Jour-An Efficient Decision Diagram Structure for Design Verification of Quantum Circuits under a Practical Restriction

nal of Quantum Information and Computation,
5(2):113–130, February 2005.
[16] G. F. Viamontes, I. L. Markov, and J. P. Hayes.
Equivalence checking of quantum circuits andstates. In Proceedings of the International Conference on Computer Aided Design, pages 69–74,
2007.
*

A

A Unitary Matrix for a 3-input
Gate

As mentioned in Sec. 2.1, one qubit state can be described as a 2-dimensional vector. If we consider thequantum state of n qubits, the state can be described
as a 2n -dimensional vector. For example, if we consider three qubits, |x1  = α1 |0 + β1 |1, |x2  =α2 |0 + β2 |1 and |x3  = α3 |0 + β3 |1, at the sametime, the total states
as a 8(= 23 )⎛ can be described⎞
α1 α2 α3⎜α α β ⎟⎜ 1 2 3⎟⎜⎟⎜ α1 β2 α3 ⎟⎜⎟⎜ α1 β2 β3 ⎟⎜⎟ . For example, the first
dimensional vector ⎜⎟⎜ β1 α2 α3 ⎟⎜⎟⎜ β1 α2 β3 ⎟⎜⎟⎝ β1 β2 α3 ⎠β1 β2 β3element α1 α2 α3 and the second element α1 α2 β3 correspond to the basis state (|x1  |x2  |x3  =) |0 |0 |0
and |0 |0 |1, respectively. This vector can be obtained
from the tensor product of the three 2-dimensional vectors corresponding to |x1  , |x2  and |x3 . See more details in a standard text such as [11].
Thus, an operation to n qubits at the same time canbe described by a 2n × 2n unitary matrix. For example, the matrix in Fig. 11 shows the unitary matrix that
describes the operation by the last gate in Fig. 4. The
third and the forth rows (and columns) correspond to|0 |1 |0 and |0 |1 |1, respectively, and thus we cansee that this operation output the state ( 1+i
2 |0 |1 |0 +1−i
2 |0 |1 |1) if the input state is (|0 |1 |0). This
corresponds to the fact that the controlled-V gate applies V to |x3  (i.e., |x3  = |0 is changed to V |0 =
1−i
( 1+i
2 |0 + 2 |1)) when |x1  |x2  = |0 |1.

13