SANDIA REPORT

SAND2006-3440
Unlimited Release
Printed July 2006

Quantum Gate Decomposition

Algorithms
Alexander Slepoy

Prepared by
Sandia National Laboratories
Albuquerque, New Mexico 87185 and Livermore, California 94550

Sandia is a multiprogram laboratory operated by Sandia Corporation,

a Lockheed Martin Company, for the United States Department of Energy’s
National Nuclear Security Administration under Contract DE-AC04-94AL85000.

Approved for public release; further dissemination unlimited.

Issued by Sandia National Laboratories, operated for the United States Department of Energy
by Sandia Corporation.

NOTICE: This report was prepared as an account of work sponsored by an agency of the
United States Government. Neither the United States Government, nor any agency thereof,
nor any of their employees, nor any of their contractors, subcontractors, or their employees,
make any warranty, express or implied, or assume any legal liability or responsibility for the
accuracy, completeness, or usefulness of any information, apparatus, product, or process
disclosed, or represent that its use would not infringe privately owned rights. Reference herein
to any specific commercial product, process, or service by trade name, trademark,
manufacturer, or otherwise, does not necessarily constitute or imply its endorsement,
recommendation, or favoring by the United States Government, any agency thereof, or any of
their contractors or subcontractors. The views and opinions expressed herein do not
necessarily state or reflect those of the United States Government, any agency thereof, or any
of their contractors.

Printed in the United States of America. This report has been reproduced directly from the best
available copy.

Available to DOE and DOE contractors from

U.S. Department of Energy
Office of Scientific and Technical Information
P.O. Box 62
Oak Ridge, TN 37831

Telephone: (865) 576-8401

Facsimile: (865) 576-5728
E-Mail: [email protected]
Online ordering: http://www.osti.gov/bridge

Available to the public from

U.S. Department of Commerce
National Technical Information Service
5285 Port Royal Rd.
Springfield, VA 22161

Telephone: (800) 553-6847

Facsimile: (703) 605-6900
E-Mail: [email protected]
Online order: http://www.ntis.gov/help/ordermethods.asp?loc=7-4-0#online

2
 SAND2006-3440
Unlimited Release
Printed July 2006

Quantum Gate Decomposition Algorithms

Alexander Slepoy
Multiscale Composition Materials Methods
Sandia National Laboratories
P.O. Box 5800
Albuquerque, New Mexico 87185-MS1110

Abstract

Quantum computing algorithms can be conveniently expressed in a format of a

quantum logical circuits. Such circuits consist of sequential coupled operations,
termed “quantum gates”, on quantum analogs of bits called qubits. We review a
recently proposed method [1] for constructing general “quantum gates” operating on
a n qubits, as composed of a sequence of generic elementary “gates”.

3
4
 CONTENTS

I. Introduction ................................................................................................................................7
II. Decomposition Algorithm .........................................................................................................8
A. Cosine-Sine Decomposition ................................................................................................8
B. Quantum Circuits ................................................................................................................9
C. Uniformly Controlled Gate .................................................................................................9
D. Gray Code Ordering ............................................................................................................9
III. References ..............................................................................................................................10
Distribution ...................................................................................................................................12

FIGURES
Figure 1. .Definition of the uniformly controlled rotation .............................................................9
Figure 2. .Quantum circuit realizing the gate and Binary reflected 3-bit Gray code ...................10

5
6
 APS/123-QED

Quantum Gate Decomposition Algorithms

A. Slepoy
Sandia National Laboratories, Albuquerque, NM
(Dated: January 27, 2006)
Quantum computing algorithms can be conveniently expressed in a format of a quantum logical
circuits. Such circuits consist of sequential coupled operations, termed ”quantum gates”, on quan-
tum analogs of bits called qubits. We review a recently proposed method [1] for constructing general
”quantum gates” operating on n qubits, as composed of a sequence of generic elementary ”gates”.

PACS numbers: Valid PACS appear here

I. INTRODUCTION to another vector is a matrix, so a quantum operator is

