数理解析研究所講究録
第 1658 巻 2009 年 112-123

112

Quantum algorithm for SAT problem withentangled degree
Satoshi Iriyama and Masanori Ohya
Tokyo University of Science
Abstract
There are some quantum algorithms to solve SAT problem. Ohya,
Masuda and Volovich showed the quantum algorithm with chaos amplifier
solving it in polynomial time. Ohya and Accardi proposed the quantum
algorithm using a stochastic limit.
In this paper, we show a new approach by using an entangled degree. We calculate it with the merginal states of the result state to check
whether the SAT condition is held or not.

1

Introduction

Ohya, Masuda and Volovich proposed a quantum algorithm with chaos amplifierfor SAT problem[l, 2]. The computational complexity of it is in polynomial of
input data[7]. The part of calculation of objective function is written as a
product of unitary operators and there are no Black boxes, so called Oracles.
Since the probability to obtain the correct result is very small in some cases, weapply a chaos amplifier to make it larger than 1/2. The whole process of thequantum algorithm can be written in the form of generalized quantum Turingmachine which is a mathematical model of quantum computation defined in thepaper[8].
In this paper, we propose the new quantum algorithm which calculates anentangled degree of the result state in order to check that it holds the conditionsof problem. Entanglement is the one of properties of quantum state that theclassical state does not have. To calculate an entangled degree, we can reducethe computational complexity of quantum algorithm. We show the examples ofDeutch-Jozsa problem and SAT problem.

2

Outline of Quantum Algorithm

We first explain the usual quantum algorithm that is represented by unitary
operators. The computational complexity of them is defined by the number offundamental quantum gates in it, introduced below.

113

For the mathematical expression of problem, we construct the quantum algorithm for it following these steps.

1. Define the Hilbert space for computation.
2. Construct the initial state.

3. Construct the unitary operators to solve the problem.
4. Apply it for the initial density operator and obtain the result.

5. Measure the observable with the result state.
In the first step, we define the Hilbert space by the instance of the problem. This Hilbert space should be qubit space for correspondence to digitalcomputation that uses classical bits. Let
be a Hilbert space spanned$\mathcal{H}=\mathbb{C}^{2}$

by$|0\rangle=(\begin{array}{l}l0\end{array})$and$|1\rangle=(\begin{array}{l}01\end{array})$, a normalized vector$|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$on$\mathcal{H}$is called a qubit.
One can apply Hadamard transformation defined by$H= \frac{1}{\sqrt{2}}(\begin{array}{ll}1 1l -l\end{array})$

to create a superposition. For$|0\rangle$

and$|1\rangle$, it works as$H|0 \rangle=\frac{1}{\sqrt{2}}|0\rangle+\frac{1}{\sqrt{2}}|1\rangle$.

$H|1 \rangle=\frac{1}{\sqrt{2}}|0\rangle-\frac{1}{\sqrt{2}}|1\rangle$

Here we introduce logical gates on qubit space, which are NOT gate, C-NOT
gate and CC-NOT gate. We call these gates fundamental gates. We can also
construct AND and OR gate by considering the product of fundamental gatesand some imprementations. NOT gate $U_{NOT}$ is defined on one qubit Hilbert
space as$U_{NOT}=|1\rangle\langle 0|+|0\rangle\langle 1|$.

C-NOT $U_{CN}$ gate and CC-NOT $U_{CCN}$ are given on two and three qubit Hilbert
space as$U_{CN}=|0\rangle\langle 0|\otimes I+|1\rangle\langle 1|\otimes U_{NOT}$,$U_{CCN}=|0\rangle\langle 0|\otimes I\otimes I+|1\rangle\langle 1|\otimes|0\rangle\langle 0|\otimes I+|1\rangle\langle 1|\otimes|1\rangle\langle 1|\otimes U_{NOT}$

respectively. The unitary operator to solve the problem is constructed by thesefundamental gates.

114

SAT problem

3

