text:
# Next Nearest-Neighbor Correlation Functions of the Spin-1/2 XXZ Chain at Critical Region

(April 22, 2003)

## Abstract

The correlation functions of the spin-$`\frac{1}{2}`$ $`XXZ`$ spin chain in the ground state are expressed in the form of the multiple integrals. For $`1<\mathrm{\Delta }<1`$, they were obtained by Jimbo and Miwa in 1996. Especially the next nearest-neighbour correlation functions are given as certain three-dimensional integrals. We shall show these integrals can be reduced to one-dimensional ones and thereby evaluate the values of the next nearest-neighbor correlation functions. We have also found that the remaining one-dimensinal integrals can be evaluated analytically, when $`\nu =\mathrm{cos}^1(\mathrm{\Delta })/\pi `$ is a rational number.

The spin-1/2 $`XXZ`$ chain is one of the fundamental models in the study of the low-dimensional magnetism. The Hamiltonian is given by

$`H={\displaystyle \underset{j=\mathrm{}}{\overset{\mathrm{}}{}}}\left\{S_j^xS_{j+1}^x+S_j^yS_{j+1}^y+\mathrm{\Delta }S_j^zS_{j+1}^z\right\},`$ (1)
where $`S=\sigma /2`$ and $`\sigma `$ are Pauli matrices. The model can be solved by Bethe ansatz method and diverse physical properties have been investigated with varying the anisotropy parameter $`\mathrm{\Delta }`$ Bethe31 ; Hulthen38 ; TakahashiBook ; KorepinBook . Especially, in the region $`1<\mathrm{\Delta }1`$, the ground state is critically disordered and the excitation spectrum is gapless. Then the long-distance asymptotics of two-point the correlation functions such as $`S_j^\alpha S_{j+k}^\alpha _{k1}\alpha =x,y,z`$ are shown to decay as a power law via field theoretical approach (see, for example, Lukyanov03  and the references therein). However, if possible, it is more desirable
(1) to calculate $`S_j^\alpha S_{j+k}^\alpha `$ for finite $`k`$ first and
(2) to derive its asymptotic behavior exactly.
Unfortunately such a program has not been achieved except for the $`\mathrm{\Delta }=0`$ case Lieb61 ; McCoy68 .

In 1996, Jimbo and Miwa Jimbo96  obtained the multiple integral representation for the arbitrary correlation functions of the $`XXZ`$ chain for $`1<\mathrm{\Delta }<1`$. For example, the Emptiness Formation Probability (EFP) Korepin94  defined by

$`P(n)={\displaystyle \underset{j=1}{\overset{n}{}}}\left(S_j^z+{\displaystyle \frac{1}{2}}\right),`$ (2)
has the integral representation

$`P(n)`$ $`=\left(\nu \right)^{\frac{n(n1)}{2}}{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}x_1}{2\pi }}\mathrm{}{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}x_n}{2\pi }}{\displaystyle \underset{a>b}{}}{\displaystyle \frac{\mathrm{sinh}(x_ax_b)}{\mathrm{sinh}\left(\left(x_ax_b\mathrm{i}\pi \right)\nu \right)}}`$
$`\times {\displaystyle \underset{k=1}{\overset{n}{}}}{\displaystyle \frac{\mathrm{sinh}^{nk}\left(\left(x_k+\mathrm{i}\pi /2\right)\nu \right)\mathrm{sinh}^{k1}\left(\left(x_k\mathrm{i}\pi /2\right)\nu \right)}{\mathrm{cosh}^nx_k}},`$ (3)
where the parameter $`\nu `$ is related to the anisotropy $`\mathrm{\Delta }`$ as

$`\nu ={\displaystyle \frac{1}{\pi }}\mathrm{cos}^1(\mathrm{\Delta }).`$ (4)
Recently there have been an increasing number of researches concerning the properties of the EFP Korepin94 ; Essler95n1 ; Essler95n2 ; Kitanine00 ; Razumov01 ; Kitanine02n1 ; Shiroishi01 ; Boos01 ; Boos02 ; BKNS02 ; Boos03 ; Abanov02 ; Korepin03 ; Kitanine02n2 . Particularly, in the isotropic limit $`\mathrm{\Delta }1(\nu 0)`$, the general method to evaluate the multiple integral was recently developed by Boos and Korepin Boos01 ; Boos02 ; BKNS02 .

It is of some importance to note that $`P(2)`$ and $`P(3)`$ are related to the nearest and next nearest-neighbor correlation functions :

$`S_j^zS_{j+1}^z`$ $`=P(2)1/4,`$ (5)
$`S_j^zS_{j+2}^z`$ $`=2(P(3)P(2)+1/8).`$ (6)
One of our purposes in this letter is to evaluate $`S_j^zS_{j+2}^z`$ through the integral representations of $`P(3)`$ and $`P(2)`$. Similarly the nearest and the next nearest-neighbor transverse correlation functions have the integral representations,

$`S_j^xS_{j+1}^x={\displaystyle \frac{1}{2\nu }}{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}x_1}{2\pi }}{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}x_2}{2\pi }}{\displaystyle \frac{\mathrm{sinh}(x_2x_1)}{\mathrm{sinh}\left(\left(x_2x_1\right)\nu \right)}}{\displaystyle \frac{\mathrm{sinh}\left(\left(x_1+\mathrm{i}\pi /2\right)\nu \right)\mathrm{sinh}\left(\left(x_2\mathrm{i}\pi /2\right)\nu \right)}{\mathrm{cosh}^2x_1\mathrm{cosh}^2x_2}},`$ (7)
and

$`S_j^xS_{j+2}^x`$ $`={\displaystyle \frac{1}{\nu ^3}}{\displaystyle \underset{k=1}{\overset{3}{}}}{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}x_k}{2\pi }}{\displaystyle \frac{\mathrm{sinh}^{3k}\left(\left(x_k+\mathrm{i}\pi /2\right)\nu \right)\mathrm{sinh}^{k1}\left(\left(x_k\mathrm{i}\pi /2\right)\nu \right)}{\mathrm{cosh}^3x_k}}`$
$`\times {\displaystyle \frac{\mathrm{sinh}(x_2x_1)}{\mathrm{sinh}\left(\left(x_2x_1\right)\nu \right)}}{\displaystyle \frac{\mathrm{sinh}(x_3x_1)}{\mathrm{sinh}\left(\left(x_3x_1\right)\nu \right)}}{\displaystyle \frac{\mathrm{sinh}(x_3x_2)}{\mathrm{sinh}\left(\left(x_3x_2\mathrm{i}\pi \right)\nu \right)}},`$ (8)
respectively.

It was already shown by Jimbo and Miwa that the two-dimensional integral for $`P(2)`$ reduces to the one-dimensional one for arbitrary $`\nu `$ as

$`P(2)={\displaystyle \frac{1}{2}}+{\displaystyle \frac{1}{2\pi ^2\mathrm{sin}\pi \nu }}{\displaystyle \frac{}{\nu }}\left\{\mathrm{sin}\pi \nu {\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{sinh}(1\nu )w}{\mathrm{sinh}w\mathrm{cosh}\nu w}}dw\right\},`$ (9)
which leads to the one-dimensional integral representation of $`S_j^zS_{j+1}^z`$ via the relation (5). The result coincides with a different derivation of $`S_j^zS_{j+1}^z`$ from the ground-state energy per site $`e_0`$ :

$`S_j^zS_{j+1}^z`$ $`={\displaystyle \frac{e_0}{\mathrm{\Delta }}}={\displaystyle \frac{1}{\pi \mathrm{sin}\pi \nu }}{\displaystyle \frac{e_0}{\nu }}`$
$`={\displaystyle \frac{1}{4}}+{\displaystyle \frac{\mathrm{cot}\pi \nu }{2\pi }}{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}w}{\mathrm{sinh}w}}{\displaystyle \frac{\mathrm{sinh}(1\nu )w}{\mathrm{cosh}\nu w}}{\displaystyle \frac{1}{2\pi ^2}}{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}w}{\mathrm{sinh}w}}{\displaystyle \frac{w\mathrm{cosh}w}{(\mathrm{cosh}\nu w)^2}},`$ (10)
where

$`e_0={\displaystyle \frac{\mathrm{\Delta }}{4}}{\displaystyle \frac{\mathrm{sin}\pi \nu }{2\pi }}{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{sinh}(1\nu )w}{\mathrm{sinh}w\mathrm{cosh}\nu w}}dw.`$ (11)
Similarly we can get the one-dimensional integral representation for $`S_j^xS_{j+1}^x`$ as

$`S_j^xS_{j+1}^x`$ $`={\displaystyle \frac{1}{2}}\left(e_0\mathrm{\Delta }S_j^zS_{j+1}^z\right)`$
$`={\displaystyle \frac{1}{4\pi \mathrm{sin}\pi \nu }}{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}w}{\mathrm{sinh}w}}{\displaystyle \frac{\mathrm{sinh}(1\nu )w}{\mathrm{cosh}\nu w}}+{\displaystyle \frac{\mathrm{cos}\pi \nu }{4\pi ^2}}{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}w}{\mathrm{sinh}w}}{\displaystyle \frac{w\mathrm{cosh}w}{(\mathrm{cosh}\nu w)^2}}.`$ (12)
Thus, for the nearest-neighbor correlation functions, we have known the two-dimensional integrals by Jimbo-Miwa formula can be reduced to one-dimensional ones. The main result of this letter is that three-dimensional integrals for $`P(3)`$ and $`S_j^xS_{j+2}^x`$ can also be reduced to one-dimensional integrals. In other words, we have succeeded in performing the integrals for $`P(3)`$ and $`S_j^xS_{j+2}^x`$ twice. Our results are