typically represented as such.
A classical bit, an elementary unit of classical informa-
tion, is allowed two mutually exclusive values only, for ex- |Ψi = M |Φi,
ample, 1 or 0. Its quantum counterpart, qubit, can span
the continuous space between the two values through a where |Ψi and |Φi are vectors, and matrix elements of
complex-valued superposition of the two exclusive states: M are obtained through an |ei i basis projection: Mij =
hei |ej i.
|Ψi = α|0i + β|1i, A unitary operator on a vector space is a linear op-
erator that is length-preserving. A reversible operator
where α and β are complex variables. Thus, the qubit is bijective, i.e. has a well-defined inverse. These con-
potentially stores an infinite amount of information. Pro- cepts are well understood in linear algebra, have been
cessing such information could lead to extreme paral- translated to constraints on matrix properties, and time-
lelism since a single operation could transform an infi- dependent evolution of an isolated quantum system has
nite data set simultaneously. The resulting information, been demonstrated to obey such rules [2].
however, is not accessible directly, since an act of mea- A quantum gate can be represented by a general uni-
surement collapses the superposition to one of the exclu- tary transformation involving n-qubits. A quantum com-
sive values, leaving no hint of the superposition. The su- puter requires a library of quantum gates to represent or
perposition existence is revealed through repeated trials, approximate a general unitary transformation. A set of
which result in a statistical distribution of the outcomes, such gates is termed a universal library of elementary
reflective of the continuous value of the superposition co- gates. It has been demonstrated that such a library can
efficient. be constructed from single qubit unitary gates and almost
any fixed two-qubit gate [3]. Typically, a controlled-NOT
P (|0i) = kαk2 [CNOT] gate is used as the two-qubit gate mainly cho-
P (|1i) = kβk2 sen for its simplicity. Two-qubit gates operate through
the relatively weak coupling of two qubits, making such
An apparent need to query the state of the registers re- gates more difficult to implement. Therefore, efficient de-
peatedly to obtain the results seems to work against the compositions attempt to minimize the number of CNOT
advantage gained through the quantum parallelism. gates. Such gates are also constrained by the physical
The deficiency described above can be overcome proximity of the relevant qubits adding further require-
through load balancing. If a significant number of se- ments to the decomposition.
quential parallel operations can be performed on a quan- When a rotation axis corresponds to a particular
tum state of the system before collapsing it, then the con- Cartesian axis, the elementary single qubit rotations in
stant cost of measurement at the end of the execution can matrix form are
be arbitrarily amortized by the benefits of the quantum
parallelism. We do not yet understand how such load bal-  
ancing can be accomplished and construction of efficient cos(θ/2) i sin(θ/2)
Rx = eiσx θ/2 =
quantum algorithms is a subject of ongoing research. A i sin(θ/2) cos(θ/2)
set of operations can be described that transforms a col-
lective state of a quantum bus, an enumerated collection  
of qubits, without collapsing the quantum state of the iσy θ/2 cos(θ/2) sin(θ/2)
Ry = e =
system. The operators that satisfy this criterion are uni- − sin(θ/2) cos(θ/2)
tary and reversible. Since a superposition state of a sys-
tem can be conveniently viewed as a vector, much of the  
quantum operator formalism has borrowed the language iσz θ/2 eiθ/2 0
Rz = e =
of linear algebra. An operator that transforms a vector 0 e−iθ/2

7
 2

Any SU (2) operation can be accessed by at most three A. Cosine-Sine Decomposition

rotations:

CSD is an iterative procedure for decomposing a gen-

U = Rz (α)Ry (β)Rz (γ), eral unitary operator into elementary operators. A single
step in the recursion is based on the following idea:
where α, β, and γ are the Euler angles.
The two-qubit gate CNOT is represented in the basis
{|00i, |01i, |10i, |11i} as
   
L0 D0,0 D0,1 R0
U= .

1 0 0 0
 L1 D1,0 D1,1 R1
