4.2. PRIMAL DECOMPOSITION 69
with ! equal to the cubic root of unity (! D e
i 2=3
D 1=2 C i
p
3=2). Beneath each of the
4n 2 blocks is displayed the number of real parameters of the block. ese numbers sum to
16, i.e., exactly n
2
, the dimensionality of U(n).
Hence, the synthesis problem of an arbitrary U(2
w
) matrix involves, for the given value
of w, the synthesis of the 2
w
1 circuits T
j
. e synthesis of such matrices is not straigthfor-
ward [61]. For T
3
above, the following ad hoc decomposition is helpful:
T
3
D
0
B
B
@
1
1
1=
p
2 1=
p
2
1=
p
2 1=
p
2
1
C
C
A
0
B
B
@
1
1=
p
3
p
2=
p
3
p
2=
p
3 1=
p
3
i
1
C
C
A
0
B
B
@
1
1
1=
p
2 1=
p
2
1=
p
2 1=
p
2
1
C
C
A
:
However, no general-purpose technique is available for an arbitrary n n matrix of the form
(4.2) where j satisfies 2 j n 1.
e repeated application of the ZXZ theorem thus, in principle, allows the implementa-
tion of quantum circuits [61], with the help of 2 2 PHASOR gates and j j Fourier-transform
circuits with 2 j 2
w
. However, compact and elegant in mathematical form, the ZXZ de-
composition is not naturally tailored to qubit-based quantum circuits due to the presence of the
j j Fourier transforms. Indeed, whenever j is not a power of 2, the Fourier transform acts
on a subspace of the total 2
w
-dimensional Hilbert space rather than on a subset of the w qubits.
In the next section, we will demonstrate a more natural synthesis method, with all j exclusively
equal to some 2
a
with 1 a w. It will even turn out that j D 2 suffices. us only the 2 2
Fourier-transform gate, i.e., the HADAMARD gate, will be necessary.
4.2 PRIMAL DECOMPOSITION
Below we will demonstrate the more natural synthesis method, which respects the qubit struc-
ture of the quantum circuit to be synthesized. At each step, the algorithm lowers the matrix size
by a factor of 1/2. us, instead of matrices from the group sequence U(n), U(n 1), U(n 2),
…, we will take matrices from U(n), U(n=2), U(n=4), …. As a result, the method is not appli-
cable for arbitrary n, but only useful for n equal to some power of 2, i.e., for n D 2
w
. But this is
exactly the n value we need for circuit synthesis.
We recall that an arbitrary member of U(2) can be decomposed as two DU(2) matrices
and one XU(2) matrix: see (3.6). We recall that Idel and Wolf [58] proved the generalization
for an arbitrary element U of U(n) with arbitrary n:
U D D
1
XD
2
;