Accardi L., Freudenberg W., Obya M. (Eds.) Quantum Bio-informatics IV: From Quantum Information to Bio-informatics
Подождите немного. Документ загружается.
180
Therefore
,
the
Problem
1 is equivalent as
the
following:
[Game
Problem2]
Determine
whether
an
initial
position
of
the
game
is
in
a winning
position
of A?
5.2.
Pebble
Game
Let
n
be
a positive finite integer
denoted
by
a size
of
Pebble
Game.
n-
Pebble
Game
is given
by
a
triplet
G
Pebble
=
(I,
M,
P)
where I =
{A,B},
M =
{r=(r
l
,r
2
,r
3
)E{1,
...
,n}3;risanavailablemove}
and
P =
{f:
Mk
->
{O,
I}}.
M is a
set
of
available moves
depending
on
a
situation
of
the
board
and
positions
of
stones.
The
rule
of
Pebble
Game
is
the
following:
•
Prepare
n
lattices
denoted
by
a
board
and
put
m ( < n)
stones
on
nodes.
Each
nodes
has
a
unique
number
i = 1,
...
n.
• Players move
one
of
stones
alternatively
if
the
stone
so chosen
can
jump
the
neighbor stone.
•
If
a player
puts
a
stone
on
the
node
n,
he wins.
If
a player
can
not
move
any
stones,
he
loses.
Let
x = (Xl,
X2,
...
, xn)
be
a vector
of
Boolean variables
denoted
by
a
situation
of
board,
where
Xi
has
one
to
one
correspondence
with
a
node
i:
Xi
=
{O
no
stone
on
a
node
i
1
nod
e i
has
a
ston
e
We
prepare
m
stones
on
the
board
Xs
arbitrary
and
call
it
an
initial
situa-
tion.
And
we call a finished
situation
X f if
there
are
no
available moves.
A move
ri (i E
{A,
B})
for a player i is
represented
by
(rl,
r2,
r3)
E
{I,
...
,
n}
3
where
rl
indicates a position
of
stone,
r2
the
neighbor
and
r3
a
position of
destination.
If
there
is a
stone
on
rl
and
r2
and
there
is
not
a
stone
on
r3
,
th
e move ri = (rl,r2,r3) is available.
After
one move,
the
situation
of
board
is
changed
by
_
{Xi
i =
rl
or
i =
r3
Xi
-
Xi
otherwise
we
denote
ri (x)
by
a
situation
of
board
after
a move
rio
If
there
no moves available
or
he
can
move a
stone
to
the
node
n,
the
game
is finished.
Then
we
have a sequence
of
moves. For a sequence
of
moves
Pi
(i E
{A,
B})
= (r1,
r§,
...
,
rf)
a
payment
for a player A is given
by
a function fA E
P:
and
for a player B is
by
fB
E
P:
{
o
i = A
fB
(Pi)
= 1 i = B
Let
us define
the
following problem:
181
[Pebble
Probleml]
Does
there
exist a way such
that
a player A wins
independently
of how a player B plays
in
n-Pebble
Game?
This
problem
belongs
to
EXPTIME
if m is
not
fixed
8
.
We check
whether
an
initial
situation
is a winning
position
of A for all
number
m
of
stones.
Then
the
Pebble
Problem1
is
translated
to
the
following problem:
[Pebble
Problem2]
For
all finished
situations
xf
determine
whether
there
exists k such
that
3r~\lr~-1
...
3d
\lr13r~
(xs)
=
xf
where
Xs
is
an
initial
situation.
We propose a
quantum
algorithm
with
Oracle
to
solve
the
Pebble
Problem2,
and
show
that
even if we assume
an
Oracle, a classical
algorithm
is still
an
exponential
time.
5.3.
Computational
Complexity
of
a
Classical
Algorithm
for
Pebble
Game
In
order
to
discuss a relative
computational
complexity
between
classcal
and
quantum
algorithm, we
assume
the
following Oracle Mo:
Mo
: {x; x is a
situation}
---;
N U
{O}
For a finished
situation
x
f'
Mo
cutputs
the
time
of
it
immediately,
just
one step.
If
a
situation
x is
not
a final
situation,
Mo
outputs
o.
A classical
algorithm
to
solve
Pebble
Problem2
is
the
following.
Step1
For
all
situations,
we do:
Step2
Calculate
time
k (x) for a
situation
x
Step3
If
x is a final
situation,
construct
a
set
Wi
(i =
1,2,
...
, k (x))of
winning situations:
Wi
=
{y;
3r~,
\lrB,
3r
A,
r~rBr
AY
E
Wi-I}
where
Wo
= {x}
Step4
Check
Xs
=
Wk(x).
182
The
number
of all
situations
2
n
,
and
the
upper
bound
of
number
of
available moves is
4n
since a player
can
move one
pebble into
four directions
at
most. Therefore
the
computational
complexity
of
a classical
algorithm
Tc (n) is
Tc (n)
rv
(4n)3
x 2
n
rv
exp
(n)
Even
if
we
assume
the
Oracle,
this
problem
belongs
to
EXPTIME.
6.
Quantum
Algorithm
for
Pebble
Game
As
we
assume
the
Oracle
Mo,
we
use a
quantum
Oracle U
Mo
which works
as
same
as
Mo.
Here,
we
construct
the
following
quantum
algorithm:
Step
1
Create
a
superposition
of
all
situations.
Step2
For
the
superposition,
apply
Oracle U
Mo.
Step3
We
construct
Wi (i =
1,2,
...
k
(xf))
for
the
superposition.
Step4
If
Xs
E
Wk(x),
make
the
final
qubit
11).
All
situations
are
represented
by
a
binary
form, so
then
we
can
create
a
superposition
of
them
using
Hadamard
transformation.
Step3
is achieved
by
a
product
of
unitary
gates.
In
Step4,
AND
operation
is
constructed
by
unitary
gates
9
.
If
final
qubit
of
superposition
is
11),
there
exists a way
of
winning. Using
the
chaos amplifier,
we
obtain
the
result.
7.
Computational
Complexity
Here,
we
calculate
the
computational
complexity
of
the
quantum
algorithm
as
the
total
number
of
fundamental
gates.
The
Step
1 is
constructed
by
n
Hadamard
gates.
The
Step2
is done
by
only
one
Oracle U
Mo.
The
compu-
tational
complexity
of
Step3
has
the
same
order
as
the
classical algorithm.
In
the
Step4
AND
operation
requires n
gates
for n
qubit.
The
upper
bound
of
IWk(x)
I is
(~)
where m is
the
number
of
pebbles.
Therefore,
computational
complexity
TQ
(n)
of
quantum
algorithm
of
Pebble
Problem2
is
TQ
(n)
rv
{n
+ 1 +
(4n)3
+
(:)
} x
[~(n
-1)]
rv
poly (n)
where
[~(
n - 1)] is for chaos amplification
to
obtain
the
correct result.
183
8.
Conclusion
The
computational
complexity
Tc
(n) of a classical
algorithm
for
n-Pebble
Game
with
Oracle is
Tc
(n)
~
(4n)3
x 2
n
~
exp (n)
This
is a
exponential
time
of
input
size n. We
constructed
a
quantum
algorithm
for this,
the
computational
complexity
TQ
(n) is
T Q (n)
cv
{ n + 1 + (4n) 3 +
(:)
} x
[~(
n -
1)]
cv
poly (n)
In
this
study,
we
assume
the
Oracle
Mo
and
the
unitary
operator
U
Mo
which works as
Mo.
Even if we use
this
Oracle,
the
computational
com-
plexity
of
the
classical
algorithm
for Pebble
game
is
an
exponential
time
while
it
of
the
quantum
algorithm
is a polynomial
of
n.
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 NP-complete
problems,
Rep.Math.Phys.
,
52
, No.l,25-33 2003.
3.
M.Ohya
and
I.V.Volovich,
Mathematical
Foundation
of
Quantum
Comput-
ers,
Teleportations
and
Cryptography,
to
be
published.
4.
M.Ohya
and
N.Masuda,
NP
problem
in
Quantum
Algorithm,
Open
Sys
tems
and
Information
Dynamics,
7 No.1 33-39, 2000.
5. L.
Accardi
and
M.Ohya,
A
Stochastic
limit
approach
to
the
SAT
problem,
Open
systems
and
Information
Dynamics,
11-3, 219-233, 2004
6.
L.Accardi
and
R.Sabbadini,
On
the
Ohya
-
Masuda
quantum
SAT
Algorithm,
Preprint
Volterra, N. 432, 2000.
7.
E.Bernstein
and
U.Vazirani,
Quantum
Complexity Theory,
In
Proc.
25th
ACM
Symp.
on
Theory
of
Computation,
11-20, 1993.
8.
T.Kasai,
A. Adachi,
S.
Iwata,
Classes
of
Pebble
Games
and
Complete
Prob-
lems,SIAM J.
Comput.
Volume 8, Issue 4, pp. 574-586 (1979)
9.
S.Iriyama
and
M.Ohya,
Rigorous
Estimate
for
OMV
SAT
Algorithm,
Open
Systems
&
Information
Dynamics,
15, 2, 173-187, 2008
10. S.Iriyama,
M.Ohya
and
I.V.Volovich (2006) Generalized
Quantum
Turing
Machine
and
its
Application
to
the
SAT
Chaos
Algorithm,
QP-PQ:Quantum
Prob.
Whit
e Noise Anal.,
Quantum
Information
and
Computing,
19,
World
Sci.
Publishing,
204-225
11.
S.Iriyama
and
M.Ohya
(2008)
Language
Classes Defined by Generalized
Quantum
Turing
Machine,
Open
System
and
Information
Dynamics
15:4,
383-396.
12.
S.Iriyama
and
M.Ohya
(2009)
The
problem
to
construct
Unitary
Quantum
Turing
Machine
for
compute
partial
recursive function,
TUS
preprint.
13.
S.Iriyama
and
M.Ohya
(2010)
Quantum
Algorithm
for
Pebble
Game
and
Its
Computational
Complexity,
TUS
preprint.
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.
185-197)
ON
SUFFICIENT
ALGEBRAIC
CONDITIONS
FOR
IDENTIFICATION
OF
QUANTUM
STATES
ANDRZEJ JAMIOLKOWSKI
Institut
e
of
Physics, Nicholas Copernicus University,
87
- 100 Torun, Poland
E-mail: jam@fizyka.umk.pl
The
aim
of
this
paper
is
to
discuss
the
relationship
between
some
problems
of
the
identification
of
quantum
states
by
geometric
methods
used
in
stroboscopic
tomography
and,
on
the
other
hand
,
by
alg
ebraic
approach
typical
for
the
quantum
generalization
of
classical
sufficient
statistics.
Some
examp
les
of
necessary
and
sufficient
conditions
which
must
be
fulfilled by
generators
of
algebras
in
order
to
estimate
states
of
quantum
systems
are
discussed.
Keywords:
algebras
of
observables;
stroboscop
ic
tomography;
generators
of
suba
lgebras.
1.
Introduction
One
of
the
basic
purpose
of
physical theories, in
both
classical
and
quantum
sectors, is
to
describe events
that
are
observed in
Nature
or
in
experiments
conducted
in
laboratories. Usually,
we
have a physical
system
under
in-
vestigation,
and
we
try
to
obtain
information
about
it
by
making
some
experiments. As results,
measurement
outcomes
are
registered.
In
fact,
in
many
situations
in classical systems,
and
in
all cases in
the
quantum
regime, we
can
not
predict
the
individual
measurement
outcomes
and
we
obtain
only some probabilities
of
results.
In
other
words, we
obtain,
as
the
outputs
of
experiments, only probability
distributions
on
a
set
of
possible
measurement
outcomes.
The
statistical
theory
of
classical
systems
is based
on
classical probabil-
ity
theory. However,
atoms
and
molecules obey
the
statistical
laws
of
quan-
tum
mechanics
and
one
has
to
develop a parallel
theory
based
on
quantum
probability (noncommutative probability),
which is
an
essential generaliza-
tion
of
classical probability theory.
In
classical
statistical
physics
we
consider probability
distributions
as
natural
representation
of
states
and
random
variables as
representation
of
observables (physical quantities).
In
the
description
of
microsystems
it
185
186
is
natural
to
start
with
the
idea
of
observables as a
quantum
analogue
of
random
variables
and
to
define
states
as
a derived concept.
This
means
that
we
introduce
quantum
states
through
the
concept
of
algebra
of
observables,
taking
the
states
to
belong
to
the
dual
space.
The
algebra, furnished
with
the
operation
of
conjugation
(*-operation) is
postulated
to
be
a
C*-algebra
with
identity.
It
can
be
considered as a
natural
generalization of
the
algebra
of
classical functions
with
*
-operation
given
by
complex conjugation,
and
whose real
random
variables
are
self-adjoint elements. A nice discussion
of
these
issues is given
by
W.
Thirring
in his
lecture
notes
1.
From
the
physical
point
of
view,
by
a
state
we
understand
the
descrip-
tion
of
statistical
properties
of
a
system
when
prepared
repeatedly
in
the
same
way. In
other
words, one
of
the
basic
assumptions
of
quantum
me-
chanics is
based
on
the
observation
that
determination
of a completely
unknown
state
can
be
achieved
by
appropriate
measurements
only if
we
have
at
our
disposal a
set
of identically
prepared
copies
of
the
system
in
question.
From
the
mathematical
point
of
view, we say
that
a state
on
a
C*-
algebra
of
observables is
an
assignment
of
a
number
(the
expectation
value) for every element of
the
algebra.
This
assignment
should
obey
the
natural
laws
of
linearity
and
positivity.
Thus,
if
we
denote
by
A a C*-
algebra
with
identity
(a
set
of
observables)
then
a
state
on
A is a linear
map
(1)
such
that
P(C"1Q1
+ a2Q2) = a1P(Qd + a2P(Q2) for all a1,
a2
in
C
and
Q1,Q2 in A,
and
p(Q)
~
0 for all positive Q E A. Usually,
we
also assume
that
p(lI)
= 1.
Moreover,
to
set
up
an
effective
approach
to
the
above
problem
of
state
determination,
one
has
to
identify a collection
of
observables, a quorum
2
,
such
that
their
expectation
values
contain
complete
information
about
the
state
of
the
system
under
consideration. In
the
standard
formulation
of
quantum
mechanics, usually
we
introduce
a
Hilbert
space H
associated
with
a given microsystem
and
we identify
an
algebra
of observables A
with
the
set
of
hermitian
elements
of
the
Hilbert-Schmidt
space
B(H).
For
any
normalized vector
Iw)
E H
the
formula
p,p(Q) =
(wIQlw)
(2)
defines a
state
on
A. Such a
state
is called vector state. In general,
the
expectation
values
are
given
by
convex
combinations
of
some vector
states
187
and
we have
the
following equality
f5(Q)
= Tr(pQ) , (3)
where p denotes a
state
of
the
system
in
question.
The
problems
of
state
determination
have gained new relevance in recent
years, following
the
realization
that
quantum
systems
and
their
evolutions
can
perform
tasks
such as
teleportation
, secure communication
or
dense
coding (c.f. e.g.
3,
4).
It
is
important
to
realize
that
if
we
identify
the
quorum
of
observables,
then
we also have a possibility
to
determine
the
ex-
pectation
values
of
physical
quantities
(observables) for which
no
measuring
apparatuses
are
available
5.
The
idea
of
stroboscopic
tomogr
aphy for
open
quantum
systems ap-
peared
for
the
first
time
in
the
beginning
of
1980's (although
it
was ex-
pressed in different
terms
6,7 from
the
ones used presently).
In
particular,
the
question
of
the
minimal
number
of observables
Ql,
.
..
,
Q",
for which
quantum
states
can
be
(Ql
, . . . , Q",)-reconstructible was discussed.
Simultan
eously,
it
was shown
that
reconstructibility
of
states
in
a finite
dimensional
systems
can
be
achieved if a sequence
of
the
so-called K rylov
subspaces
which
are
defined by
(4)
where Q is a fixed observable
and
lL
is a
generator
of
time
evolution
of
the
system
in
question,
span
the
Hilbert-Schmidt space
B(H)
(cf.
below
Sect. 3).
That
is, more
pr
ecisely, if
the
following equality is satisfied
(5)
In
the
above e
quality
I-"
denotes
the
degree
of
the
minimal polynomial
of
the
superoperator
lL
and
Ql,
...
,
Qr
represent fixed observables.
The
symbol
ffi denotes
the
Minkowski
sum
of
subspaces (5)
(cf.
e.g.
8).
We recall
that
for two subspaces
Kl
and
K2
of
the
vector space
H,
by
Kl
ffi
K2
one
understands
the
smallest subspace
of
H which contains
both
Kl
and.K
2
.
It
is well known
that
the
Krylov subspaces Kk(lL,
Q)
for k =
1,2,
...
form
a nested sequence
of
subspaces
of
increasing dimensions
that
eve
ntually
become invariant
under
lL
. Hence for a given Q,
there
exists
an
index
I-"
=
1-"(
Q)
, often called
th
e grade
of
Q with respect to
lL,
for which
Kl(lL,Q)
<;;
...
<;;
KJJ-(lL,Q)
= KJJ-+l(lL,Q) = KJJ-+2(lL,Q)... . (6)
It
is easy
to
see,
that
for a given
operator
Q,
the
natural
number
I-"(Q)
is equal
to
the
degree
of
the
minimal
polynomial
of
lL
with
respect
of
Q.
188
Clearly,
p,(
Q)
:::;
p,(lL)
where
p,(lL)
denotes
the
degree
of
the
minimal
poly-
nomial of
the
superoperator
lL
(cf.
e.g.
9).
Now, let us observe
that
even if
the
observables Q1,
...
,
Qr
are
linearly
independent,
the
Krylov subspaces
JCk(lL,
Qi) for i =
1,
...
, r
can
have
nonempty
intersections.
When
during
one
of
the
previous
QBIC
meetings
the
author
presented
the
main
ideas
of
the
stroboscopic tomography,
in
response, Prof. M.
Ohya
immediately
suggested
an
operator
algebra
approach
to
these
problems
and
proposed
to
study
the
case of some
subalgebras
of
the
set
of
all observables,
instead
of
Krylov subspaces.
The
main
aim
of
this
paper
is
to
discuss
properties
of
sub
algebras which allow us for identification
of
quantum
states
and
to
analyse
the
minimal
number
of
generators
of
these
algebras.
The
organization
of
the
paper
is as follows:
In
Section 2 we formulate
some questions
connected
with
problems
of
estimation
and
discrimination
of
quantum
states;
Section 3
presents
the
main
ideas
of
the
stroboscopic
tomography.
Then,
in Section 4, we discuss
an
algebraic
approach
to
the
problem
of
identification of
quantum
states.
We conclude
the
paper
in Sec-
tion
5
by
discussing some examples
of
algebraic
methods
in
low dimensional
systems.
2.
Identification
of
quantum
states
In
the
statistical
description
of
physical
systems
the
main
role
of
observables
is
to
statistically
identify
states,
or
some
of
their
properties. A typical goal
of
an
experiment
can
be
to
decide
among
various
alternatives
or
hypothesis
about
states.
As a
very
good
reference
on
such
type
of
problems
we
recom-
mend
the
review
book
10.
The
details
of
a
particular
identification
problem
depend
on
our
prior
knowledge
and
the
properties
we
want
to
discuss.
One
can
say
that
owing
to
both
the
a priori knowledge
about
states
and
the
knowledge of
our
technical possibilities we define
the
alternatives
that
we
should
experimentally
verify.
In
general,
depending
whether
the
set
of
alternatives
is finite
or
not,
one
makes a
distinction
between
discrimination
and
estimation
problems.
One
can
introduce
three
different
types
of
problems:
1)
State
estimation
problem.
In
its
most
general form, one
wants
to
identify
the
state
of
a
system
assuming
that
no
additional
(prior)
knowledge is available.
In
other
words,
the
whole
state
space
of
a
system
constitutes
the
set
of
possible hypotheses.
2)
Sufficient
statistics
for
families
of
states.
In
this
case
we
are
inter-
ested
in considering only a
subset
of
the
whole
set
of
states.
We
189
encode prior knowledge
about
the
preparation
of
states
in
a mul-
tiparameter
family
of
states
and
consider
them
as a possible
set
of
hypotheses. For example, we
can
assume
that
one considers
states
which
are
vector
states
or
have a
particular
block-diagonal form.
3) State discrimination problem. A
particular
case
of
the
problem 2).
One assumes
that
we
want
to
identify
the
state
which belongs
to
a
finite
set
{PI"'"
Pr}
and
our
aim
is
to
distinguish
among
these r
possibilities.
It
is
an
obvious observation
that
in
this
case
the
set
of
observables used for identification
can
be
restricted
in
an
essential
way.
All above problems
create
very interesting
particular
questions
and
we
will discuss
them
in
separate
publications.
The
problem
2)
is discussed
in
details in
our
paper
"Wandering subalgebras, sufficiency
and
stroboscopic
tomography"
11.
3.
Stroboscopic
tomography
of
open
quantum
systems
Quantum
th
eo
ry
- as a description of
properties
of microsystems - was
born
more
then
a
hundred
years ago.
But
for a long
time
it
was merely
a
theory
of isolated systems.
Only
around
fifty years ago
the
theory
of
quantum
systems was generalized.
The
so-called theory
of
open quantum
systems
(systems
interacting
with
their
environments) was established,
and
the
main
sources of
inspiration
for
it
were
quantum
optics
and
the
theory
of
lasers.
This
led
to
the
generalization of
states
(now density
operators
are
considered as
natural
representation
of
quantum
states),
and
to
generalized
description
of
their
time
evolution.
At
that
time
the
concept of so-called
quantum
master
equations - which preserve positive semi-definiteness
of
density
operators
-
and
the
idea
of
a quantum communication channel
were
born,
cf.
e.g.
4,3,12.
On
the
math
e
matical
level,
this
approach
initi-
ated
the
study
of
semi groups
of
completely positive
maps
and
their
gener-
ators. Now, for
the
comfort
of
the
Readers,
we
summarize
the
main
ideas
and
methods
of
description of
open
quantum
systems
and
the
so-called
stroboscopic tomography.
The
time
evolution of a
quantum
system
of
finitely
many
degrees
of
freedom
(a
qudit),
coupled
with
an
infinite
quantum
system, usually called
a reservoir,
can
be
described,
under
certain
limiting conditions, by a one-
parameter
semigroup
of
maps
(cf. e.g.
13,14).
Let 7i
be
the
Hilbert space
of
the
first
system
(dim
7i
=
d)
and
let
(7)