$`P(3)`$ $`={\displaystyle \frac{1}{2}}+{\displaystyle _{\mathrm{}\mathrm{i}\delta }^{\mathrm{}\mathrm{i}\delta }}{\displaystyle \frac{\mathrm{d}x}{\mathrm{sinh}x}}[{\displaystyle \frac{1\mathrm{cos}2\pi \nu }{16\pi ^2}}{\displaystyle \frac{}{\nu }}\left\{{\displaystyle \frac{\mathrm{cosh}3\nu x}{(\mathrm{sinh}\nu x)^3}}\right\}+{\displaystyle \frac{3\mathrm{tan}\pi \nu }{8\pi }}{\displaystyle \frac{\mathrm{cosh}3\nu x}{(\mathrm{sinh}\nu x)^3}}`$
$`{\displaystyle \frac{4\mathrm{cos}2\pi \nu }{4\pi ^2}}{\displaystyle \frac{\left(\mathrm{coth}\nu x\right)}{\nu }}{\displaystyle \frac{\left(4\mathrm{cos}2\pi \nu \right)\mathrm{coth}\nu x}{2\pi \mathrm{sin}2\pi \nu }}],`$ (13)
and

$`S_j^xS_{j+2}^x`$ $`={\displaystyle _{\mathrm{}\mathrm{i}\delta }^{\mathrm{}\mathrm{i}\delta }}{\displaystyle \frac{\mathrm{d}x}{\mathrm{sinh}x}}[{\displaystyle \frac{\left(\mathrm{sin}\pi \nu \right)^2}{8\pi ^2}}{\displaystyle \frac{}{\nu }}\left\{{\displaystyle \frac{\mathrm{cosh}3\nu x}{(\mathrm{sinh}\nu x)^3}}\right\}{\displaystyle \frac{3\mathrm{cos}2\pi \nu (1\mathrm{cos}2\pi \nu )}{8\pi \mathrm{sin}2\pi \nu }}{\displaystyle \frac{\mathrm{cosh}3\nu x}{(\mathrm{sinh}\nu x)^3}}`$
$`+{\displaystyle \frac{1}{4\pi ^2}}{\displaystyle \frac{\left(\mathrm{coth}\nu x\right)}{\nu }}+{\displaystyle \frac{\left\{1+3\mathrm{cos}2\pi \nu 3\left(\mathrm{cos}2\pi \nu \right)^2\right\}\mathrm{coth}\nu x}{2\pi \mathrm{sin}2\pi \nu }}].`$ (14)
Here $`\delta (0<|\delta |<\pi )`$ should take some non-zero real value, which is introduced to avoid the singularity at the origin. We, however, note that the singular term may be subtracted from the integrand in principle, as its residue vanishes. Or alternatively, by applying the Fourier transform, we can express the one-dimensional representations (13) and (14) as

$`P(3)`$ $`={\displaystyle \frac{1}{2}}+{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}w}{\mathrm{sinh}w}}{\displaystyle \frac{\mathrm{sinh}(1\nu )w}{\mathrm{cosh}\nu w}}\left[{\displaystyle \frac{1+2\mathrm{cos}2\pi \nu }{2\pi \mathrm{sin}2\pi \nu }}+{\displaystyle \frac{3\mathrm{tan}\pi \nu }{4\pi ^3}}w^2\right]`$
$`{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}w}{\mathrm{sinh}w}}{\displaystyle \frac{\mathrm{cosh}w}{(\mathrm{cosh}\nu w)^2}}\left[{\displaystyle \frac{3}{4\pi ^2}}w+{\displaystyle \frac{(\mathrm{sin}\pi \nu )^2}{4\pi ^4}}w^3\right],`$ (15)
and

$`S_j^xS_{j+2}^x`$ $`={\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}w}{\mathrm{sinh}w}}{\displaystyle \frac{\mathrm{sinh}(1\nu )w}{\mathrm{cosh}\nu w}}\left[{\displaystyle \frac{1}{2\pi \mathrm{sin}2\pi \nu }}+{\displaystyle \frac{3\mathrm{cos}2\pi \nu \mathrm{tan}\pi \nu }{4\pi ^3}}w^2\right]`$
$`+{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}w}{\mathrm{sinh}w}}{\displaystyle \frac{\mathrm{cosh}w}{(\mathrm{cosh}\nu w)^2}}\left[{\displaystyle \frac{\mathrm{cos}2\pi \nu }{4\pi ^2}}w+{\displaystyle \frac{(\mathrm{sin}\pi \nu )^2}{4\pi ^4}}w^3\right].`$ (16)
Note that in the representations (15) and (16), there are no singularities at the origin. This is in the similar situation as (10) and (12). Combining (9) and (15), we can also write down the one-dimensional integral representation for $`S_j^zS_{j+2}^z`$ through the relation (6),

$`S_j^zS_{j+2}^z`$ $`={\displaystyle \frac{1}{4}}+{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}w}{\mathrm{sinh}w}}{\displaystyle \frac{\mathrm{sinh}(1\nu )w}{\mathrm{cosh}\nu w}}\left[{\displaystyle \frac{\mathrm{cot}2\pi \nu }{\pi }}+{\displaystyle \frac{3\mathrm{tan}\pi \nu }{2\pi ^3}}w^2\right]`$
$`{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \frac{\mathrm{d}w}{\mathrm{sinh}w}}{\displaystyle \frac{\mathrm{cosh}w}{(\mathrm{cosh}\nu w)^2}}\left[{\displaystyle \frac{1}{2\pi ^2}}w+{\displaystyle \frac{(\mathrm{sin}\pi \nu )^2}{2\pi ^4}}w^3\right].`$ (17)
Now let us discuss some properties of the obtained one-dimensional representations (16) and (17). At a first glance, some integrands in (16) and (17) are divergent at $`\nu =1/2`$ and also in the limit $`\nu 0`$ and $`\nu 1`$, due to the the factor $`1/\mathrm{sin}2\pi \nu `$. However, by investigating the integrands carefully, we have found these singular terms cancel each other, therefore yielding definite finite values for the correlation functions :

* $`\nu =1/2`$ :

$`S_j^xS_{j+2}^x={\displaystyle \frac{1}{\pi ^2}},S_j^zS_{j+2}^z=0,`$ (18)
* $`\nu 0`$ :

$`S_j^xS_{j+2}^x,S_j^zS_{j+2}^z{\displaystyle \frac{1}{12}}{\displaystyle \frac{4}{3}}\mathrm{ln}2+{\displaystyle \frac{3}{4}}\zeta (3),`$ (19)
* $`\nu 1`$ :

$`S_j^xS_{j+2}^x{\displaystyle \frac{1}{8}},S_j^zS_{j+2}^z0.`$ (20)

It is especially intriguing to observe that the $`\nu 0`$ limit (19) reproduces the known result by one of the authors in Takahashi77 .

More generally, we have found when $`\nu `$ takes a rational value, the one-dimensional integrals can be evaluated analytically. Some of our explicit results are summarized in Table 1. One can see that the correlation functions are in general a polynomial of $`1/\pi `$. Particularly, when $`\nu =1/3`$, we expect all the correlation functions are given solely as a single rational number (c.f. Razumov01 ; Kitanine02n1 ). In Fig. 1 and Fig. 2, plotted are the numerical values of the nearest and the next nearest-neighbor correlation functions calculated from the one-dimensional integral representations. For comparison, the analytical values in Table 1 are represented by the filled circles.

We have obtained (13) and (14) by generalizing the method developed by Boos and Korepin Boos01 ; Boos02 , which allows us to calculate the multiple integrals for the correlation functions of the $`XXX`$ model ($`\mathrm{\Delta }=1`$). Below we outline the derivation of (13) and (14) quite briefly. The details of the calculations will be published in a separate paper Kato03 . First we introduce the following convenient notation for $`P(3)`$ :

$`P(3)={\displaystyle \underset{k=1}{\overset{3}{}}}{\displaystyle _{\mathrm{}\mathrm{i}/2}^{\mathrm{}\mathrm{i}/2}}{\displaystyle \frac{\mathrm{d}\lambda _k}{2\pi \mathrm{i}}}U_3(\lambda _1,\lambda _2,\lambda _3)T_3(\lambda _1,\lambda _2,\lambda _3),`$ (21)
where

$`U_3(\lambda _1,\lambda _2,\lambda _3)={\displaystyle \frac{\pi ^3_{1k<j3}\mathrm{sinh}\pi \left(\lambda _j\lambda _k\right)}{\nu ^3_{j=1}^3\mathrm{sinh}^3\pi \lambda _j}},`$ (22)
and

$`T_3(\lambda _1,\lambda _2,\lambda _3)={\displaystyle \frac{(qz_11)^2(qz_21)(z_21)(z_31)^2}{8(z_2qz_1)(z_3qz_1)(z_3qz_2)}},`$ (23)
with $`q\mathrm{e}^{2\pi \mathrm{i}\nu },z_i\mathrm{e}^{2\pi \nu \lambda _i},(i=1,2,3)`$. Then after similar but more complicated calculation as Boos and Korepin Boos02 , we can transform the integrand $`T_3(\lambda _1,\lambda _2,\lambda _3)`$ into a certain canonical form without changing the value of the integral as