0 1 0 0
UCN OT = I ⊕ σx = 
0 0 0 1
0 0 1 0 A general unitary matrix can be decomposed into left
and right block diagonal forms, where the dimensions of
This operator performs an inversion on the state of the the two blocks sum to the original dimension, and a cen-
second cubit, if the first qubit is in |1i state, and does tral D matrix consisting of four diagonal blocks. Here,
nothing if the first qubit is in |0i state. L0 , L1 , R0 , R1 are unitary, and D0,0 , D0,1 , D1,0 , D1,1 are
The method described in the paper decomposes an ar- diagonal with D0,1 = −D0,0 . For equal-dimensional par-
bitrary n-qubit unitary gate into a set of the elementary tition, this is a special case of the Generalized SV decom-
gates. The proposed algorithm is compared to the the- position. Because of the unitary constraint,
oretical minimum number of gates required to represent
a general unitary transformation, and arrives at the an
estimated 4 times the theoretical minimum for the re- D0,0 = D1,1 = diag(C1 , C2 , ..., CN/2 ),
quired number of the crucial CNOT gates. This number D0,1 = −D1,0 = diag(S1 , S2 , ..., SN/2 ).
is allegedly the best available to date. The description of
the algorithm follows.
where Ci = cos(θi ) and Si = sin(θi ) for some angle θi .
The first step in the recursion produces three matri-
II. DECOMPOSITION ALGORITHM ces, L and R with two diagonal unitary blocks each, and
a central D with four blocks, each diagonal. The next
The method uses a Cosine-Sine Decomposition [CSD] step in the recursion operates on L0 , L1 , R0 , R1 in the
[4] and uniformly controlled rotations to represent a gen- same manner. Both L and R each become three matri-
eral unitary operation in terms of elementary gates de- ces, with the decomposition applied individually to each
scribed in the introduction. block, resulting in a product of 7 matrices:

  D1 D1 
L10 R01 L10
   
0,0 0,1
1 1
 
 L11  D1,0 D1,1 
 R11  D0,0 D0,1  L11 
 L12  1
D3,3 1
D3,4  R21  D1,0 D1,1  L12 
1
L3 1 1
D4,3 D4,4 R31 L13
1 1
 
D0,0 D0,1 R01

1 1
 D1,0 D1,1 1
 R1
.
  
1 1 
 D3,3 D3,4 R21
1 1 1
D4,3 D4,4 R3

The superscript refers to the iteration number. The trices now have a 2 × 2 block-diagonal structure. The
subscripts indicate position of block in its matrix struc- D matrices have two entries in each row connected with
ture. L, D and R matrices on the right are not the same a complimentary pair in another row by the cosine-sine
as the ones on the left, except in structure. Their entries relation. Each of these resulting matrices is termed a
are given by their respective decompositions. At the end uniformly controlled rotation.
of the recursion, we are left with a product of matrices
that have a special form. All the resulting L and R ma-

8
 3

k
B. Quantum Circuits. Let Fm (Ra ) represent an uniformly controlled rotation.
k
A special case of such rotation is Fk+1 (Ra ), which has a
A quantum circuit is a convenient representation of the matrix representation
operators as they transform the state of a multi-qubit
Ra (α1 )1
 
array. In such circuits, the wires represent the state of
.
a qubit as they progress through the operations. The .
 
 .
following quantum circuits were rendered using public
Ra (α2k )
domain software [5]. The circuit directly below is a rep-
resentation of three qubits, initialized to state |000i. where the rotation matrices are of the form
→
−
|0i Ra (φ) = eia· σ φ/2 = I (1)
|0i cos(φ/2) + i(a · − →
σ) (2)
|0i sin(φ/2). (3)

The operators are represented as quantum gates in the Here, a · −

→
σ = ax σx + ay σy + az σz . Setting ax = 0
order from left to right. This order is inverted with re- produces the following result: σx Ra (θ)σx = Ra (−θ).
spect to the ”bra-ket” notation, where the next operator Clearly, single qubit control can now undo a rotation
is right-most with respect to the ”ket”. For example, of another qubit. The fact that the CNOT gate is ex-
contrast operation CBA|0i with the circuit below. actly the ”controlled σx ” leads to a decomposition of the
uniformly controlled gate into 2k CNOTs and 2k single
|0i A B C qubit rotations.

Single qubit gates cannot represent coupling between

qubits. Mulit-qubit gates often take form of control • • =


 

gates, where the operation on a given qubit is conditional
on the state of another qubit. The circuit below expresses R̃a (θ) R̃a (−θ)
a controlled operation in which the second qubit state is
flipped with a CNOT operation if the first qubit is set:



|0i • This is an important piece of information in understand-
|0i ing the decomposition procedure.

|0i
D. Gray Code Ordering.

