# An Optimization for Qubiter

## Abstract

In a previous paper, we described a computer program called Qubiter which can decompose an arbitrary unitary matrix into elementary operations of the type used in quantum computation. In this paper, we describe a method of reducing the number of elementary operations in such decompositions.

According to Eqs.(4.17) and (4.18) of Ref., if we define $`\mathrm{\Gamma }(\theta )`$ by

$$\mathrm{\Gamma }(\theta )=\mathrm{exp}(i\theta \sigma _y)I_2I_2,$$
(1)   
then

$$D=\underset{\stackrel{}{b}Bool^2}{}A_\stackrel{}{b},$$
(2)   
where

$$A_{00}=\mathrm{\Gamma }(\theta _{00}),$$
(3)   
$$A_{10}=\sigma _x(2)^{n(1)}\mathrm{\Gamma }(\theta _{10}),$$
(4)   
$$A_{11}=[\sigma _x(2)^{n(1)}\sigma _x(2)^{n(0)}]\mathrm{\Gamma }(\theta _{11}),$$
(5)   
$$A_{01}=\sigma _x(2)^{n(0)}\mathrm{\Gamma }(\theta _{01}).$$
(6)   
The operators $`A_\stackrel{}{b}`$ commute so Eq.(2) is valid regardless of the order in which the $`A_\stackrel{}{b}`$ are multiplied. Suppose we multiply them in the following order:

$$D=A_{01}A_{11}A_{10}A_{00}.$$
(7)   
Note that in this order, if $`A_{\stackrel{}{b}_L}`$ is immediately to the left of $`A_{\stackrel{}{b}_R}`$, then $`\stackrel{}{b}_L`$ and $`\stackrel{}{b}_R`$ are elements of $`Bool^2`$ that differ only in the value of one bit. Eq.(4) simplifies to

$$D=\sigma _x(2)^{n(0)}\mathrm{\Gamma }(\theta _{01})\sigma _x(2)^{n(1)}\mathrm{\Gamma }(\theta _{11})\sigma _x(2)^{n(0)}\mathrm{\Gamma }(\theta _{10})\sigma _x(2)^{n(1)}\mathrm{\Gamma }(\theta _{00}).$$
(8)   
We see that by ordering the $`A_\stackrel{}{b}`$ in this special way, many c-nots cancel out. Only one c-not remains between any two adjacent $`\mathrm{\Gamma }`$’s. There is no c-not to the right of the rightmost $`\mathrm{\Gamma }`$ in Eq.(5). And, because the leftmost $`\stackrel{}{b}`$ in Eq.(4) has only one non-zero bit, there is only one c-not to the left of the leftmost $`\mathrm{\Gamma }`$ in Eq.(5).

The above example assumes $`N_B=3`$ and that we are decomposing a central matrix of type 1 (i.e., a central matrix which is a single D matrix). However, this method of reducing the number of c-nots in a decomposition can also be used for other values of $`N_B`$ and for the other two types of central matrices. Let’s see how. For general $`N_B`$, one can (see Appendix) order the elements $`\stackrel{}{b}`$ of $`Bool^{N_B}`$ so that adjacent $`\stackrel{}{b}`$’s differ only in the value of one bit, and so that the first $`\stackrel{}{b}`$ is the zero vector and the last $`\stackrel{}{b}`$ is a standard unit vector (i.e., it has only one non-zero bit). We’ll call such an ordering of the elements of $`Bool^{N_B}`$ a “lazy” ordering (a step from one $`\stackrel{}{b}`$ to the next is “lazy” since it involves a single bit flip instead of many). Products of $`A_\stackrel{}{b}`$ operators arise in the decomposition of all three types of central matrices. If the order in which one multiples the $`A_\stackrel{}{b}`$ is such that their $`\stackrel{}{b}`$ subscripts are in a lazy order, then the number of c-nots in the decomposition will be reduced.

## APPENDIX: A Method of Generating a Lazy Ordering of $`Bool^{N_B}`$

Create a binary tree $`T`$ with $`N_B1`$ levels. Label each node of $`T`$ by its level number (top is 0, bottom is $`N_B1`$). See Fig.1 for $`T`$ when $`N_B=3`$. Create a sequence $`s=(s_1,s_2,\mathrm{},s_{N_S1})`$ of integers by recording the node labels encountered during an “inorder transversal” of the tree. For example, for Fig.1, $`s=(2,1,2,0,2,1,2)`$. Let $`\stackrel{}{b}_0=\stackrel{}{0}Bool^{N_B}`$. On step $`j\{1,2,\mathrm{},N_S1\}`$, $`\stackrel{}{b}_{j1}`$ transforms into $`\stackrel{}{b}_j`$ when you flip the bit at position $`s_j`$. As usual, we label the bit positions so that they increase from right to left and the rightmost bit is at position 0.

Fig.1 A lazy ordering of $`Bool^3`$