$`T_c=P_0+{\displaystyle \frac{P_1}{z_2z_1}},`$ (24)
where

$`P_0=`$ $`{\displaystyle \frac{(1+q)^2}{8q}}{\displaystyle \frac{z_1}{z_3}},`$ (25)
$`P_1=`$ $`{\displaystyle \frac{3(1+q)}{2q}}{\displaystyle \frac{(1+10q+q^2)z_1}{8q}}{\displaystyle \frac{3(1+q)^2}{8q^2z_1}}`$
$`+z_3\left\{{\displaystyle \frac{1+10q+q^2}{8q}}+{\displaystyle \frac{3(1+q)z_1}{8}}+{\displaystyle \frac{3(1+q)}{8qz_1}}\right\}`$
$`+{\displaystyle \frac{1}{z_3}}\left\{{\displaystyle \frac{3(1+q)^2}{8q^2}}+{\displaystyle \frac{3(1+q)z_1}{8q}}+{\displaystyle \frac{(1+q)(1+q+q^2)}{8q^3z_1}}\right\}.`$ (26)
We find the first part of $`T_c`$, namely $`P_0`$, can be integrated easily

$`{\displaystyle \underset{k=1}{\overset{3}{}}}{\displaystyle _{\mathrm{}\mathrm{i}/2}^{\mathrm{}\mathrm{i}/2}}{\displaystyle \frac{\mathrm{d}\lambda _k}{2\pi \mathrm{i}}}U_3(\lambda _1,\lambda _2,\lambda _3){\displaystyle \frac{(1+q)^2\mathrm{e}^{2\pi \nu (\lambda _1\lambda _3)}}{8q}}={\displaystyle \frac{1}{2}}.`$ (27)
The second part $`P_1/(z_2z_1)`$ can be integrated twice, namely with respect to $`\lambda _3`$ and $`a(\lambda _2+\lambda _1)/2`$. Finally the remaining one-dimensional integration with respect to $`d(\lambda _2\lambda _1)/2`$ together with (27) gives the expression (13).

Similarly for $`S_j^xS_{j+2}^x`$, $`T_3(\lambda _1,\lambda _2,\lambda _3)`$ in (21) is replaced by

$`T_3(\lambda _1,\lambda _2,\lambda _3)={\displaystyle \frac{(qz_11)^2(qz_21)(z_21)(z_31)^2}{8q(z_2z_1)(z_3z_1)(z_3qz_2)}}.`$ (28)
As a corresponding canonical form, we have found

$`T_c={\displaystyle \frac{P_1}{z_2z_1}},`$ (29)
with

$`P_1=`$ $`{\displaystyle \frac{(1+q)(3+q^2)}{8q^2}}+{\displaystyle \frac{(32q+3q^2)z_1}{8q}}+{\displaystyle \frac{(1+q)^2}{8q^3z_1}}`$
$`+z_3\left\{{\displaystyle \frac{3q}{4q}}{\displaystyle \frac{(1+q)z_1}{8q}}+{\displaystyle \frac{(1+q)(2+q)}{8q^2z_1}}\right\}`$
$`+{\displaystyle \frac{1}{z_3}}\left\{{\displaystyle \frac{1+q}{2q}}{\displaystyle \frac{(1+q)z_1}{8}}{\displaystyle \frac{1+q}{8q^2z_1}}\right\}.`$ (30)
Again after integrating with respect to $`\lambda _3`$ and $`a(\lambda _2+\lambda _1)/2`$, we arrive at the one-dimensional integral representation (14).

In conclusion, we have shown the multiple integrals for the correlation functions of the $`XXZ`$ chain at the critical region $`1<\mathrm{\Delta }<1`$, can be reduced to the one-dimensional ones in the case of the next nearest-neighbor correlation functions. This property will be generalized to other higher-neighbor correlations as well as the correlations in the massive region ($`\mathrm{\Delta }>1`$) Jimbo92 ; JimboBook . In this respect, we like to refer to the recent work by Boos, Korepin and Smirnov BKS03 , where they have shown the reducibility of the multiple integrals in the case of the $`XXX`$ chain.

In our future work, we are particularly interested in calculating the third-neighbor correlation functions $`S_j^xS_{j+3}^x`$ and $`S_j^zS_{j+3}^z`$ for general $`\mathrm{\Delta }`$. For $`\mathrm{\Delta }=1`$, they were recently calculated in Sakai03  from the multiple integrals Korepin94 ; Nakayashiki94  by Boos-Korepin method .

We are grateful to H.E. Boos, M. Jimbo, V.E. Korepin, Y. Nishiyama, J. Suzuki and M. Wadati for valuable discussions. This work is in part supported by Grant-in-Aid for the Scientific Research (B) No. 14340099 from the Ministry of Education, Culture, Sports, Science and Technology, Japan. GK and KS are supported by the JSPS research fellowships for young scientists. MS is supported by Grant-in-Aid for young scientists No. 14740228.


format: text

text:
# Quantum computation based on d-level cluster state

## I Introduction

Quantum computers can process computational tasks that are intractable with classical computers. The reason lies in the fact that quantum computing systems composed by qubits (two-level quantum systems) possess mysterious quantum coherence, such as entanglement (or quantum correlation), which has no counterpart in the classical realm Ni . Recently, an important kind of entangled states, cluster states Bri , was introduced with remarkable property—the maximal connectedness, i.e., each pair of qubits can be projected onto maximally entanglement state with certainty by single-qubit measurements on all the other qubits. More surprisingly, it was shown that the cluster states can be used to build a one-way universal quantum computer, in which all the operations can be implemented by single-qubit measuments only Rau . As one of the key elements to realize such a scalable quantum computer, a celebrated theorem proved by R. Raussendorf and H. J. Briegel provides a simple criterion for the functioning of gate simulations on such quantum computer Rau1 . It was pointed out that the protocol of cluster state computers can be easily realized in practical physical systems since the creation of the cluster states needs only Ising-type interactions Bri . In fact, it has been demonstrated that the Hamiltonian with such interactions can be easily found in the solid state lattice systems with proper spin-spin interactions Bri , even in the system for cold atoms in optical lattices Du .

Theoretically, it is natural to ask whether the concept of cluster states would have its counterpart in higher dimensional Hilbert space, i.e., the qudits cases, since most of the available physical systems can not be treated as a two-level systems even in an approximate way. The answer to this question is affirmative. Using a pair of non-commutative operators $`X`$ and $`Z`$, which will be identified with the $`d`$ dimensional irreducible representations of Manin’s quantum plane algebra (QPA) in Sec. II Sun , we find that the qudit cluster states $`|\varphi _𝒞`$ can be defined as a common eigenstate of the tensor product operators

$$X_a^{}\underset{b\mathrm{𝚗𝚋𝚐𝚑}(a)}{}Z_b,$$
(1)
where the lower indexes $`a`$ and $`b`$ denote qudit $`a`$ and qudit $`b`$ in the cluster, and index $`b`$ is taken in the neighborhood of index $`a`$ depending on the cluster structure. Based on this definition of qudit cluster states, we further show that we can build an one way universal quantum computer by explicitly demonstrating how to construct all single qudit unitary gates and one imprimitive two-qudit gate.

We organize our paper as follows: We first briefly review the finite dimensional representations of quantum plane algebra in Sec. II, which provides the main mathematical tools in this article. As a non-trivial generalization of the qubit cluster state, the qudit cluster state is defined according to the quantum plane algebra, and its essential properties of quantum correlations are analyzed in Sec. III. In Sec.IV, the one-way quantum computer based on qudit cluster states is proposed with crucial supports from the proof of a central theorem. Similar to that for qubit case Rau1 , this theorem guarantees the functioning of gate simulations on those computers. Its proof depends on the subtle understanding about the quantum correlations of the qudit cluster states. In Sec. V, the universality of the qudit cluster state computers is proved through the explicit construction of all the single- and one two-qudit logic gates. Finally, we give our conclusion in the last section.

## II Finite dimensional representaions of quantum plane algebra

In this section, we will review the mathematics for finite dimensional representations of Manin’s quantum plane algebra, which will be the main mathematical tool to describe not only qudit cluster states but also unitary transformation on the Hilbert space. The Manin’s quantum plane is defined by

$$XZ=qZX,$$
(2)
where $`q`$ is a complex number. Mathematically, it can be proved that the associated algebra generated by $`Z`$, $`X`$ possesses a $`d`$dimensional irreducible representation only for $`q^d=1`$ Sun . In this article, we take $`qq_de^{i\frac{2\pi }{d}}`$. This special case is first introduced by Weyl Wey  and whose completeness is first proved by Schwinger Sch . Obviously, when $`d=1,q=1`$, $`X`$ and $`Z`$ can be regarded as the ordinary coordinates of $`R^2`$ plane; When $`d=2,q=1`$, $`X`$ and $`Z`$ can be identified with the Pauli matrices $`\sigma _x`$ and $`\sigma _z`$. In this sense $`Z`$ and $`X`$ can be regarded as the so-called “generalized Pauli operators” Bar1 ; San ; Dab ; Got ; Pat ; Kni .

