Accardi L., Freudenberg W., Obya M. (Eds.) Quantum Bio-informatics IV: From Quantum Information to Bio-informatics
Подождите немного. Документ загружается.
170
B
(m)
B(m)
Th
h
1 ,
...
,
m·
en
we ave
/
g(m)
(x)diJ>t(x)
=
f>~m)iJ>t
(Bk
m
))
k=l
=
f>~m)
/
iJ>(d[x,
s])X(O,t)
(s
)Ox+wx(t-s) (
Bk
m
))
k=l
L g(ml(x +
wx(t
- s)).
(30)
From
(30)
we
obtain
C<!>t(g(m))
[x,sjE<!>,O<s<t
=
Eexp
(i
/
g(m)
(X)diJ>t(X))
=
Eexp
{ L g(m)(x + wx(t -
S))}
[x,sjE<!>,O<s<t
=E
II
exp{ig(m)(x+wx(t-s))}.
[x,sjE<!>
,
O<s<t
= /
P,,(diJ»
II
Eexp{ig(m)(x+wx(t-s))}
[x,sjE<!>,O<s<t
=
exp
(/
f.l(d[x,
s])X(O,t)(s)
[E
exp
{ig(m)(x +
wx(t
-
s))}
-
1])
(31)
where
the
equality
(31)
is
obtained
from
the
independence of
((wx(t))t>O)xERd
and
iJ>.
Further
it
holds
Eexp{ig(m)(x+wx(t-s))}
= /
exp
{ig(m)(y)}
kt-s(x,y)dy.
(32)
From
(31),(32) we
obtain
C<!>t
(g(m))
=
exp
(/
f.l(d[x,
s]h(o,t) (s)
[/
exp
{ii
m
)
(y) }
kt-s(x
, y)dy -
1])
=
exp
(/
{/
/ h(x, s
)X(O,t)
(s
)kt-s(x,
y)dxds } [ex
p
{ig(m) (y) } -
1]
d
Y
) .
(33)
Setting
h
t
as
ht(y)
:=
/ / h(x, s)X(O,t)(s)kt-s(x, y)dxds,
we
obtain
from (33)
CiPt(g(m))
= exp
(/
ht(y) [ex
p
{ig(m)(y)}
-1]
d
Y
)
171
= exp
(/
ILt(dy)
[ex
p
{ig(m)(y)} - 1
J)
. (34)
Similarly as (18) let us
approximate
a general function g by
the
sequence
(g(m))mEN.
Then
it
holds from (34)
CiPt(g)
=
exp
(/
ILt(dy)
[exp{ig(y)}
-l
l
) .
That
proves
lemma
4.4
.•
References
1. L.
Breiman,
Probability,
Reading,
Mass., 1968.
2.
J.
Feldman,
Decomposable
processes
and
continuous
products
of
probability
spaces,
J.
Function.
Analysis,
8,
I-51, 1971.
3. K.-H.
Fichtner,
K. Inoue, M.
Ohya,
Approximative
approaches
to
a
stochastic
partial
differential
equation
by
point
systems,
Preprint.
4.
K.-H.
Fichtner,
R.
Manthey,
Weak
approximation
of
stochastic
equations,
Stochastics
and
Stochastics
Reports,
43,
139-160, 1993.
5. K.-H.
Fichtner,
M.
Schmidt,
Approximation
of
a
continuous
system
by
point
systems,
SERDIeA,
13,
396-402, 1987.
6.
K.-H.
Fichtner,
G.
Winkler,
Generalized
Brownian
motion,
point
processes
and
stochastic
calculus for
random
fields,
Math.
Nachr.
161,
291-307, 1993.
7.
K.
Matthes,
J.
Kerstan,
J.
Mecke, Infinitely divisible
point
processes, J.Wiley,
New York, 1978.
8.
J.B.
Walsh, A
stochastic
model
of
neural
response,
Adv.Appl.Probability,
13,
231-281, 1981.
9.
H. Zessin,
The
method
of
moments
for
random
measure,
Z.
Wahrsch.
Verw.
Gebiete
62,
395-409, 1983.
This page intentionally left blankThis page intentionally left blank
Quantum
Bio-Informatics
IV
eds. L.
Accardi,
W. Freudenberg
and
M.
Ohya
© 2011
World
Scientific
Publishing
Co.
(pp
. 173- 183)
ON
QUANTUM
ALGORITHM
FOR
EXPTIME
PROBLEM
S.
IRIYAMA
AND
M.
OHYA
Department
of
Information
Sciences
, Tokyo
University
of
Science
2641,
Yamazaki,
Noda
City, Chiba, Japan
There
exists
a
quantum
algorithm
with
chaos
dynamics
solving
an
NP-complete
problem
in
polynomial
time,
called
OMV
SAT
algorithm
.
The
language
class
EXPTIME
is
larger
class
than
NP,
there
is no classical
algorithm
to
solve
it
in
polynomial
time.
In
this
paper
we
propose
a
quantum
algorithm
for
one
of
the
problems
in
EXPTIME,
Pebble
Game,
and
compare
the
computational
complex-
ity
of
it
with
the
classical one.
We
show
that
a
quantum
algorithm
with
Oracle
solves
it
in
polynomial
time
while
a classical
algorithm
with
same
Oracle
does
in
exponential
time.
1.
Introduction
We have
studied
on
quantum
algorithm
for several years. Ohya,
and
Volovich discovered
the quantum
algorithm
with
chaos dynamics called
the
OMV
quantum
algorithm
which
can
solve
NP
complete
problem
in poly-
nomial time. We applied
this
quantum
algorithm
to
the
other
problems,
multiple alignment
of
amino acid sequence,
Hamilton
closed
path
problem,
protein
folding
problem
and
EXPTIME
problem. Therefore we found
that
OMV
quantum
algorithm
is useful for searching problems, i.e.,
to
search
the
objects
which satisfy
the
given conditions.
In
the
field
of
Bio-Information
there
exist
many
searching problems,
and
we
can
apply
our
quantum
algo-
rithm
to
them.
In
this
paper,
we show a
quantum
algorithm
for
EXPTIME
problem,
Pebble Game.
Then
we discuss
the
computational
complexity
of
it.
2.
Quantum
Algorithm
A
quantum
algorithm
is
constructed
by
the
following steps:
(1)
Prepare
a Hilbert space
(2)
Construct
an
initial
state
(3)
Construct
unitary
operators
to
solve
the
problem
173
174
(4)
Apply
them
for
the
initial
state
and
obtain
a
result
state
(5)
If
necessary, amplify
the
probability
of
correct
result
(6)
Measure
an
observable
with
the
result
state
In
the
first
step,
we
define
the
Hilbert
space
depending
on
the
problem.
Let
((:2
be
a
Hilbert
space
spanned
by
10)
=
(~)
and
11)
=
(~),
a
normalized
vector
1'If!)
= a
10)
+
(311)
on
this
space
is called a
qubit.
Since
we
can
use a
superposition
of
10)
and
11)
as
an
initial
state
vector,
the
quantum
algorithm
is more effective
than
classical one.
One
can
apply
Hadamard
transformation
H
__
1
(1
1 )
-
y'2
1-1
to
create
a superposition.
For
10)
and
11),
it
works as
1 1
H
10)
=
y'210)
+
y'211)
1 1
H
11)
=
-10)
-
-11)
.
y'2 y'2
Hadamard
transformation
has
a very
important
role
in
a
quantum
algo-
rithm.
Here we
introduce
logical gates, which
are
NOT
gate,
C-NOT
gate
and
CC-NOT
gate. We call
these
gates
fundamental
gates. We
can
also con-
struct
AND
and
OR
gate
by
considering
the
product
of
fundamental
gates
and
some
imprementations.
The
NOT
gate
U
NOT
is defined
on
a
Hilbert
space ((:2 as
UNO
T
=
11)
(01
+
10)
(11·
It
works for
an
arbitrary
qubit
as
C-NOT
UCN
gate
and
CC-NOT
UCCN
are
given
on
two
and
three
qubit
Hilbert
space as
UCN
=
10)
(01
® I +
11)
(11
®
UNO
T
UCCN
=
10)
(01
® I ® I +
11)
(11
®
10)
(01
® I +
11)
(11
®
11)
(11
®
UNO
T
,
respectively.
The
unitary
operator
to
solve
the
problem
is
constructed
by
these
fundamental
gates.
175
3.
OMV
SAT
Algorithm
In
this
section,
we
explain
OMV(Ohya-Masuda-Volovich)
quantum
algo-
rithm
which
contains
two
part,
that
are
unitary
computation
and
chaos
amplification process.
It
is discussed precisely
in
the
papers
l
,2,4,9.
Let
X
==
{Xl,
...
,xn},n
E N
be
a set. Xk
and
its
negation
Xk (k =
1,
...
,
n)
are
called literals.
Let
X
==
{Xl,
..
"
Xn}
be
a set,
then
the
set
of
all literals is
denoted
by
X'
==
X
UX
=
{Xl,
...
, X
n
,
Xl,""
X
n
}.
The
set of all
subsets
of
X'
is
denoted
by
:F
(X')
and
an
element G E :F
(X')
is called a clause. We
take
a
truth
assignment t
to
all variables Xk.
If
we
can
assign
the
truth
value
to
at
least
one
element
of
G,
then
G is called
satisfiable.
Let
L =
{O,
I}
be
a Boolean
lattice
with
usual
join
V
and
meet
1\,
and
t (x)
be
the
truth
value
of
a literal X
in
X.
Then
the
truth
value
of
a clause
G is
written
as
t(G)
==
VxEct(x).
Moreover
the
set
C of all clauses G
j
(j
=
1,2,'"
,m)
is called satisfiable
iff
t
(C)
==
I\'j=l t
(G
j
)
=
1.
Thus
the
SAT
problem
is
written
as follows:
[SAT problem] Given a Boolean
set
X
==
{Xl,'"
,xn}and
a
set
C =
{G
l
,'"
,G
m
}
of
clauses,
determine
whether
C is satisfiable
or
not.
That
is,
this
problem
is
to
ask
whether
there
exists a
truth
assignment
to
make
C satisfiable.
It
is known
that
we
can
check
the
satisfiability
in
polynomial
time
when
a specific
truth
assignment is given, however we do
not
determine
it
in
polynomial
time
when
an
assignment is
not
specified.
We first calculate
the
total
number
of qubits,
and
show
that
this
number
depends
on
the
input
data.
This
calculation is done
in
polynomial
time
of
input
size. Since
the
total
number
of
qubit
required
the
quantum
algorithm,
we
decide
the
Hilbert
space
and
the
initial
state
vector
on it.
Let
C
{G
l
,
...
,G
m
}
be
a
set
of
clauses on
X'
{Xl,
...
,X
n
,
Xl,
...
,x
n
}.
The
computational
basis
of
this
algorithm
is
on
the
Hilbert
space H =
(C
2
)'l9
n
+I-'+l
where
f.L
is a
number
of
dust
qubits,
it
is shown
that
f.L
is less
than
2mn
g.
Let
be
an
initial
state
vector. For X =
{Xl,
...
,x
n
}
and
a
truth
assignment t,
we
put
where
Cl,
C2,
...
,Cn
E
{O,
I}
,
and
we
write
t
as
a sequence of
binary
sym-
176
boIs:
A
unitary
operator
Uc
:
1i
-t
1i
computes
t
(C)
for all
truth
assignment as
follows
where
Id
P
)
is
dust
qubits
denoted
by
p,
strings
of
binary
symbols,
and
lei)
= leI,
e2,
...
,en) is a
binary
representation
of
t. Accardi
and
Sabbadini
pointed
out
that
OMV
SAT
algorithm
is
combinatorial
6
.
Theorem
3.1.
(l)
For a set
of
clauses C =
{G
l
,
...
, G
m
}
on
X'
==
{Xl,
...
,X
n
,
Xl,···,
xn}, the number
p,
of
dust qubits for algorithm
of
SAT
problem is
p,:::::
2nm
For a
set
of
clauses C =
{G
l
,
...
, G
m
},
we
can
construct
the
unitary
operator
Uc
to
calculate
the
truth
value
of
C
as
m - l m
U
c
==
II
UAND
(i)
IIU
oR
(j)
H (n)
i=l
j=l
where, H (k) is a
unitary
operator
to
apply
Hadamard
transformation
to
first k
qubits,
that
is
The
computational
complexity
of
quantum
computation
depends
on
the
number
of
unitary
operator
in
the
quantum
circuit.
Let
U
be
the
unitary
operator,
it
is
written
as
where Un,·
..
,U
l
are
fundamental
gates.
The
computational
complexity
T (U) is considered
as
n.
177
We need
to
combine some
fundamental
gates
such as UNOT,
UCN
and
UCCN
to
construct
the
quantum
circuit in fact. U
AN
D
and
UOR
can
be writ-
ten
as
a
combination
of
fundamental
gates. Here
we
obtain
the
computa-
tional
complexity T (Uc) of SAT
algorithm
by
the
number
of
U NOT, U AN D
and
UOR.
Theorem
3.2.
f)
For a
set
of
clauses C =
{G
1
,
...
, G
m
}
and literal
X'
=
{X1,
...
,X
n
,X1,
...
,X
n
},
T(Uc)
is
m
T (Uc) = m - 1 + L
(IGkl
+
2i~
-
1)
k-1
:::;
4mn-l
3.1.
Chaos
Amplifier
Here we will briefly review how chaos
can
playa
constructive
role
in
com-
putation
(see
1,2
for
the
details).
Consider
the
so called logistic
map
which is given
by
the
equation
The
properties
of
the
map
depend
on
the
parameter
a.
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
notice
that
if
the
initial value
Xo
= 0,
then
Xn
= ° for all
n.
The
state
1'IjJ)
of
the
previous
subsection
is
transformed
into
the
density
matrix
of
the
form
where
PI
and
Po
are
projectors
to
the
state
vectors
11)
and
10
) .
One
has
to
notice
that
PI
and
Po
generate
an
Abelian
algebra
which
can
be
considered
as a classical system.
The
following
theorems
is proven
in
1,2,3.
Theorem
3.3.
For the logistic
map
X
n
+1
= aXn
(1
-
Xn)
with a E [0,4]
and
Xo
E
[0
, 1], let
Xo
be
2~
and a
set
J
be
{O
,
1,2,
...
, n,
...
,
2n}.
If
a is
3.71, then there exists an integer
k
in
J satisfying
Xk
>
~.
Theorem
3.4.
Let
a and n
be
the
same
in
above theorem.
If
there exists
k
in
J such that
Xk
>
~,
then k >
log2~~A
-
1.
178
Theorem
3.5.
Let
It
(C)I
be
the
cardinality
of
thes
e
assignments,
if
Xo
==
.{n
with
r =
It
(C)I
and
there
exists
k
in
J
such
that
Xk
>
~,
then
there
exists k
satisfying
the following
inequality
if
C is SAT.
[
n -
1
-log2
r]
< k <
[-4
5
(n
_ 1)]
log2 3.71 - 1 - -
From these
theorem
s, for all k,
it
holds
k (2)
{=
0
g3.71
q > 0
iff C is
not
SAT
iff C is SAT
Ohya
a
nd
Volovich proposed
quantum
algorithm
to
calculate
truth
func-
tion
by
unitary
operators
and
mentioned
that
it
is necessary
to
use some
amplification processes
to
detect
the
result in case
of
very small proba-
bility.
Then
they
discovered
that
on
e
can
construct
this
process by using
chaos dynamics.
The
computational
complexity
of
OMV
SAT
algorithm
is
discussed
pr
ecisely
in
the
papers
10
,9,1l
4.
Language
Classes
There
exist several classical language classes defined by a deterministic
Turing
machine.
Definition
4.1.
Let M
be
a deterministic
Turing
machine such
that
halts
for all
input.
For a
length
n of
input
, let f (n)
be
a
maximum
length
of
tape
cell of
M.
We define a space complexity
of
M as f.
Definition
4.2.
PSPACE
is
the
languag
e class which is recognized by a
deterministic Turing machine in a polynomial
spac
e.
Definition
4.3.
NPSPACE
is
the
language class which is recognized by a
non-deterministic
Turing
machine in a polynomial space.
Definition
4.4.
EXPTIME
is
the
language class which is recognized by a
deterministic
Turing
machine in
an
exponential
time
.
The
following relation is known:
P
~
NP
~
PSPACE
=
NPSPACE
~
EXPTIME
179
5.
Pebble
Game
Pebble
Game
is
the
two players
game
using a play
board
and
stones(pebbles). Players move one
stone
at
a
time
along a given rule alter-
natively. A player wins when he moves a
stone
to
the
winning position
on
the
board
given by
the
rule,
or
he loses when
he
cannot
move
any
stones.
We
want
to
know
whether
there
exist
strategies
such
that
a first mover
can
win every time.
The
computational
complexity of
this
problem is obvi-
ously very large,
and
in
some cases dep
end
ing
on
a size
of
board
and
rule
it
belongs
to
EXPTIME.
Then
we propose a
quantum
algorithm
for
Pebble
Game.
First
, we explain a
representation
of
game
and
a definition
of
Pebble
Game.
5.1.
Representation
of
a
Game
Let
I
be
a
set
of players, M a
set
of
moves (
or
strategi
es) available
to
those
players,
and
P a
set
of
payments
for each combination of moves. A
game
G is given a
triplet
(I,
M,
P).
The
set
of moves is given by a rule of
the
game.
Play
ers choice
th
eir move
in
their
turn
alternatively, so
then
these
choices
are
described by a sequence
of
moves. We
denote
this
by a position
Pi
where a player i E I
has
the
move. A
set
of
ordered
pair
(pi, Pj) where
Pi
and
Pj are positions such
that
Pi
-7
Pj is a feasible move implies
the
rule
of
the
game.
The
game is finished when
there
does
not
exist
any
moves in someone's
turn.
When
the
game
is finished,
the
payments
are
given
to
players by a
function
of
the
position.
In
this
study
we assume
that
the
game
must
be
finished so
that
the
length
of position is finite.
We say a player A wins if
the
payments
of
A is
greater
than
a player B
in
two players game.
Then
we consider
the
following problem:
[Game
Probleml]
Does
there
exist a way such
that
a player A wins
independently
of
how a player B plays?
To answer this,
a winning position
of
A was
introduced
by Konig.as a
set
of
positions where A wins
in
finite moves
in
spite
of
moves of B.
A
set
of
winning positions
of
A is
constructed
inductively from a
set
of
positions where A wins by only one move.
Let
P is a winning position, q
is also a winning position if
there
exists a move r A
of
A such
that
for all
moves
rB
of
B,
it
holds