C. Uniformly Controlled Gate. The authors propose an algorithm where a CNOT gate
is sandwiched between two single-qubit rotation opera-
The decomposed form of the arbitrary unitary operator tors on the slave qubit. These rotations are perpendic-
now consists of a product of operators, each of which is ular to the x axis to assure the decoupled action of the
a uniformly controlled rotation. These are single-qubit CNOTs. They minimize the number of single control
rotations controlled by a joint classical state of the rest CNOTs needed to accomplish this by ordering the rota-
of the qubits. The paper defines this rotation as Fmk
(Ra ), tions and their control states according to a cyclic binary
where the m-th qubit is controlled by the 2k classical Grey code. The reordering is permitted because the oper-
states of k other qubits, example in Fig.1. ations commute. Gray code arranges the control states so
that they only differ by a value of a single bit. A realiza-
tion of the uniform rotation F43 (Ra ) with the associated
Gray code ordering is depicted in Fig. 2. The position
of the control node in the lth CNOT gate matches the
position where the lth and (l + 1)s t bit strings gl−1 and
gl of the Gray code are different.
The first CNOT gate is set by the state of the 3rd
bit, the second CNOT gate is set by the 2nd bit, and
so on. It is clear that, for any of the basis vector input
states, CNOT gates destroy each other. The rotations are
FIG. 1: Definition of the uniformly controlled rotation additive since they share a common axis Ra (φ)Ra (ω) =
F43 (Ra ) . Here a is a three-dimensional vector fixing the ro- Ra (φ + ω) for any φ and ω. The resulting operation is
tation axis of the matrices Raj = R( αj ).
a rotation of the slave qubit through an angle which is

9
 4

that solve a linear system of equations

θ1 α1
   
 .   . 
Mk  = (4)
.   . 
θ 2k α2k
.
The matrix elements of Mk can be obtained from equa-
tion 1. A rotation angle θj is reversed if the lth bit of the
gj−1 bit string is 1. Then

k
Mij = (−1)bi−1 ·gj−1 , (5)
FIG. 2: (a) Quantum circuit realizing the gate F43 (Ra ) , where
a is perpendicular to the x axis. Here the authors have used
a notation R̃j (a) = Ra (θj ) . (b) Binary reflected 3-bit Gray where bi is a standard binary representation of the integer
code used to define the positions of the control nodes. The i and the exponent is a bitwise product of binary vectors.
black and white rectangles denote bit values one and zero, The inverse of Mk is (Mk )−1 = 2−k (M k )T , so θi can
respectively. be calculated by applying the inverse to the right hand
side of Eqn. 4. This means that any uniform rotation
k
operation Fm (Ra ) around the x-axis with k ≥ 1 needs
linearly constructed of the angles θj . The circuits in the at most 2 CNOT gates and 2k single qubit rotations
k

figures 1 and 2 are equivalent if the angles θi can be found Ra (θi ).

[1] M. Mottonen, J. J. Vartiainen, V. Bergholm, and M. M. 8444.

Salomaa, Physical Review Letters 93, 130502 (2004), [4] G. H. Golub and C. F. V. Loan, Matrix Computations
ISSN 0031-9007. (The Johns Hopkins University Press, Baltimore, MD,
[2] A. Peres, Physical Review A 32, 32663276 (1985). USA, 1989), 2nd ed.
[3] A. BARENCO, PROCEEDINGS OF THE ROYAL SOCI- [5] S. Flammia and B. Eastin, Q-circuit.
ETY OF LONDON SERIES A-MATHEMATICAL AND
PHYSICAL SCIENCES 449, 679 (1995), ISSN 0962-

10
 III. REFERENCES
1. M. Mottonen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa, Physical Review Letters
93, 130502 (2004, ISSN 0031-9007.

2. A. Peres, Physical Review A 32, 32663276 (1985).

3. A. Barenco, Proceedings of the Royal Society of London Series A-Mathematical and

Physical Sciences 449, 679 (1995), ISSN 0962-8444.

4. G. H. Golub and C. F. V. Loan, Matrix Computations (The Johns Hopkins University Press,
Baltimore, MD, USA, 1989), 2nd ed.

5. S. Flammia and B. Eastin, Q-circuit.

11
DISTRIBUTION:

1 MS0321 William J. Camp 1400

1 MS0672 L. Pierson 5616
1 MS1318 David Womble 1410
1 MS1318 John B. Aidun 1435
1 MS1318 Erik DeBenedictis 1423
5 MS1318 Alex Slepoy 1435

2 MS9018 Central Technical Files 8944

2 MS0899 Technical Library 4536

12