In fact, when $`q=q_d`$, $`Z^d`$ and $`X^d`$ commutate with the algebra generators, so they belong to the center of QPA. The Shur’s lemma tells us $`Z^d`$ and $`X^d`$ are constants multiples of the $`d`$dimensional identity matrix, i.e., $`Z^d=zI`$ and $`X^d`$ $`=xI`$. In general we can normalize them to the identity. Since the complex field $`C`$ is algebraically closed, there must exist an eigen-state $`|0`$, which satisfies

$$Z|0=|0.$$
(3)
According to Eq. (2), we obtain all the eigenvalue equations for operator $`Z`$

$$Z|k=q_d^k|k,(kZ_d),$$
(4)
where $`|k=X^k|0`$. This also implies

$$X|k=|k1.$$
(5)
In the $`Z`$-diagonal representation, the matrices of $`X`$ and $`Z`$ are:

$$Z=\left[\begin{array}{cccccc}1& 0& 0& \mathrm{}& 0& 0\\ 0& q_d& 0& \mathrm{}& 0& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 0& 0& 0& \mathrm{}& q_d^{d2}& 0\\ 0& 0& 0& \mathrm{}& 0& q_d^{d1}\end{array}\right],$$
(6)
$$X=\left[\begin{array}{cccccc}0& 1& 0& \mathrm{}& 0& 0\\ 0& 0& 1& \mathrm{}& 0& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 0& 0& 0& \mathrm{}& 1& 0\\ 1& 0& 0& \mathrm{}& 0& 0\end{array}\right].$$
(7)
From Eq. (5), we have

$$X|x(0)=|x(0),$$
(8)
where

$$|x(0)=\frac{1}{\sqrt{d}}\underset{k=0}{\overset{d1}{}}|k.$$
(9)
Similar to the eigenvalue equation of $`Z`$, we have

$$X|x(j)=q_d^j|x(j),$$
(10)
where

$$|x(j)=Z^j|x(0)=\frac{1}{\sqrt{d}}\underset{k=0}{\overset{d1}{}}q_d^{jk}|k.$$
(11)
Corresponding to this representation, we can also define $`Z(d)`$ algebra as generated by $`Z`$, $`X`$. Its all basis elements

$$B=\{Z^jX^k,(j,kZ_d)\},$$
(12)
are called unitary operator bases in Ref. Sch . The general commutation relations for any two basis elements are

$$X^jZ^k=q_d^{jk}Z^kX^j.$$
(13)
In addition, we can replace the generators $`Z`$ and $`X`$ with two other elements in the basis. First, Let $`(m,n)`$ be the greatest common factor of integers $`m`$ and $`n`$. Then if $`(m_1,n_1)=1,(m_1,n_1Z_d)`$, we can take

$$\overline{Z}=q_d^{\frac{d1}{2}m_1n_1}Z^{m_1}X^{n_1},$$
(14)
where the factor before $`Z^mX^n`$ makes $`\overline{Z}`$ have the same eigenvalues with $`Z`$. To maintain Eq. (2), we take

$$\overline{X}=q_d^{\frac{d1}{2}m_2n_2}Z^{m_2}X^{n_2},$$
(15)
where $`(m_2,n_2)=1,(m_2,n_2Z_d)`$, and $`m_1n_2m_2n_1=1`$. From another viewpoint, $`\overline{Z}`$ and $`\overline{X}`$ defines a unitary transformation $`U`$

$$\overline{Z}=UZU^{},\overline{X}=UXU^{}.$$
(16)
By the above definition, it is easy to check that all this kind of unitary transformations form a group. In fact, it is the so-called Clifford group, which is a useful concept in universal quantum computation.

## III Qudit cluster states in quantum plane

To generalize the concept of qubit cluster states to qudit cases, we first restrict ourselves to one dimensional lattices for the sake of the conceptual simplicity. First, let us recall the definition of one-dimensional cluster states for $`N`$ qubits. For a $`N`$-site lattice, each qubit is attached to a site. As a novel multi-qubit entanglement state, the cluster state is written as

$$|\varphi _𝒞=\frac{1}{2^{N/2}}\underset{a=1}{\overset{N}{}}(|0_a+|1_a(\sigma _z)_{a+1}),$$
(17)
where $`(\sigma _i)_a(i=x,y,z)`$ are the Pauli matrices assigned for site $`a`$ in the lattice, and

$$\sigma _z|s=(1)^s|s,(s\{0,1\}).$$

Analogy to Eq. (17), it is natural to conjuncture that the qudit cluster state in one dimension as

$$|\varphi _𝒞=\frac{1}{d^{N/2}}\underset{a=1}{\overset{N}{}}\left(\underset{k=0}{\overset{d1}{}}|k_aZ_{a+1}^k\right),$$
(18)
where

$$Z_a|k_a=q_d^k|k_a,a.$$
(19)
Now we present one of our main result:

###### Theorem 1

The qudit cluster state in one dimension defined by Eq. (18) is a common eigen-state, with eigen-values being equal to $`1`$, of the operators $`X_a^{}\underset{b\mathrm{𝚗𝚋𝚐𝚑}(a)}{}Z_b`$ , i.e.,

$$X_a^{}\underset{b\mathrm{𝚗𝚋𝚐𝚑}(a)}{}Z_b|\varphi _𝒞=|\varphi _𝒞,$$
(20)
where