The followings are discussed more precisely in the papers[l, 2, 4, 7]. Let
be a set of literals and $t:Xarrow\{0,1\}$ a truth$t(x)=1-t(\overline{x})$. Let $F(X)$ ne all subsets of literals and an
assignment holding
element of it is called a clause. Let $C=\{C_{1}, \cdots, C_{m}|C_{k}\in F(X)\}$ be a set ofclauses.
[Problem(SAT problem)] Are there any truth assignments to make $f(C)=1$(satisffiable) ?
$X=\{x_{1}, \cdots, x_{n},\overline{x}_{1}, \cdots,\overline{x}_{n}\}$$f(C) \equiv\bigwedge_{i=1}^{m}_{x_{j}\in C_{i}}t(x_{j})$SAT problem is one of NP-complete problems. In [4] we discussed the quantum algorithm of the SAT problem. In [1, 2] it is shown that the chaotic quantum
algorithm can solve the SAT problem in polynomial time.

4

OMV SAT algorithm

The computational basis of this algorithm is on the Hilbert space
where is a number of dust qubits. Let$\mathcal{H}=(\mathbb{C}^{2})^{\otimes n+\mu+1}$$\mu$$|v_{in}\rangle\equiv|0^{n},$$0^{\mu},$$0\rangle$

be an initial state vector. A unitary operator$(i=1, \cdots , 2^{n-1})$ as follows
truth assignment$U_{C}$:$\mathcal{H}arrow \mathcal{H}$computes $t(C)$ for$e_{\iota}$$U_{C}|v_{in}\rangle=U_{C}|0^{n},$$0^{\mu},$$0\rangle$$= \frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{2^{n}-1}|e_{i},$ $d^{\mu},$$t(C)\rangle$$\equiv|v_{out}\rangle$

where$|d^{\mu}\rangle$

is dust qubits denoted by