$$\mathrm{𝚗𝚋𝚐𝚑}(a)=\{\begin{array}{cc}\{2\},\hfill & a=1,\hfill \\ \{N1\},\hfill & a=N,\hfill \\ \{a1,a+1\},\hfill & a\{1,N\}.\hfill \end{array}$$
(21)
Proof. To prove this theorem, we notice that qudit cluster state (18) can be constructed in the following procedure. We first prepare a product state

$$|+=\underset{a=1}{\overset{N}{}}|x(0)_a,$$

then apply a unitary transformation

$$S=\underset{ba=1}{}S_{ab}$$
(22)
to the state $`|+`$. Here $`S_{ab}`$ is defined by as an intertwining operator

$$S_{ab}|j_a|k_b=q_d^{jk}|j_a|k_b.$$
(23)
It is easy to prove

$$|\varphi _𝒞=S|+.$$
(24)
Since $`X_a^{}|+=|+`$, it is easy to check

$$SX_a^{}S^{}|\varphi _𝒞=|\varphi _𝒞.$$
(25)
The next step is to prove

$$SX_a^{}S^{}=X_a^{}\underset{b\mathrm{𝚗𝚋𝚐𝚑}(a)}{}Z_b$$

To this end, for $`a,b,c\{1,\mathrm{},N\}`$, we observe that

$$S_{ab}X_a^{}S_{ab}^{}=X_a^{}Z_b,$$
(26)
$$S_{ab}X_b^{}S_{ab}^{}=Z_aX_b^{},$$
(27)
$$S_{ab}X_c^{}S_{ab}^{}=X_c^{},c\{a,b\},$$
(28)
and

$$S_{ab}Z_cS_{ab}^{}=Z_c,c.$$
(29)
This completes the proof. $`\mathrm{}`$

Although the above proof is restricted to one dimensional cluster, it is convenient to generalize from one-dimensional qudit cluster to more complex clusters whether in two or three dimensional space. In fact, for a general cluster $`C`$ with one qudit on each site, the cluster state $`|\varphi _𝒞`$ is defined by the following eigen-equations:

$$X_a^{}\underset{b\mathrm{𝚗𝚋𝚐𝚑}(a)}{}Z_b|\varphi _𝒞=|\varphi _𝒞.$$
(30)
Formally, the definition of a general cluster is the same as one dimensional case. Different clusters correspond to different relations of neighbours.

Now we will discuss the properties of quantum correlations in the above cluster states under single qudit measurements. For simplicity, we still restrict ourselves to one dimensional case.

First, let us discuss how to describe a von Neumann measurement for single qudit. Although the generator $`Z`$ (or $`X`$) is not Hermitian, i.e., the eigenvalues of $`Z`$ (or $`X`$) are not real, the non-degenerate eigenstates of $`Z`$ (or $`X`$) can still form a complete orthogonal basis of $`H_d`$. Therefore they can be used to define a von Neumann measurement. For example, when we make a measurement marked by $`Z`$, we mean that we can obtain different results corresponding to different eigenstates of $`Z`$.

Next, we discuss the minimal number of single qudit measurements needed to destroy all the quantum correlations in qudit cluster states. For the one dimensional cluster state, we find all quantum entanglement will be destroyed by measuring $`Z_{2a},(a=1,2,\mathrm{},[N/2])`$.

Finally, we will discuss the most remarkable property - maximally connected - of qudit cluster state, i.e., each pair of qudits in the cluster can be projected onto maximally entanglement state with certainty by single-qudit measurement with all the other qudits. In fact, to project arbitrary two qudits in one dimensional cluster onto maximally entanglement state, we only need to measure $`X`$ for the qudits between them, and $`Z`$ for all the other qudits. It is easy to find that two or three dimensional qudit cluster states is also maximally connected. We only need to find a one-dimensional path connecting these two qudits and measure $`Z`$ for all the other qudits which are not on the path, which reduces the two or three dimensional problem to one dimension.

We now discuss the problem of physical implementation of our one-way quantum computer. Physically the qudit cluster state (18) can be created by Hamiltonian

$$H=\mathrm{}g\underset{(a,b)}{}N_a^{(z)}N_b^{(z)},(g>0)$$
(31)
where $`(a,b)`$ denotes sites $`a`$ and $`b`$ are nearest neighbors in the cluster; and $`N^{(z)}`$ is defined as

$$N^{(z)}=\underset{k=0}{\overset{d1}{}}|kkk|$$
(32)
Then we find the intertwining operator $`S`$ in Eq. (22) has the the explicit form

$$S=exp\left(\frac{i}{\mathrm{}}Ht_𝒞\right),$$
(33)
where the evolution time $`t_𝒞=\frac{2\pi }{dg}`$.

To associate with more familiar Hamitonian in physics, let us define the spin-$`\frac{(d1)}{2}`$ operator of $`z`$ direction

$$s_z=N^{(z)}\frac{d1}{2}.$$
(34)
Then we can rewrite Eq. (31) as

$$H=\frac{d1}{2}\mathrm{}g\underset{a}{}\nu _a(s_z)_a\mathrm{}g\underset{(a,b)}{}(s_z)_a(s_z)_b,$$
(35)
where $`\nu _a`$ is the number of nearest neighbors for qudit $`a`$ in the cluster. Obviously, the interaction Hamiltonian

$$H_I=\mathrm{}g\underset{(a,b)}{}(s_z)_a(s_z)_b,$$
(36)
which is the ferromagnetic Ising type interaction with spin-$`\frac{d1}{2}`$.

Those kinds of Ising model, other than the usual spin-$`1/2`$ Ising model, has been one of the most actively studied systems in condenced matter and statistical physics due to their rich variety of critical and multicritical phenomena. For example, the spin - $`1`$ Ising model with nearest- neighbor interactions and a single-ion potential is know as the Blume-Emery-Griffiths (BEG) model Blu , the spin - $`3/2`$ Ising model was introduced to explain phase transitions in $`DyVO4`$ and its phase diagrams were obtained within the mean-field approximation Siv . In addition, higher spin Ising models can be associated with the magnetic properties of artificially fabricated superlattices. Such lattices consist of two or more ferromagnetic materials have been widely studied over the years, because their physical properties differ dramatically from simple solids formed from the same materials. The development of film deposition techniques has aroused great interest in the synthesis and study of superlattices in other materials. A number of experimentalKwo ; Maj ; Kre ; Cam1  and theoretical worksIzm ; Mat ; Hin ; Qu ; Fis ; Gri1 ; Sy ; Sab1  have been devoted to those directions.

## IV Measurement based quantum computation with qudit

As discussed above, the qudit cluster states exhibit the same features in quantum entanglement as that for the qubit cluster states. Then a question arises naturally: Can these natures of quantum correlations be available for constructing the universal quantum computations? We will give an affirmative answer to this question in the following two sections.

In this section, we further generalize the basic concept of “single qudit quantum measurement” and the corresponding measurement based quantum computation (MBQC) on qubit clusters to that on qudit clusters. Along the line to construct MBQC for the qubit case, we will formulate the corresponding theorem which relates unitary transformation to quantum entanglement exhibited by the qudit cluster states. Quantum computations with qudit clusters inherit all basic concepts of those with qubit clusters. They include the basic procedure of simulation of any unitary gate, the concatenation of gate simulation and the method to deal with the random measurement results. Here we will give a $`d`$-dimensional parallel theorem as generalization of the central theorem $`1`$ in Ref. Rau1 .

Before formulating our central theorem, let us introduce the basic elements for quantum computing with qudit clusters. The main task of quantum computing with qudits is to simulate arbitrary quantum gate $`g`$ defined on $`n`$ qudits Hilbert space. For this purpose, the first step for quantum computing on qudit clusters is to find out a proper cluster $`𝒞(g)`$. Then we divide it into three sub-clusters: the input cluster $`𝒞_I(g)`$, the body cluster $`𝒞_M(g)`$, and the output cluster $`𝒞_O(g)`$. As usual we require that the input and output clusters have the same rank (i.e. the same number of qudits), $`|𝒞_I(g)|=|𝒞_O(g)|=n`$. Then we prepare the initial state in

$$|\mathrm{\Psi }(\mathrm{𝚒𝚗})_{𝒞(g)}=|\psi (\mathrm{𝚒𝚗})_{𝒞_{I(g)}}|+_{𝒞_{M(g)}𝒞_{O(g)}}.$$
(37)
In this first step of quantum computing, we entangle the qudits on the qudit cluster by using the cluster state generator $`S`$, i.e.,

$$|\mathrm{\Phi }(\mathrm{𝚒𝚗})_{𝒞(g)}=S|\mathrm{\Psi }(\mathrm{𝚒𝚗})_{𝒞(g)}.$$
(38)
This step brings the structure information of the qudit cluster into our computing process, and thus relates it with the corresponding qudit cluster state.

The second step is to measure all qudits on the cluster in special space-time dependent basis according to a given measurement pattern (MP). The definition of MP is given as follows.

###### Definition 1

A measurement pattern $`_𝒞`$ on a cluster $`𝒞`$ is a set of unitary matrixes

$$_𝒞=\left\{u_aZ_au_a^{}\right|a𝒞,u_aSU(d)\},$$
(39)
which determines the one-qudit measured operators $`N_a^{(u)}`$ on $`𝒞`$, with the explicit form

$$N_a^{(u)}=\underset{s=0}{\overset{d1}{}}u_a|s_as_as|u_{a}^{}{}_{}{}^{}.$$
(40)
If this measurement pattern $`_𝒞`$ operates on the initial state $`|\mathrm{\Phi }(\mathrm{𝚒𝚗})_{𝒞(g)}`$, the set of measurement outcomes

$$\{s\}_𝒞=\left\{s_aZ_d\right|a𝒞\}$$
(41)
is obtained. Then, modulo norm factor, the resulting state $`|\mathrm{\Psi }_{}_𝒞`$ is given by

$$|\mathrm{\Phi }__𝒞^{\{s\}}=P__𝒞^{\{s\}}|\mathrm{\Phi }(\mathrm{𝚒𝚗})_{𝒞(g)},$$
(42)
where the pure state projection

$$P__𝒞^{\{s\}}=\underset{k𝒞}{}u_k|s_k_ks|u_k^{}.$$
(43)
It is worthy pointing out that we always measure $`X`$ for the input qudits and $`Z`$ for the output, which is independent of gate $`g`$, i.e.,

$`_{𝒞_I(g)}`$ $`=`$ $`\{X_i,i𝒞_I(g)\},`$ (44)
$`_{𝒞_O(g)}`$ $`=`$ $`\{Z_i,i𝒞_O(g)\}.`$ (45)
Then we reach the final step, to associate the measurement values with the result of gate $`g`$ acting on the initial state.

From the above standard procedure of qudit clusters quantum computation, we learn that what is crucial for this scheme is to associate a given gate $`g`$ with a measurement pattern. Although by now we have no general optimal operational procedure to do this for practical problem, the following theorem provides a useful tool in realizing specific gates on the qudit clusters.

###### Theorem 2

Suppose that the state $`|\psi _{𝒞(g)}=P_{_{𝒞_M}(g)}^{\{s\}}|\varphi _{𝒞(g)}`$ obeys the $`2n`$ eigenvalue equations

$`X_{𝒞_I(g),i}\left(UX_iU^{}\right)_{𝒞_O(g)}|\psi _{𝒞(g)}`$ $`=`$ $`q_d^{\lambda _{x,i}}|\psi _{𝒞(g)}`$ (46)
$`Z_{}^{}{}_{𝒞_I(g),i}{}^{}\left(UZ_iU^{}\right)_{𝒞_O(g)}|\psi _{𝒞(g)}`$ $`=`$ $`q_d^{\lambda _{z,i}}|\psi _{𝒞(g)},`$ (47)
with $`\lambda _{x,i},\lambda _{z,i}Z_d`$ and $`1in`$. Then, according to the above standard quantum computing procedure, we have

$$P_{_{𝒞_I(g)}}^{\{s\}}P_{_{𝒞_M(g)}}^{\{s\}}|\mathrm{\Phi }(\mathrm{𝚒𝚗})_{𝒞(g)}(|s_i)_{𝒞_I(g)𝒞_M(g)}|\psi (\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)},$$
(48)
where the input and output state in the simulation of $`g`$ are related via

$$|\psi (\mathrm{𝚘𝚞𝚝})=UU_\mathrm{\Sigma }|\psi (\mathrm{𝚒𝚗}),$$
(49)
where $`U_\mathrm{\Sigma }`$ is a byproduct operator given by

$$U_\mathrm{\Sigma }=\underset{(𝒞_O(g)i)=1}{\overset{n}{}}(Z_i)^{\lambda _{x,i}s_i}(X_i)^{\lambda _{z,i}}.$$
(50)
Proof. Let us begin with the case when

$$|\psi (\mathrm{𝚒𝚗})_{𝒞_I(g)}=|\{t\}_{𝒞_I(g)},$$
(51)
with

$$\{t\}=\{t_1t_2\mathrm{}t_n\}.$$

To associate with $`|\psi _{𝒞(g)}`$, the initial input state is written as

$$|\psi (\mathrm{𝚒𝚗})_{𝒞_I(g)}=(\sqrt{d})^nP_{_{𝒞_I(g)}^{}}^{\{t\}}|+_{𝒞_I(g)},$$
(52)
where

$$_{𝒞_I(g)}^{}=\{Z_i,i𝒞_I(g)\}.$$
(53)
In terms of Eqs. (37, 38, 48, 52), we have

$$(|s_i)_{𝒞_I(g)𝒞_M(g)}|\psi (\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)}P_{_{𝒞_I(g)}}^{\{s\}}P_{_{𝒞_I(g)}^{}}^{\{t\}}|\psi _{𝒞(g)}.$$
(54)
To find out the equations for the final state $`|\psi (\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)}`$, we take $`P_{_{𝒞_I(g)}}^{\{s\}}P_{_{𝒞_I(g)}^{}}^{\{t\}}`$ acting on both sides of Eq. (46) and Eq. (47):

$$\left(UX_iU^{}\right)_{𝒞_O(g)}|\overline{\psi }(\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)}=q_d^{s_i\lambda _{x,i}}|\psi (\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)},$$
(55)
$$\left(UZ_iU^{}\right)_{𝒞_O(g)}|\psi (\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)}=q_d^{t_i\lambda _{z,i}}|\psi (\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)},$$
(56)
where the input state for $`|\overline{\psi }(\mathrm{𝚘𝚞𝚝})`$

$$|\overline{\psi }(\mathrm{𝚒𝚗})=X_i^{}|\{t\}.$$
(57)
Before drawing a conclusion, we need to check the final state is not a zero vector. In fact, from Eqs. (46) and (47), the state $`U^{}|\psi _{𝒞(g)}`$ is the simutaneous eigen-state of operators $`X_{𝒞_I(g),i}X_{𝒞_O(g),i}`$ and $`Z_{}^{}{}_{𝒞_I(g),i}{}^{}Z_{𝒞_O(g),i}`$. We can directly evaluate this state and find out that it has every components in $`Z`$-diagonal representation of the input part. Consequently the final state is indeed a nonzero vector. So from Eq. (55) and Eq. (56), we obtain

$$|\psi (\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)}=e^{i\eta (t)}UU_\mathrm{\Sigma }|\{t\}_{𝒞_O(g)}.$$
(58)
To further determine the relation between the output state and the input state, let us consider the other case when

$$|\psi ^{}(\mathrm{𝚒𝚗})_{𝒞_I(g)}=|+_{𝒞_I(g)}.$$
(59)
At this time, the final state

$$|\{s_i\}_{𝒞_I(g)𝒞_M(g)}|\psi ^{}(\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)}=P_{𝒞_I(g)}^{\{s\}}(X)|\psi _{𝒞(g)}.$$
(60)
Let $`P_{_{𝒞_I(g)}}^{\{s\}}`$ apply on both sides of Eq. (46) and Eq. (47), we obtain

$$\left(UX_iU^{}\right)_{𝒞_O(g)}|\psi ^{}(\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)}=q_d^{s_i\lambda _{x,i}}|\psi ^{}(\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)},$$
(61)
$$\left(UZ_iU^{}\right)_{𝒞_O(g)}|\overline{\psi ^{}}(\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)}=q_d^{\lambda _{z,i}}|\psi ^{}(\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)},$$
(62)
where the input state for $`|\overline{\psi ^{}}(\mathrm{𝚘𝚞𝚝})`$

$$|\overline{\psi ^{}}(\mathrm{𝚒𝚗})=Z_i^{}|+.$$
(63)
From the above equations, we obtain

$$|\psi ^{}(\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)}=e^{i\chi }UU_\mathrm{\Sigma }|+_{𝒞_O(g)}.$$
(64)
Substitute Eq. (58) into Eq. (64),

$$|\psi ^{}(\mathrm{𝚘𝚞𝚝})_{𝒞_O(g)}=UU_\mathrm{\Sigma }d^{\frac{n}{2}}\underset{\{t\}}{}e^{i\eta (t)}|\{t\}_{𝒞_O(g)}.$$
(65)
Comparing Eq. (64) to Eq. (65), we obtain

$$e^{i\eta (t)}=e^{i\chi }.$$
(66)
This completes the proof.$`\mathrm{}`$

This theorem tells us that, since the cluster states have remarkable quantum correlations, which has been discussed in Sec. II, they play an essential role in the realization of arbitrary unitary gates. More precisely, as long as one cluster can be used to process a unitary gate for the cluster state, it will work for arbitrary input states. Therefore, it is sufficient to check the conditions for the cluster states, i.e., Eq. (46) and Eq. (47). To be emphasized, the special features of the above theorem arising from qudits is that it is expressed not only in terms of unitary operators $`X`$ and $`Z`$ , but also in terms of their conjugates. For $`d=2`$, it exactly reduces to the Theorem $`1`$ of Ref. Rau1 .

Before using the theorem to construct a specific unitary gate, we need to explain how to deal with the byproduct part $`U_\mathrm{\Sigma }`$. The basic idea is to move $`U_\mathrm{\Sigma }`$ to the front of $`U`$ according to the commutation relations between $`U_\mathrm{\Sigma }`$ and $`U`$. To complete this operation, the general strategy is to divide measurements into several steps, in which the subsequent measurements depend on the results of previous measurements. In the next section, we will use specific examples to demonstrate how to construct all basic elementary gates with the help of this theorem.

## V Universality of qudit cluster quantum computation

It is well known that, for qubit quantum computing network, a finite collection of one qubit unitary operations and $`CNOT`$ gate is enough to construct any unitary transformation in the network. This conclusion has been shown to work well for qudit case Bry . More precisely, the collection of all one-qudit gates and any one imprimitive two-qudit gate is exactly universal for arbitrary quantum computing, where a primitive two-qudit gate is such a gate which maps all separate states to separate states. Therefore, in order to prove universality of quantum computation with qudit clusters, we only need to construct those basic element gates, and then to integrate them to realize arbitrary unitary gate. In this section, based on Theorem 2 in Sec. III, we will build certain qudit clusters to simulate the basic elementary gates, i.e., any one-qudit unitary operation and one imprimitive two-qudit unitary transformation.

### V.1 Realizations of single qudit unitary transformations

Let us start with single qudit gates. First, we introduce a proposition for any unitary transformation in $`d`$ dimensional Hilbert space.

###### Proposition 1

Let $`\{N_i,(iZ_{d^21})\}`$ be a Hermitian basis of the operator space for $`d`$ dimensional Hilbert space, then any unitary transformation $`U`$ has the form

$$U=q_{d}^{}{}_{}{}^{_i\alpha _iN_i}=\underset{i}{}q_{d}^{}{}_{}{}^{\beta _iN_i},$$
(67)
where $`\alpha _i`$ and $`\beta _i`$ are real numbers.

The first equality is obvious, and we refer to Ref. pur  for the proof of the second equality.

By the above proposition, we can divide any qudit gate into a product of more simple basic ones, i.e., single parameter unitary transformations. Now, we need to find $`d\times d`$ independent $`N_i`$ to simulate all unitary gates for one qudit. To use the definition of qudit cluster states, we expect that the single parameter unitary transformations must have deep relations with the basis elements of QPA. In fact, we find such a way to introduce $`d\times d`$ one parameter unitary transformations. This originates from that the fact that some of the basis elements of QPA can be used to define a state basis. We find that all the unitary transformations that do not change every basis state up to a phase are defined by the property of multi-values for complex functions. For example, for operator $`Z`$, we can define

$$Z^\beta (\{m\})=q_d^{\beta N(Z,\{m\})},(\beta ),$$
(68)
where

$$N(Z,\{m\})=\underset{n=0}{\overset{d1}{}}|n(n+m_nd)n|,(m_n𝒵).$$
(69)
Although the above definitions include infinity unitary transformations, there are only $`d`$ independent ones, which can be used to describe the following type of unitary transformations

$$U_Z(\{\alpha \})|n=q_d^{\alpha _n}|n,(nZ_d,\alpha ).$$
(70)
Obviously, these $`d`$ independent unitary transformations, also the corresponding $`N(Z,\{m\})`$, can take the place of $`\{Z^n,nd\}`$ in the unitary basis.

A similar argument can be generalized to $`\overline{Z}`$, which is defined in Sec. II. More precisely, for operator $`\overline{Z}`$, we define

$$\overline{Z}^\beta (\{m\})=q_d^{\beta N(\overline{Z},\{m\})},(\beta ),$$
(71)
where

$$N(\overline{Z},\{m\})=\underset{n=0}{\overset{d1}{}}|n(\overline{Z})(n+m_nd)n(\overline{Z})|,(m_n𝒵),$$
(72)
with

$$\overline{Z}|n(\overline{Z})=q_d^n|n(\overline{Z}).$$
(73)
In the following, we will show that we can select $`dd`$ independent Hermitian operators from $`N(\overline{Z},\{m\})`$.

When $`d`$ is a prime number, a convenient choice is to take $`\overline{Z}`$ from the operator set

$$\{Z,X,ZX,ZX^2,\mathrm{},ZX^{d1}\}.$$
(74)
Because each $`\overline{Z}`$ defines $`d1`$ independent $`N(\overline{Z},\{m\})`$ besides the identity, we obtain $`d^2(=(d1)(d+1)+1)`$ independent Hermitian operators.