Theorem 1 $[7J$ The number

$\mu$

$\mu$

strings of binary symbols.

of dust qubits for algorithm of SAT problem is$\mu\leq 2nm$

Theorem 2 $[7JFor$ a set of clauses $C=\{C_{1}\ldots., C_{m}\}$ , we can construct theunitary operator $Uc$ to calculate the truth value of as$C$$U_{C} \equiv\prod_{i=1}^{m-1}U_{AND}(i)\prod_{j=1}^{m}$

UOR $(j)H(n)$where$H(k)=(H\cdot I)^{\otimes k}I^{\otimes N-k}$

115

and $U_{OR}$ is constructed by the product of fundamental gates. We
prove this by calculating the indices of qubit and the information of clauses.
The computational complexity of quantum computation depends on thenumber of unitary operator in the quantum circuit. Let $U$ be the unitary operator, it is written as$U_{AND}$$U=U_{n}U_{n-1}\cdots U_{1}$whereare fundamental gates. The computational complexity $T(U)$is considered as .
We need to combine some fundamental gates such as $U_{NOT},$ $U_{C-N}$ and$U_{C-C-N}$ to construct the quantum circuit in fact.
$U_{AND}$ and $U_{OR}$ can be
written as a combination of fundamental gates. Here we obtain the computational complexity of SAT algorithm by the number of $U_{NOT},$ $U_{AND}$ and $U_{OR}$ .
$U_{n},$$\cdots,$$U_{1}$$n$

Theorem 3 For a set of clauses $C=\{C_{1}, \ldots , C_{m}\}$ and literal$T(U_{C})$$X=\{x_{1}, \ldots, x_{n},\overline{x}_{1_{!}}\ldots,\overline{x}_{n}\}$is$T(U_{C})=m-1+ \sum_{k-1}^{m}(|C_{k}|+2i_{k}’-1)$$\leq 4mn-1$

4.1

Chaos Amplffier

Here we briefly review how chaos can play a constructive role in computation(see [1, 2] for the details).
Consider the so called logistic map which is given by the equation$x_{n+1}=ax_{n}(1-x_{n})\equiv g_{a}(x)$,$x_{n}\in[0,1]$.

The properties of the map depend on the parameter . If we take, for example,$a=3.71$ , then the Lyapunov exponent is positive, the trajectory is very sensitive
to the initial value and one has the chaotic behavior [2]. It is important to noticethat if the initial value $x_{0}=0$ , then $x_{n}=0$ for all .
The stateof the previous subsection is transformed into the density
matrix of the form
$a$

$n$

$|\psi\rangle$$\overline{\rho}=q^{2}P_{1}+(1-q^{2})P_{0}$. One has toandandare projectors to the state vectors
where
and
generate an Abelian algebra which can be considered as
notice that
following theorems is proven in [1, 2, 3].
system.
The
classicala$P_{0}$$P_{1}$$|0\rangle$$|1\rangle$$P_{1}$$P_{0}$

Theorem 4 For the logistic map $x_{n+1}=ax_{n}(1-x_{n})$ with $a\in[0.4]$ and$[0,1]$ , letbeand a set be $\{0.1,2, \ldots , n\ldots. , 2n\}$ . If is 3.71. then there.
integerin satisfying
anentsts$x_{0}\in$$x_{0}$$J$$\frac{1}{2^{n}}$

$k$

$J$

Theorem 5 Let and, thensuch that$a$$x_{k}> \frac{1}{2}$$a$$x_{k}> \frac{1}{2}$$n$be the same in above theorem.

$k> \frac{\mathfrak{n}-1}{\log_{2}3.71-1}$.

If there exists$k$in $J$.

116

Corollary 6 Let $|t(C)|$ be the cardinality of these assignments, if, then there vtsts
in such that
$r=|t(C)|$ and there exists
the following inequality if is SAT.

withsatisfying$x_{0} \equiv\frac{r}{2^{n}}$

$k$

$J$

$x_{k}> \frac{1}{2}$

$e$

$k$

$C$

$[ \frac{n-1-\log_{2}r}{\log_{2}3.71-1}]\leq k\leq[\frac{5}{4}(n-1)]$.

From these theorems, for all , it holds$k$$Af_{k}\{\begin{array}{ll}=0 iff C is not SAT>0 iff C is SAT\end{array}$where $AI_{k}=g_{a}^{k}(q^{2})$ .
OMV SAT algorithm is represented in the form of generalized quantum
Turing machine(GQTM) and the computational complexity is discussed in [2,4, 8, 9].

Computational complexity of OMV SAT algorithm

5

be a computational complexity ofLetproven in [7].
$T(\Lambda)$$\Lambda$. The following theorems are

Theorem 7 Let $X’=X\cup\overline{X}=\{x_{1}, \cdots x_{n},\overline{x}_{1}, \cdots,\overline{x}_{n}\}$ be literals and $C=$
is$\{C_{1}, \cdots , C_{m}\}$ a setof literals, the computational complestty$T(\Lambda_{C})$$T( \Lambda_{C})=3\sum_{k=1}^{m}$(card $(C_{k})-1$ )$+ \sum_{\iota--1}^{m}2$card $(C_{k}\cap\{\overline{x}_{1}, \ldots , \vec{x}_{n}\})+m-1+n$$\leq(8mn-2m-1)$

Theorem 8 For a set of clauses and Boolean variables, the computational
complexity of the $oMV$ SAT algorithm including the chaos amplifier, $T(\Lambda_{SAT})$is obtained as follows
$C$

$n$

$T(\Lambda_{SAT})=T(\Lambda_{C})+T(\Lambda_{T})+T(\Lambda_{CA}^{k})=\mathcal{O}$where poly $(n)$ denotes a polynomial of

6$n$(poly $(n)$ ),.

Entanglement degree

It is important to measure the degree of entanglement of entangled states. Thereexist several such measures, for most of such measures it is difficult to compute.
Thus Belavkin and Ohya introduced another measure called the degree of entanglement $D_{EN}[5]$ .
Let be the entangled state with the marginal states and .
$\theta$$\rho$$\sigma$117

Definition 9 The degree of entanglement is defined by$D_{EN}( \theta;\rho, \sigma)\equiv\frac{1}{2}(S(\rho)+S(\sigma)-I_{\theta}(\rho, \sigma))$where $S(\rho)=-tr\rho\log\rho$ and$I_{\theta}(\rho, \sigma)\equiv tr\theta(\log\theta-\log\rho\otimes\sigma)$

Definition 10 A state$\theta_{1}$has stronger entanglement than$\theta_{2}$iff$D_{EN}(\theta_{1};\rho, \sigma)<D_{EN}(\theta_{2};\rho.\sigma)$

Theorem 11 For a pure state
1.

$\theta$2.

$\theta$7
Let$\theta$with the marginal state$\rho$

and$\sigma$,is separable iff $D_{EN}(\theta;\rho, \sigma)=0$

is entangled iff $D_{EN}(\theta;\rho, \sigma)<0$

Quantum algorithm with entangled degree solving SAT problem
be a number of literals in SAT problem, a number of qubits to computea Hilbert space to solve SAT problem.
We prepare an initialstate as
$n$

$\mu$

$f(C)$ , and $\mathcal{H}=(\mathbb{C})^{\otimes n+\mu+1}$$|\psi_{0}\rangle\in \mathcal{H}$$|\psi_{0}\rangle=|0_{t}^{n}0^{\mu},$

Applying the unitary operator
ments, we have the final state as$U_{C}$$0\rangle$

which computes $f(C)$ for all truth assign-$U_{C}| \psi_{0}\rangle=\frac{1}{\sqrt{2^{n}}}\sum_{t=0}^{2^{n}arrow 1}|e_{i},x_{i},$ $f_{e_{i}}(C)\rangle$$=|\psi_{f}\rangle$

whereis a value of $f(C)$ for a truth assignment , andthat is used for the computation of it.
If is SAT, there exists the truth assignment such that$f_{e_{i}}(C)$$e_{i}$$C$$x_{e_{i}}$is the qubits$e$$f_{e}(C)=1$

Let be a number of truth assignments making $f_{e}(C)=1$ . Here, we consider
the following density operator$r$$\sigma_{f}=|\psi_{f}\rangle\langle\psi_{f}|$This is a pure state on the Hilbert space$\mathcal{H}=(\mathbb{C})^{\otimes n+\mu+1}$$=\mathcal{K}_{1}\otimes \mathcal{K}_{2}$

118

where

$\mathcal{K}_{1}$and$\mathcal{K}_{2}$are two Hilbert spaces whose dimensions are$\dim \mathcal{K}_{1}=2^{\mu+\mu}$$\dim \mathcal{K}_{2}=2$

We define two marginal states ofas$\sigma_{f}$$\rho_{1}=tr_{\mathcal{K}_{2}}\sigma_{f}$$\rho_{2}=$tr$\mathcal{K}_{1}\sigma_{f}$with these marginal
Then we compute Entanglement Degree
is a pure state, it becomesstates. Since the final state$D_{EN}(\rho;\rho_{1}, \rho_{2})$$\sigma_{f}$$D_{EN}( \rho;\rho_{1}, \rho_{2})=-\frac{1}{2}(S(\rho_{1})+S(\rho_{2}))$$=S(\rho_{1})=S(\rho_{2})$Here, we exclude the dust qubits and we obtain$\rho_{1}=(\begin{array}{ll}A_{r} 00 A_{2^{n}-r}\end{array})$$\rho_{2}=(\begin{array}{ll}\frac{2^{n}-r}{2^{n}} 0O \frac{r}{2^{n}}\end{array})$where$A_{x}\in M(x)=(a_{i,j})$$a_{i,j}= \frac{1}{2^{n}}$$\rho_{1}$is decomposed as$\rho_{1}=\frac{1}{2^{n}}\sum_{0\leq i.j<r}|e_{i}\rangle\langle e_{j}|+\frac{1}{2^{n}}\sum_{r\leq k,l<2^{n}}|e_{k}\rangle\langle e_{l}|$$= \frac{r}{2^{n}}|\varphi_{r}\rangle\langle\varphi_{r}|+\frac{2^{n}-r}{2^{n}}|\varphi_{2^{1}-r}\rangle\langle\varphi_{2^{ll}-r}|$where$| \varphi_{r}\rangle=\frac{1}{\sqrt{r}}\sum_{0\leq i<r}|e_{i}\rangle$$| \varphi_{2^{n}-r}\rangle=\frac{1}{\sqrt{2^{n}-r}}\sum_{r\leq k<2^{n}}|e_{k}\rangle$

Then we calculate$S(\rho_{1})$and$S(\rho 2\grave{)}$as$S( \rho_{1})=S(\rho_{2})=-\frac{2^{n}-r}{2^{n}}\log\frac{2^{n}-r}{2^{n}}-\frac{r}{2^{n}}\log\frac{r}{2^{n}}$119

We obtain$D_{EN}(\rho;\rho_{1}, \rho_{2})\{\begin{array}{l}=0 r=0<0 0<r<2^{n}=0 r=2^{n}\end{array}$In the cases of $r=0$ and $r=2^{n},$is equal to , this meansthat the final state is a separable state. In fact, one can see$D_{EN}(\rho;\rho_{1}, \rho_{2})$$0$$\sigma_{f}=\{\begin{array}{l}|\eta\rangle\langle\eta|\otimes|0\rangle\langle 0| r=0|\eta\rangle\langle\eta|\otimes|1\rangle\langle 1| r=2^{n}\end{array}$where$| \eta\rangle=\frac{1}{\sqrt{2^{n}}}\sum_{i=0}^{2^{n}-1}|e_{i}\rangle$

If $D_{EN}(\rho;\rho_{1_{i}}\rho_{2})<0$ , we can say that is SAT immediately.
Moreover, even if $D_{EN}(\rho;\rho_{1}, \rho_{2})=0$ , we can check satisfiability easily by
the following algorithm:
1. Compute for one truth assignment $(e.g. x_{1}=0, x_{2}=0, \cdots, x_{n}=0)$

2. If $f(C)=0$ then$C$

is not SAT

3. If $f(C)=1$ then$C$

is SAT

In the case of $D_{EN}(\rho;\rho_{1}, \rho_{2})=0$ , there are only two possibilities that are$r=0$ or $r=2^{n}$ . Hence, we can check satisfiability by computing $f(C)$ for one
assignment. Therefore, we can represent the flow of quantum algorithm as thefollowing:

1. Define the Hilbert space for computation.

2. Construct the initial state and define its marginal states.

3. Construct the unitary operators to solve the problem.
4. Apply it for the initial density operator and obtain the result.

5. Calculate an entanglement degree with the marginal states of
the result state.

7.1

Example(D-J problem)

In this section we show the quantum algorithm with entangled degree for DeutchJozsa problem.
Let $N$ be a positive integer, $h:\{0, \cdots, 2N-1\}arrow\{0,1\}$ a function holding
one of the following conditions:

A card $\{x|h(x)=0\}=0$ or card $\{x|h(x)=1\}=0$ ( $h(x)$ is a constant)$B$

card $\{x|h(x)=0\}=card\{x|h(x)=1\}$ ($h$is a balanced function)

120[problem] Decide which condition holds.
is also given by a unitary operator
explained below. A quantum algorithm of this problem is described the following unitary operators $U_{h}WU_{h}$ on
the Hilbert space
$h$

$h$

$U_{h}$$(\mathbb{C}^{2})^{\otimes 1+[\log 2N]}$$U_{h}|x,$ $y\rangle=|x,$ $y+h(x)mod 2\rangle$$W|x,$ $y\rangle=(-1)^{y}|x,$$y\rangle$

For an initial state vector$| \psi_{in}\rangle=\frac{1}{\sqrt{2N}}\sum_{x=0}^{2N-1}|x,$$0)$apply $U_{h}WU_{h}$ . Then we have$U_{h}WU_{h}| \psi_{in})=U_{h}W\frac{1}{\sqrt{2N}}\sum_{x=0}^{2N-1}|x,$ $h(x)\rangle$$=U_{h} \frac{1}{\sqrt{2N}}\sum_{x=0}^{2N-1}(-1)^{h(x)}|x,$$= \frac{1}{\sqrt{2N}}\sum_{x=0}^{2N-1}(-1)^{h(x)}|x,$$h(x)\rangle$$0\rangle$$\equiv|\psi_{out}\rangle$

Therefore, we measure the observable $M$ with$|\psi_{out}\rangle$:$Af=\langle\psi_{out}|P|\psi_{out}\rangle$$= \frac{1}{2N}|\sum_{x=0}^{2N-1}(-1)^{h(x)}|^{2}$

where
:

$P=|\psi_{in}\rangle\langle\psi_{in}|$. According the result of this measurement, we can judge
holds A
$M=0\Leftrightarrow h$holds$M=1\Leftrightarrow h$$B$Here, we rewrite this algorithm by our new quantum algorithm as

1. Apply$U_{h}$

to the initial state.

2. Compute $D_{EN}$ of the result of (1) with certain marginal states.

3. Judge the character of$h$by the information of (2)121Applying$U_{h}$

to the initial state, we have$U_{h}| \psi_{in}\rangle=\frac{1}{\sqrt{2N}}\sum_{x=0}^{2N-1}|x,$ $h(x)\rangle$$=|\psi_{out}’\rangle$$(\neq|\psi_{out}\rangle)$

Here we define two Hilbert spaces$\mathcal{K}_{1}=(\mathbb{C}^{2})^{\otimes[1og2N]}$$\mathcal{K}_{2}=\mathbb{C}^{2}$and two marginal states$\rho_{1}=tr_{\mathcal{K}_{2}}|\psi_{out}’\rangle\langle\psi_{out}’|$$\rho_{2}=tr_{\mathcal{K}_{1}}|\psi_{out}’\rangle\langle\psi_{out}’|$After the calculation of $D_{EN}$$(|\psi_{out}’\rangle\langle\psi_{out}’| ; \rho_{1}, \rho_{2})_{t}$we obtain$D_{EN}(|\psi_{out}’\rangle\langle\psi_{out}’|;\rho_{1}, \rho_{2})\{\begin{array}{l}=0 h holds A<0 h holds B\end{array}$

If

$h$

holds

$A$

, then$|\psi_{out}’\rangle\langle\psi_{out}’|$$|\psi_{out}’\rangle$

is separable state on$= \frac{1}{\sqrt{2N}}\sum_{x=0}^{2N-1}|x,$$0$

or 1 for all$\mathcal{K}_{1}\otimes \mathcal{K}_{2}$$x\rangle$. In fact,.

Therefore, the computational complexities of above algorithms become as
the following table:

where $T(U)$ is a computational complexity of unitary operator $U,$ $T(M)$ is ofmeasurement $M$ , and $T(D_{EN})$ is of calculation of $D_{EN}$ .

8Conclusion

We found the third quantum algorithm to solve SAT problem:

1. OMV SAT algorithm: Unitary operations and amplification processes(e.g. chaos amplifier).
2. GQTM : Transition function and transition channels.
complexity of quantum algorithm.

$arrow$

computational

122

3. Quantum circuit and calculation of entanglement degree.
The computational complexity$T_{S_{-}4T}$$T_{SAT}=\mathcal{O}$of OMV SAT algorithm is(poly $(n)$ )with halting probability$p= \frac{1}{2}$

However, the computational complexity of the new quantum algorithm $T$ is$T=T(U_{C})+T(D_{EN})$

calculatwhere $T(U_{C})$ is the computational complexity of unitary operator
degree.
$T(D_{EN})$is that of calculation of entanglement
ing
and
The entanglement degree is obtained with probability 1, then the halting
probability of this algorithm is 1 (c.f. OMV SAT algorithm).
Now we have to construct a physical model which achieves this algorithm.
And we apply this to the other problems.
$U_{C}$$f_{C}$

References[1] M.Ohya and I.V.Volovich, Quantum computing and chaotic amplification,
J. opt. B, 5,No.6 $639- 642$ , 2003.

[2] M.Ohya and I.V.Volovich, New quantum algorithm for studying NPcomplete problems, Rep.Math.Phys., 52, No.1,25-332003.
[3] M.Ohya and I.V.Volovich, Mathematical Foundation of Quantum Information and Quantum Computation, to be published.

[4] M.Ohya and N.Masuda, NP problem in Quantum Algorithm, Open Systems and Information Dynamics, 7 No.133-39, 2000.
[5] V.P.Belavkin and M.Ohya (2002) R. Soc. Lond. Proc. Ser. A Math. Phys.
Eng. Sci. 458, no. 2017, 209-231[6] L.Accardi and M.Ohya, A Stochastic Limit Approach to the SAT Problem,Open Systems and Information dynamics, 11,1-16, 2004.
[7] S.Iriyama and M.Ohya, Rigorous Estimation of the Computational Complexity for OMV SAT Algorithm, Open System&Information Dynamics,
15, 2, 173-187, 2008.
[8] S.Iriyama and M. Ohya, Language Classes Defined by Generalised Quantum$T_{J}ring$ Machine, to appear in OSID, 2008

123[9] S.Iriyama, M.Ohya and I.V.Volovich, Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm, QP-PQ:Quantum
Prob. White Noise Anal., Quantum Information and Computing, 19, World

Sci. Publishing, 204-225, 2006.

[10] T.Matsuoka and M.Ohya (2005) Quantum Entangled State and Its Characterization,Foundations of Probability and Physics-3, American Instituteof Physics, 750,298-306.
[11] L.Accardi, T.Matsuoka and M.Ohya (2006) Entangled Markov Chains are
Indeed Entangled, Infinite Dimensional Analysis Quantum Probability and
Related Topics, vo19, no 3, 379-390.