When $`d`$ is not a prime number, we can choose the independent $`N(\overline{Z},\{m\})`$ by the following procedure. First, we take $`\overline{Z}`$ from $`\{Z,X,ZX\}`$, and we can obtain $`3(d1)`$ independent $`N(\overline{Z},\{m\})`$ besides the identity, which can take the place of the set of basis elements

$$S=\{Z^n,X^n,Z^nX^n,(nZ_d)\}.$$
(75)
Then we take an element $`\overline{Z}S`$, find out the elements in $`\{\overline{Z}^n,nZ_d\}`$ that is not in the set $`S`$, add these elements into $`S`$, and take the new independent $`N(\overline{Z},\{m\})`$, whose number is the number of new elements in set $`S`$. We repeat the above step until set $`S=B`$, then we obtain $`d^2`$ independent Hermitian operators.

Therefore if we can do all the above basic unitary transformations $`\overline{Z}^\beta (\{m\}`$, we will declare that we can do all single qudit unitary transformations. Here we adopt the following strategy: First, we realize $`Z^\alpha (\{m\}`$ on a five qudit cluster, as a basic single qudit transformation. To associate with all the other single qudit unitary transforamtion $`\overline{Z}_{\{m\}}^\alpha `$, we observe an useful fact

$$\overline{Z}^\alpha (\{m\})=UZ^\alpha (\{m\})U^{},$$
(76)
where $`U`$ (or $`U^{}`$) can be taken as an element in the Clifford group as defined in Sec. II. Based on this observation, we further discuss how to implement these elements in the Clifford group on clusters. Then we only need to connect these clusters in the given order to realized unitary gate $`\overline{Z}^\alpha (\{m\})`$. If we succeed to pass the above procedure, in principle we can make any single qudit unitary gate in $`SU(d)`$.

Now, let us realize these basic unitary transformations with a specifically-designed qudit cluster, which will be given as follows.

#### V.1.1  <br>Five qudit cluster realization of $`X^\alpha (\{m\})`$ and $`Z^\alpha (\{m\})`$

In this subsection, we aim to realize the basic single qudit unitary transformation $`Z^\alpha (\{m\})`$ on a five qudit cluster designed as in Fig. 1, which is a linear array of five qudits. By the way, we also use the same cluster to implement $`X^\alpha (\{m\})`$, which demonstrates that the same cluster with different measurement patterns can realize different unitary transformations.

The corresponding cluster state is defined by the following system of equations:

$`X_1^{}Z_2|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (77)
$`Z_1X_2^{}Z_3|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (78)
$`Z_2X_3^{}Z_4|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (79)
$`Z_3X_4^{}Z_5|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (80)
$`Z_4X_5^{}|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞.`$ (81)
It follows from Eqs. (77-81) that

$`X_1X_3^{}X_5|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (82)
$`Z_1^{}X_2X_4^{}Z_5|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞.`$ (83)
Form Eq. (81), we obtain

$$Z_4^\alpha (\{m\})X_5^\alpha (\{m\})|\varphi _𝒞=|\varphi _𝒞.$$
(84)
Here we emphasizes that when we obtain the above equation, we have used the following condition On $`\{m\}`$. If $`n_4+n_5=0(Mod(d))`$, then

$$n_4+m_{n_4}+n_5+m_{n_5}=0,(n_4,n_5Z_d).$$
(85)
From the above four equations, we have

$`X_1X_3^{}\left(X_5^\alpha \left(\{m\}\right)X_5X_5^\alpha \left(\{m\}\right)\right)|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (86)
$`Z_1^{}X_2\left(Z_4^\alpha (\{m\})X_4^{}Z_4^\alpha (\{m\})\right)\left(X_5^\alpha (\{m\})Z_5X_5^\alpha (\{m\})\right)|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞.`$ (87)
For a measurement pattern $`\{X_2,X_3^{},Z_4^\alpha (\{m\})X_4^{}Z_4^\alpha (\{m\})\}`$, Theorem 2 concludes that the simulated unitary transformation is $`X_5^\alpha (\{m\})U_\mathrm{\Sigma }`$, where

$$U_\mathrm{\Sigma }=Z_5^{s_1s_3}X_5^{s_2+s_4}.$$

Because $`U_\mathrm{\Sigma }`$ depends on the measurement results and can not be moved to the front of $`X_5^\alpha (\{m\})`$ trivially, different measurement results lead to different unitary transformations. In order to realize unique gate $`X_5^\alpha (\{m\})`$, we complete the measurement in two steps: In the first step, we measure $`\{X_1,X_2,X_3^{}\}`$. Then, when the obtained values are $`s_1`$ , $`\lambda _x(=s_3)`$ and $`s_2`$, the byproduct operator reads $`U_\mathrm{\Sigma }=Z^{s_3s_1}X^{\lambda _z}`$. At this time, $`\lambda _z`$ is still unknown since it depends on the measured result $`s_4`$. However, notice that $`Z_5^{s_3s_1}X_5^\alpha (\{m\})Z_5^{s_3+s_3}`$ is diagonal in the $`X`$ representation, we have

$$Z_5^{s_3s_1}X_5^\alpha (\{m\})Z_5^{s_3+s_1}=\underset{\{m\}}{}X_5^{\alpha _{\{m\}}^{s_1s_3}}(\{m\}).$$
(88)
From Eq. (88), we can obtain $`d`$ equations of $`\{\alpha _{\{m\}}^{s_1s_3}\}`$, which determine the values of $`\{\alpha _{\{m\}}^{s_1s_3}\}`$.

Now we make a new choice depending on the known measurement results. Also from Eqs. (77-81), we obtain the following equation instead of Eq. (87)

$`Z_1^{}X_2\left({\displaystyle \underset{\{m\}}{}}Z_4^{\alpha _{\{m\}}^{s_1s_3}}(\{m\})X_4^{}{\displaystyle \underset{\{m\}}{}}Z_4^{\alpha _{\{m\}}^{s_1s_3}}(\{m\})\right)`$
$`\left({\displaystyle \underset{\{m\}}{}}X_5^{\alpha _{\{m\}}^{s_1s_3}}(\{m\})Z_5{\displaystyle \underset{\{m\}}{}}X_5^{\alpha _{\{m\}}^{s_1s_3}}(\{m\})\right)|\varphi _𝒞=|\varphi _𝒞.`$ (89)
Measuring the fourth qudit in the base

$$\underset{\{m\}}{}Z_4^{\alpha _{\{m\}}^{s_1s_3}}(\{m\})X_4^{}\underset{\{m\}}{}Z_4^{\alpha _{\{m\}}^{s_1s_3}}(\{m\}),$$

we obtain the value $`s_4`$ and therefore $`\lambda _z=s_2+s_4`$. According to Theorem 2, we obtain the final operation

$$UU_\mathrm{\Sigma }=Z_5^{s_3s_1}X_5^{s_2+s_4}X_5^\alpha (\{m\}).$$
(90)
Finally, by measuring $`Z_5`$ we obtain the correct result

$$s=s_5+s_2+s_4.$$
(91)
The above equation does not mean that the final result depends only on the measurements to the second, fourth, and fifth qudit, because different values of $`s_1`$ and $`s_3`$ correspond to different measurement on the fourth qudit.

Based on the same cluster, we can also implement the single qudit rotation $`Z^\alpha (\{m\})`$. Similarly, we first measure $`\{X_1,X_2,x_4^{}\}`$; Then from Eqs. (77-81), we obtain

$`X_1\left({\displaystyle \underset{m}{}}Z_3^{\alpha _{\{m\}}^{s_2s_4}}(\{m\})X_3^{}{\displaystyle \underset{m}{}}Z_3^{\alpha _{\{m\}}^{s_2s_4}}(\{m\})\right)`$
$`\left({\displaystyle \underset{m}{}}Z_5^{\alpha _{\{m\}}^{s_2s_4}}(\{m\})X_5{\displaystyle \underset{m}{}}Z_5^{\alpha _{\{m\}}^{s_2s_4}}(\{m\})\right)|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (92)
$`Z_1^{}X_2X_4^{}Z_5|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞.`$ (93)
where $`\{\alpha _{\{m\}}^{s_2s_4}\}`$ is determined by

$$X_5^{s_2+s_4}Z_5^\alpha (\{m\})X_5^{s_2s_4}=\underset{\{m\}}{}Z_5^{\alpha _{\{m\}}^{s_2s_4}}(\{m\}).$$
(94)
At the same time we make another measurement on

$$\underset{m}{}Z_3^{\alpha _{\{m\}}^{s_2s_4}}(\{m\})X_3^{}\underset{m}{}Z_3^{\alpha _{\{m\}}^{s_2s_4}}(\{m\}).$$

According to theorem 2, we conclude that the simulated unitary transformation indeed is

$$Z^{s_3s_1}X^{s_2+s_4}Z_5^\alpha (\{m\}).$$

The correct result and the measurement values are also related by Eq. (91).

#### V.1.2 Realizations of single qudit elements in Clifford group

As implied in Eq. (76), we only need to realize the single qudit elements in the Clifford group. It is easy to show that not all elements in the Clifford group are required. In fact, we only need do the elements defined as

$$U^{mn}ZU_{}^{mn}{}_{}{}^{}=\overline{Z},$$
(95)
where

$$\overline{Z}=q_d^{\frac{d1}{2}mn}Z^mX^n,$$
(96)
with

$$(m,n)=1.$$
(97)
We will show that we can do all the above Clifford unitary transformations through a series of four basic types of unitary transformations. The first is defined as

$`U^{1n}ZU_{}^{1n}{}_{}{}^{}`$ $`=`$ $`q_d^{\frac{d1}{2}n}ZX^n,`$ (98)
$`U^{1n}XU_{}^{1n}{}_{}{}^{}`$ $`=`$ $`X;`$ (99)
The second is defined as

$`U^{n1}ZU_{}^{n1}{}_{}{}^{}`$ $`=`$ $`q_d^{\frac{d1}{2}n}Z^nX,`$ (100)
$`U^{n1}XU_{}^{n1}{}_{}{}^{}`$ $`=`$ $`Z^{};`$ (101)
The third is defined as

$`VZV^{}`$ $`=`$ $`q_d^{\frac{d1}{2}}ZX,`$ (102)
$`VXV^{}`$ $`=`$ $`X;`$ (103)
The last is defined as

$`WZW^{}`$ $`=`$ $`Z,`$ (104)
$`WXW^{}`$ $`=`$ $`q_d^{\frac{d1}{2}}ZX.`$ (105)
###### Theorem 3

For any unitary transformation $`U^{mn}`$ partially defined by Eq. (95), it can be factorized into a product of a series of the above four basic unitary transformations.

Proof. Let us prove it by induction. We denote $`N_d\{1,2,\mathrm{},d\}`$. When $`m=1`$ or $`n=1`$, it is the first or the second types of unitary transformations. Let us suppose the above theorem is valid at $`mN_d`$ or $`nN_d`$, i.e., we can do

$$U^{mn}(m\text{or}nN_d,(m,n)=1).$$
(106)
For arbitrary positive integer $`n`$ that is relatively prime to $`d+1`$, there exists

$$n=i(d+1)+n^{},(iZ_{\mathrm{}},n^{}N_d).$$
(107)
Obviously,

$$n^{}N_d,(d+1,n^{})=1.$$
(108)
According to the assumption, we can do $`U^{(d+1)n^{}}`$. Then let $`V`$ operate $`i`$ times,

$$V^iU^{(d+1)n^{}}V_{}^{}{}_{}{}^{i}=U^{(d+1)n}.$$
(109)
According to the assumption, we can also do $`U^{n^{}(d+1)}`$. Then let $`W`$ operate $`i`$ times,

$$W^iU^{n^{}(d+1)}W_{}^{}{}_{}{}^{i}=U^{n(d+1)}.$$
(110)
Therefore the theorem is valid for $`m\text{or}nN_{d+1}`$. This completes the proof. $`\mathrm{}`$

Now we come to constructing the four basic unitary transformations. We will prove that the first (including the third) and the fourth can be realized on the five qudit cluster as Fig. 1. According to Eqs. (77-81), we have

$`X_1X_3^{}X_5|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (111)
$`Z_1^{}X_2(Z_{4}^{}{}_{}{}^{n}X_4)^{}Z_5X_{5}^{}{}_{}{}^{n}|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞.`$ (112)
According to theorem 2, when the measurement pattern is $`\{X_2,X_3^{},(q_{d}^{}{}_{}{}^{\frac{d1}{2}n}Z_{4}^{}{}_{}{}^{n}X_4)^{}\}`$, the corresponding unitary transformation is

$$q_{d}^{}{}_{}{}^{\frac{d1}{2}(s_1+s_3)n}Z^{s_1s_3}X^{s_2+s_4n(s_1+s_3)}U^{1n}.$$
(113)
Also from Eqs. (77-81), we obtain

$`X_1Z_3X_3^{}X_4^{}Z_5X_5|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (114)
$`Z_1^{}X_2X_4^{}Z_5|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞.`$ (115)
According to theorem 2, when the measurement pattern is $`\{X_2,q_{d}^{}{}_{}{}^{\frac{d1}{2}n}Z_3X_3^{},X_4^{}\}`$, the corresponding unitary transformation is

$$q_{d}^{}{}_{}{}^{\frac{d1}{2}(s_2+s_4)}Z^{s_2s_1s_3}X^{s_2+s_4}W.$$
(116)
To realize the unitary transformation $`U^{n1}`$, we need a cluster composed of six qudits as Fig. 2.

The cluster state is defined by the following system of equations

$`X_1^{}Z_2|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (117)
$`Z_1X_2^{}Z_3|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (118)
$`Z_2X_3^{}Z_4|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (119)
$`Z_3X_4^{}Z_5|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (120)
$`Z_4X_5^{}Z_6|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (121)
$`Z_5X_6^{}|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞.`$ (122)
It follows from the above equations that

$`X_1X_3^{}X_5Z_6^{}|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (123)
$`Z_1^{}X_2Z_{4}^{}{}_{}{}^{n}X_4^{}X_{5}^{}{}_{}{}^{n}Z_{6}^{}{}_{}{}^{n}X_6|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞.`$ (124)
When the measurement pattern is $`\{X_2,X_3^{},q_{d}^{}{}_{}{}^{\frac{d1}{2}n}Z_{4}^{}{}_{}{}^{n}X_4^{},X_5\}`$, the corresponding unitary transformation is

$$q_{d}^{}{}_{}{}^{(s_1+s_3)(s_2+s_4ns_5+\frac{d1}{2}n)}Z^{n(s_5s_1s_3)s_2s_4}X^{s_1s_3}U^{n1}.$$
(125)
### V.2  <br>Realization of an imprimitive two qudit gate

Now we come to the construction for simulating two qudit operations.

The cluster composed of six qudits as Fig. 3 is considered with the following system of equations

$`X_1^{}Z_3|\varphi _C`$ $`=`$ $`|\varphi _𝒞,`$ (126)
$`X_2^{}Z_4|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (127)
$`Z_1X_3^{}Z_4Z_5|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (128)
$`Z_2Z_3X_4^{}Z_6|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (129)
$`Z_3X_5^{}|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (130)
$`Z_4X_6^{}|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞.`$ (131)
It follows from the above equations that

$`X_1X_5^{}|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (132)
$`X_2X_6^{}|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (133)
$`Z_1^{}X_3Z_5^{}X_6^{}|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞,`$ (134)
$`Z_2^{}X_4Z_6^{}X_5^{}|\varphi _𝒞`$ $`=`$ $`|\varphi _𝒞.`$ (135)
By measuring the system according to the measurement pattern $`\{X_1X_2X_3X_4Z_5Z_6\}`$, the simulated two qudit gate $`T`$ satisfies, and is also defined by

$`TX_5T^{}`$ $`=`$ $`X_5^{},`$ (136)
$`TX_6T^{}`$ $`=`$ $`X_6^{},`$ (137)
$`TZ_5T^{}`$ $`=`$ $`Z_5^{}X_6^{},`$ (138)
$`TZ_6T^{}`$ $`=`$ $`Z_6^{}X_5^{}.`$ (139)
According to Theorem 2, the above measurement pattern realize the following unitary gate

$$TZ_5^{s_1}X_5^{s_3}Z_6^{s_2}X_6^{s_4}=q_{d}^{}{}_{}{}^{s_1s_2}Z_5^{s_1}X_5^{s_2s_3}Z_6^{s_2}X_6^{s_1s_4}T.$$
(140)
The next task is to prove that $`T`$ is an imprimitive two qudit operation. Ref. Bry  tells us that a two gate $`V`$ is primitive if and only if $`V=S_1S_2`$ or $`V=(S_1S_2)P`$. Here, $`S_1`$ and $`S_2`$ are different single qudit operators, $`P`$ is the interchanging operator obeying $`P|x|y=|y|x`$. Based on this fact, we can easily conclude that a primitive operator always maps a single qudit operator to another single qudit operator. Obviously, the above two qudit operator $`T`$ is imprimitive. Another way to prove it is to evaluate the unitary transformation directly. Then we can find that it maps all $`ZZ`$ bases to the maximum entangle states.

As demonstrated in this section, any single qudit unitary gate and one imprimitive two qudit gate can be realized on qudit clusters. Therefore, the measurement based quantum computing on qudit clusters is universal.

## VI Conclusions

We have introduced the concept of qudit cluster state in terms of finite dimensional representations of QPA. Based on these qudit cluster states, we have built all the elements of qudit clusters needed for implementation of universal measurement-based quantum computations. With generalizations of cluster states and measurement patterns, most of the results in qubit cluster can work well for qudit clusters in parallel ways. We also show that there still exists the celebrated theorem guaranteeing the availability of qudit cluster states to quantum computations. To prove the universality of this quantum computation, we show that we can implement all single qudit unitary transformations and one imprimitive two qudit gate on specific qudit clusters. In addition, we propose to build a one-way universal quantum computer with qudit cluster states practically since the high dimensional “Ising”model can be used to generate such cluster state dynamically.

###### Acknowledgements.

The authors would like to thank Prof. X. F. Liu for useful discussions. The work of D. L. Z is partially supported by the National Science Foundation of China (CNSF) grant No. 10205022. The work of Z. X is supported by CNSF (Grant No. 90103004, 10247002). The work of C. P. S is supported by the CNSF( grant No. 10205021)and the knowledged Innovation Program (KIP) of the Chinese Academy of Science. It is also funded by the National Fundamental Research Program of China with No 001GB309310.