=Paper=
{{Paper
|id=None
|storemode=property
|title=Towards the Notion of an Abstract Quantum Automaton
|pdfUrl=https://ceur-ws.org/Vol-848/ICTERI-2012-CEUR-WS-paper-36-p-17-32.pdf
|volume=Vol-848
|dblpUrl=https://dblp.org/rec/conf/icteri/AlobaidiBZ12
}}
==Towards the Notion of an Abstract Quantum Automaton==
https://ceur-ws.org/Vol-848/ICTERI-2012-CEUR-WS-paper-36-p-17-32.pdf
Towards the Notion of an Abstract Quantum Automaton
Mizal Alobaidi1, Andriy Batyiev2, and Grygoriy Zholtkevych2
1
Tikrit University, Faculty of Computer Sciences and Mathematics,
P.O. Box--42, Tikrit, Iraq
mizalobaidi@yahoo.com
2
V.N. Karazin Kharkiv National University, School of Mathematics
and Mechanics, 4, Svobody Sqr., Kharkiv, 61077, Ukraine
generatorglukoff@gmail.com, zholtkevych@univer.kharkov.ua
Abstract. The main goal of this paper is to give a rigorous mathematical
description of systems for processing quantum information. To do it authors
consider abstract state machines as models of classical computational systems.
This class of machines is refined by introducing constrains on a state structure,
namely, it is assumed that state of computational process has two components:
a control unit state and a memory state. Then authors modify the class of
models by substituting the deterministic evolutionary mechanism for a
stochastic evolutionary mechanism. This approach can be generalized to the
quantum case: one can replace transformations of a classical memory with
quantum operations on a quantum memory. Hence the authors come to the need
to construct a mathematical model of an operation on the quantum memory. It
leads them to the notion of an abstract quantum automaton. Further the authors
demonstrate that a quantum teleportation process is described as evolutionary
process for some abstract quantum automaton.
Key words: computational process, computational model, abstract state
machine, finite-level quantum system, qubit, Kraus' family, quantum operation,
abstract quantum automaton, quantum teleportation
Key terms: MathematicalModelling, MathematicalModel, FormalMethod
1 Introduction
The idea to build a device capable "to compute all that can be computed" had
emerged a long time. One can remember Blaise Pascal's Arithmetic Machine,
Gottfried Wilhelm Leibniz's Stepped Reckoner, Charles Babbage's Difference Engine
and his Analytical Engine [17]. But only in the thirties of last century, Alonzo Church
[3], Alan Mathison Turing [15], and Emil Leon Post [14] built mathematical models
of the computational processes. Although these models have different shapes each of
them describes inherently the same class of processes. The equivalence of the Turing's
model and the Church's model, for example, was proved by A.M. Turing in 1937
[16]. In the late forties, hardware implementations of a universal computational
system were developed and began to be used. They are known now as computers.
18 M. Alobaidi, A. Batyiev and G. Zholtkevych
The practice of using computers to solve real problems showed that besides
answering the question "Can the problem be solved using computer?", an answer to
the question "Do we have enough computational resources to solve the problem?" is
important too. Searches for methods to evaluate computational resources for
computer-assisted problem solving led to the special scientific area which is called
theory of computational complexity (the brief historical overview one can see in [6]).
Unfortunately, most important computational problems are complex ones. In
compliance with the generally accepted propositions of theoretical computing science
the application field of classical computers, i.e. hardware implementations of the
universal Turing machine concept, is physically challenged by problems which have
polynomial computational complexity.
However, modern science, technique, and technology are in need of methods to
solve problems whose complexity is higher than polynomial. This situation stimulates
research of non-classical approaches to computing, and quantum computing is one of
these.
The idea to use quantum systems as computing devices appeared in the early
eighties of the twentieth century. The idea's authors considered it as a way to
overcome computational complexity. In the context Yuri Ivanovitch Manin's
monograph1 [11] and Richard Phillips Feynman's paper [4] should be noted.
Considering the possibility of using quantum machines for solving complex problems
of simulation Yu.I. Manin wrote (cited by [12]): " we need a mathematical theory of
quantum automata. Such a theory would provide us with mathematical models of
deterministic processes with quite unusual properties. One reason for this is that the
quantum state space has far greater capacity then the classical one: for a classical
system with N states, its quantum version allowing superposition (entanglement)
accommodates e N states". In [12], Yu.I. Manin also sets requirements to the
mathematical theory of quantum automata: "The first difficulty we must overcome is
the choice of the correct balance between the mathematical and the physical
principles. The quantum automaton has to be an abstract one: its mathematical model
must appeal only to the general principles of quantum physics, without prescribing a
physical implementation. Then the model of evolution is the unitary rotation in a
finite dimensional Hilbert space, and the decomposition of the system into its virtual
parts corresponds to the tensor product decomposition of the state space ("quantum
entanglement"). Somewhere in this picture we must accommodate interaction, which
is described by density matrices and probabilities".
R.P. Feynman had a similar opinion [4, 5].
This paper is an attempt to construct a mathematical model of quantum automata
that fulfils requirements formulated by Yu.I. Manin.
2 Classical Computational Model
In this section a mathematical model of a classical computational system is
considered. The approach was proposed by A.N. Kolmogorov and V.A. Uspensky
1 The monograph's introduction was translated into English [12]
Towards the Notion of an Abstract Quantum Automaton 19
[10]. Theory of abstract state machine (ASM) is the further development of the
approach [7, 8].
2.1 Preliminary definitions
Definition 1. Let A denotes an algorithm. It is determined by
─ a set C ( A ) of states;
─ a subset I ( A) of C ( A ) which elements are called initial states;
─ a subset T ( A) of C ( A ) which elements are called terminal states;
─ a map A : C ( A) C ( A) which defines one step of the computational process;
─ and the next condition
I ( A) T ( A) = . (1)
Note that elements of the set C ( A ) correspond to complete state descriptions of
the computational process which is defined by the algorithm A .
Definition 2. Let A be an algorithm then a partial map C : N C ( A) 2 is called
a run of the algorithm if it satisfies the following conditions
─ C (0) I ( A);
─ if C (t ) for some t N then C (t ) for all t N such that t < t;
─ if C (t 1) for some t N then C (t 1) = A (C (t )) ;
─ if C (t ) T ( A) then C (t 1) = .
From this definition it follows immediately that the domain of an arbitrary run is
the set N or some set 0 .. T = {t N | t T } , where T is a non-negative integer.
In the first case the algorithm diverges on the initial state C (0) (this is denoted by
A (C (0)) ).
In the second case the algorithm converges on the initial state C (0) to C (T ) (this
is denoted by A (C (0)) C (T ) ).
2.2 Abstract state machines with stochastic behaviour
Let's refine the Definition 1 and Definition 2 for such algorithms that have sets of
states with some special structure.
Let's start refining with the following auxiliary definitions.
2 For two sets
A and B by f : A B a partial map from A into B is denoted. For a A
by f (a ) the clause " f ( a ) is defined" is denoted.
20 M. Alobaidi, A. Batyiev and G. Zholtkevych
Definition 3. Let N and A be finite sets of nodes and arcs respectively, dom and
codom be a maps that associate with arcs their initial and terminal nodes
respectively, then the tuple ( N , A, dom, codom) is called a directed multigraph.
Definition 4. Let G = ( N , A, dom, codom) be a directed multigraph, then an
alternating sequence = n 1, a 1, , a k , n k 1 of nodes and arcs, beginning and ending
with a node, is called a walk if for all s = 1, , k the next condition holds:
dom(as ) = ns and codom(as ) = ns 1 .
a1 ak
In this case we shall use the notation: n 1
n k 1 .
a1 ak
Definition 5. Let = n 1
n k 1 be a walk in the directed
multigraph G = ( N , A, dom, codom) and n be its node, then we shall say that
─ n is the initial node of (it is denoted by dom( ) = n ) if n = n1 ;
─ n is the terminal node of (it is denoted by codom( ) = n ) if n = nk 1 ;
─ traverses n if for some s {1, , k 1} the equality n = ns holds.
Definition 6. Let ( N , A, dom, codom, n0 , F ) be a tuple such that the
tuple ( N , A, dom, codom) is a directed multigraph, n0 is a fixed node (it is called the
initial node), F is a fixed subset of nodes(its elements are called terminal nodes). The
tuple is called a control graph if the next conditions hold:
─ n0 F ;
─ for each n F there is no arc with initial node equals n ;
─ for each node n there is a walk such that its initial node equals n0 , its terminal
node belongs to F , and it traverses n .
Note that for the control graph ( N , A, dom, codom, n0 , F ) and each n N \ F the
set Out(n) = {a A | dom(a) = n} is not empty.
Let's assume that for an arbitrary algorithm A the set of states has the next
structure C ( A) = N ( A) S ( A) where N ( A) is the nodes set of some control graph
G ( A ) and S ( A) is some set of memory snapshots.
In this case suppose that the set of initial states is the next set
I ( A) = {(n0 , S ) | S S ( A )} and the set of terminal states is the following set
T ( A) = {(n, S ) | n F & S S ( A)} .
This supposition leads us to the next representation of the map A :
A (n, S ) = ( A (n, S ), A (n, S )) , where A : N ( A) S ( A) N ( A)
(2)
and A : N ( A) S ( A) S ( A)
Towards the Notion of an Abstract Quantum Automaton 21
Suppose now that the map A has property of locality. It means that for each
n N ( A) \ F there exists a map hn : S ( A) Out(n) and for each a A( A) 3 there
exists a map g a : S ( A) S ( A) such that the following equalities are true:
A (n, S ) = codom(hn ( S )); (3)
A (n, S ) = g h ( S ) ( S ). (4)
n
From (2), (3), and (4) it follows
A (n, S ) = (codom(hn ( S )), g h ( S ) ( S )). (5)
n
Therefore, we can consider the computational process which is determined by the
algorithm A as a sequence of steps. Each step begins when the current state is
described by some control graph node n and a memory snapshot S . Then the map
hn chooses the arc a outgoing from the node n depending on the snapshot S .
Finally, using the selected arc and the memory snapshot the new control graph node
and the new memory snapshot are determined in compliance with (5).
Let's modify the computational model by rejecting the assumption about
determinacy for the choosing process. Definition 2.5 describes this modification
formally.
Definition 7. Let G = ( N , A, dom, codom, n0 , F ) be a control graph, S be some
set of memory snapshots, P = {Pr( | S , n) | n N \ F , S S} be a family of
probability distributions on A , and T = {g a | a A} be a family of maps from S
into itself then the tuple (G , S , P , T ) is called an abstract state machine with
stochastic behaviour if the following condition holds
for all n N , S S , a A if a Out(n) then Pr(a | S , n) = 0 . (6)
Dynamics of such machines is determined by the next definition.
Definition 8. Let (G , S , P , T ) be an abstract state machine with stochastic
behaviour, G = ( N , A, dom, codom, n0 , F ) be its control graph then a partial map
C : N N S is called a run of the machine if it satisfies the following conditions
─ C (0) = (n0 , S ) , where S S ;
─ if C (t ) for some t N then C (t ) for all t N such that t < t ;
─ if C (t 1) = (n, S ) for some t N and C (t ) = (n, S ) then there exists
a Out(n) such that Pr(a | n, S ) > 0 , n = codom(a ) , and S = g a ( S ) ;
─ if C (t ) = (n, S ) for n F and S S then C (t 1) = .
Below such machines will be generalised for the quantum case.
3 By
A( A ) is denoted the set of arcs for the control graph G ( A ) .
22 M. Alobaidi, A. Batyiev and G. Zholtkevych
3 Mathematical Model of Finite-Level Quantum Systems
In the section the model of quantum systems with finite quantity of levels (finite-level
quantum systems) is described. It is based on the approaches set forth in the
works [9, 13].
3.1 Postulates of finite-level quantum systems
The postulates of finite-level quantum systems fix basic notions which are used to
construct mathematical models for the systems.
Postulate 1: an n -dimensional Hilbert space H n is associated to any quantum
physical system with n levels. This space is known as the state space of the system.
The system is completely described by its pure state, which is a one-dimensional
subspace of the state space. This subspace is uniquely represented by the ortho-
projector on a vector which generates the subspace.
In contrast to pure states mixed states are used to describe quantum systems whose
state is not completely known.
Rather more detailed suppose we know that a quantum system is in one of a
number of states k k : k = 1, , m with respective probabilities
pk : k = 1, , m . We shall call pk , k k : k = 1, , m an ensemble of pure
states. The density operator for the system is defined by the equation
m
= pk k k .
k =1
We identify mixed states with density operators 4. Evidently, that each density
operator is a non-negative defined operator which trace is equal to unit. It is known
that the inverse statement is true: a non-negative defined operator, which trace is
equal to unit, is a density operator [9].
Of course, a one-dimensional ortho-projector is a density operator. The set of all
density operators is convex and its subset of one-dimensional ortho-projectors is the
subset of its extreme points [9]. This allows to consider pure states as indecomposable
states.
Postulate 2: the state space of a composite physical system is the tensor product of
the state spaces of the component physical systems. Moreover, if we have systems
indexed by k = 1, , m , and the state of the system with number k is described by
the density operator k , then the joint state of the total system before any interactions
is 1 m .
Postulate 3: the evolution of a closed quantum system is described by a unitary
transformation. That is, the state of the system at time t1 is related to the
4 The set of all density operators on the space
H n is denoted by Sn
Towards the Notion of an Abstract Quantum Automaton 23
state of the system at time t2 by a unitary operator U which depends only
on the times t1 and t2 , = U U .
If we have an ensemble of pure states of the system which is described by the
density operator at time t1 then the density operator of the system at time t2
can be calculated by the formula = U U .
Postulate 4: quantum measurements are described by an indexed finite family
K = K ( x) : x X of Kraus' operators, where X is a finite set. These are operators
acting on the state space of the system being measured. The index x refers to the
measurement outcome that may occur in the experiment. If the state of the quantum
system is described by the density operator immediately before the measurement
then the probability that result x occurs is given by the following formula 5
Pr x | = Tr K ( x) K ( x) (7)
and the state of the system immediately after the measurement is described by the
density operator
K ( x) K ( x)
Eff | x =
Tr K ( x) K ( x) (8)
Any Kraus' family K = K ( x) : x X satisfies the completeness condition
K ( x) K ( x) = 1 (9)
x X
which ensures correctness of the definitions given by formulas (7) and (8).
3.2 Measurements and isometric operators. Quantum operations
Postulate 3 and Postulate 4 describe two different ways of changing a system state. It
looks non-naturally. Hence, we can set the problem: find a unified description for
evolutions and measurements of a finite-level quantum system.
To solve the problem let's introduce for a state space H n of an n -level quantum
system and a finite set X operators J ( x ) : H n H n l 2 X by the formula
J ( x) = x (10)
where x l 2 X such that x ( ) = x, .
5 By
Tr() the usual operator trace is denoted
24 M. Alobaidi, A. Batyiev and G. Zholtkevych
Properties of operators from the family J ( x) : x X are established by the next
proposition, which is proved by the direct calculation.
Proposition 1. Let H n be a state space of an n -level quantum system and X be
a finite set, then the operators family J ( x) : x X defined by formula (10) satisfies
the next identities
J ( x) ( x) x = ( x) (11)
x X
J ( x) J ( x) = ( x, x) 1 (12)
J ( x) J ( x) = 1 x x (13)
Now using a Kraus' family K = {K ( x) : x X } for some measurement let's define
an operator WK : H n H n l 2 ( X ) by the formula
WK = K ( x) x (14)
x X
Proposition 2. Let K = K ( x) : x X be a Kraus' family, and WK be the
operator that is built by the formula (14), then WK is an isometric operator and the
next identities hold for all x X :
K ( x) = J ( x)WK (15)
Proof. Let | 0 , ,| n 1 be some orthonormal basis in H n , then for any
k = 0, , n 1 from (14) we have
WK k = K ( x) k x
x X
Hence,
n 1
WK = K ( x) k x k
k 0 x X
and
n 1
WK = k k K ( x) x
k 0 x X
Therefore,
Towards the Notion of an Abstract Quantum Automaton 25
n 1 n 1
WK WK = l
l 0
l K ( x) x k0 xX K ( x) k x k =
n 1 n 1
l l K ( x) K ( x) k x x k = K ( x) K ( x) k k
k ,l 0 x , x X k 0 x X
K ( x ) K ( x) .
x X
Using the completeness condition one can obtain that WK WK = 1 .
The last equation ensures that WK is an isometric operator.
Equation (15) is proved by the direct calculation:
J ( x)WK = J ( x) K ( x) x = K ( x) .
x X
Proof is complete.
Using Proposition 2 one can rewrite formulae (7) and (8) in the following way:
Pr x | = Tr WK WK 1 x x . (16)
J ( x)WK WK J ( x) (17)
Eff | x = .
Tr WK 1 x x WK
Now we claim that this construction can be inverted.
Really, let H n be a state space for an n -level quantum system, X be a finite set
of outcomes, and W : H n H n l 2 X be an isometric operator.
Let's define a family K = K ( x) : x X of operators on the space H n by the
formula
K ( x) = J ( x)W . (18)
Proposition 3. Let H n be a state space for an n -level quantum system, X be a
finite set of outcomes, W : H n H n l 2 X be an isometric operator, and
K = K ( x) : x X be the family of operators which is defined by formula (16); then
1. K satisfies the completeness condition and, therefore, it is a Kraus' family;
2. WK = W .
Proof. To prove the completeness condition let's calculate the left side of (9) using
(13) and the isometry property
K ( x) K ( x) = W J ( x) J ( x)W = W (1 | x x |)W = W W = 1 .
x X x X x X
26 M. Alobaidi, A. Batyiev and G. Zholtkevych
To prove the second statement let's calculate using (13)
WK | = K ( x) x = J ( x) K ( x) =
x X x X
J ( x) J ( x) W = J ( x) J ( x)W = 1 x x W = W .
x X x X x X
Proof is complete.
Proposition 2 and 3, formulae (16) and (17) substantiate replacing the Kraus'
families by the corresponding isometric operators under studying the interaction of
quantum systems with classical systems. This replacing leads us to unification of
Postulate 3 and Postulate 4. To stress such unification we will say that an isomeric
operator describes the quantum operation by formulae (16) and (17).
Definition 9. Let H n be a state space of an n -level quantum system, X be a
finite set of outcomes, then isometric operators W1 , W2 : H n H n l 2 X are
called equivalent if for all x X and for any density operator the following
equalities are true
Tr W1 1 x x W1 = Tr W2 1 x x W2 , (19)
J ( x)W1 W1 J ( x) = J ( x)W2 W2 J ( x) . (20)
Classes of this equivalence will be called quantum operations with a set of
outcomes X .
Easy to see that isometric operators W1 , W2 : H n H n l 2 X describe the same
quantum operation if J ( x)W2 = ei ( x ) J ( x)W1 for any : X [0, 2 ) .
We claim that the inverse statement is true too.
Theorem 1. Let H n be a state space of an n -level quantum system, X be a finite
set of outcomes, W1 , W2 : H n H n l 2 X be equivalent isometric operators then
J ( x)W2 = ei ( x ) J ( x)W1 for some : X [0, 2 ) .
Proof. It is evident, that each isometric operator Ws : H n H n l 2 X , where
s = 1, 2 , can be represented by the formula
n 1
Ws = k( s ) ( x) x
x X k 0
k, (21)
where {| 0 , ,| n 1} is an orthonormal basis in H n and k( s ) ( x ) = J ( x )Ws | k
for k = 0, , n 1 and x X .
Using representation (21) we calculate Pr x | k k for Ws where s = 1, 2 .
Towards the Notion of an Abstract Quantum Automaton 27
Pr x | k k Tr k k Ws 1 x x Ws = k | Ws (1 | x x |)Ws ) | k =
n 1
k Ws 1 x x l( s ) ( x) x
x X l 0
l k = k W ( x) x =
s
( s)
k
n 1
( x) x = ( x) .
2
k l l( s ) ( x) x (s)
k
(s)
k
x X l 0
Using this and identity (19) one can derive that for all k = 0, , n 1 and x X
the next equality holds
2 2
k(1) ( x) = k(2) ( x) (22)
Let I s ( x) = k | 0 k < n, k( s ) ( x) 0 for each x X and s = 0,1 . From (22) it
follows that I1 ( x) = I 2 ( x) , hence, we can denote this set by I ( x) .
From (20) one can derive that for all x X and k I ( x)
k(2) ( x) k(2) ( x) = k(1) ( x) k(1) ( x) . (23)
The next equality is obtained by multiplying equality (23) from left by k(1) ( x )
and from right by k(1) ( x ) and using equality (22):
2 2 2
k(2) ( x) k(1) ( x) = k(2) ( x) k(1) ( x) . (24)
From the (24) and (22) it follows that for all x X and k I ( x)
k(2) ( x) = ei ( k , x ) k(1) ( x) , where 0 (k , x) < 2 . (25)
Further, from (20) it follows that for all x X and k , l I ( x) the next equality is
true:
k(2) ( x) l(2) ( x) = k(1) ( x) l(1) ( x) .
Therefore,
ei ( ( k , x ) (l , x )) k(1) ( x ) l(1) ( x ) = k(1) ( x ) l(1) ( x )
and ei ( ( k , x ) (l , x )) = 1 .
In summary, we obtain the next equality for all x X and k I ( x)
k(2) ( x ) = ei ( x ) k(1) ( x) . (26)
28 M. Alobaidi, A. Batyiev and G. Zholtkevych
Using (24) for x X , k I ( x) and the equality l(2) ( x ) = l(1) ( x ) = 0 for
l {0, , n 1} \ I ( x) one can get that equality (26) is true for all 0 k < n .
Therefore, J ( x)W2 = ei ( x ) J ( x)W1 for some : X [0, 2 ) .
Corollary 1. Two isometric operators W1 , W2 : H n H n l 2 ( X ) define the same
quantum operation if and only if for some : X [0, 2 ) the following equality
holds W2 = W1 , where = 1 ei ( x ) x x .
x X
4 Abstract Quantum Automata
Now we describe some class of mathematical models for quantum information
processes. This class we call the class of abstract quantum automata.
4.1 The notion of an abstract quantum automaton
Definition 10. Let H m (m > 1) be a state space of an m -level quantum system, and
let G = ( N , A, dom, codom, n0 , F ) be a control graph. Suppose that each non-terminal
node n of the graph G is connected with a quantum operation for which H m is the
state space, Out(n) is the outcomes set, and Wn : H m H m l 2 Out( n) is an
isometric operator describing the operation. Then the tuple
( H m , G ,{Wn | n N \ F })
is called an abstract quantum automaton.
The next definition describes the set of runs for an abstract quantum automaton
similarly to Definition 8.
Definition 11. Let ( H m , G ,{Wn | n N \ F }) be an abstract quantum automaton
where the control graph G is equal to ( N , A, dom, codom, n0 , F ) . Then a partial map
C : N N Sm is called a run of the automaton if it satisfies the following
conditions
─ C (0) = (n0 , ) , where Sm ;
─ if C (t ) for some t N then C (t ) for all t N such that t < t ;
─ if C (t 1) = (n, ) for some t N and C (t ) = (n, ) then there exists
a Out(n) such that
Pr a | n, = Tr Wn 1 a a Wn > 0 , n = codom(a ) ,
Towards the Notion of an Abstract Quantum Automaton 29
J (a )Wn Wn J (a )
and = Eff | n, a = ;
Pr a | n,
─ if C (t ) = (n, ) for n F and Sm then C (t 1) = .
Now we can consider two important examples.
Let's consider a quantum information process which sets a qubit (2-level quantum
system) into the state 0 0 .
Evidently, that this problem can not be solved by any unitary transformation.
We shall specify an abstract quantum automaton that does it. The control graph of
the automaton is shown in Fig. 1.
Fig. 1. Qubit cleaner.
As one can see Out(m) = {0,1} . Let's define Wm : H 2 H 2 l 2 0,1 by the
formula
Wm = 0 0 0 1 1 1 .
Further, Out( f ) is a singleton hence W f : H 2 H 2 . Let's define
Wf = 0 1 1 0 .
Easy to see that for an arbitrary initial state of a qubit its state after handling by the
automaton is equal to 0 0 .
Therefore, we have built the abstract quantum automaton that specifies the process
of cleaning a qubit.
The next example deals with preparing an entangled pair of qubits. We shall
specify an abstract quantum automaton that does it.
The control graph of the automaton is shown in Fig. 2.
Let's define Wh : H 2 H 2 H 2 H 2 by the formulae
1
Wh 0 = 0 1 ,
2
30 M. Alobaidi, A. Batyiev and G. Zholtkevych
1
Wh 1 = 0 1 ,
2
and define Wc : H 2 H 2 H 2 H 2 by the formulae
Wc 0 = 0 ,
Wc 1 = 1 0 | 1 0 1 | 1 .
Fig. 2. Preparing an entangled pair of qubits.
Easy to see that for an arbitrary initial state of a qubit pair its state after handling
by the automaton is equal to
1
2
0 0 1 1 0 0 1 1 .
These examples demonstrate that modelling of quantum information processes by
abstract quantum automata allows to describe processes of initial preparation of a
quantum memory for quantum computing devices.
4.2 Quantum teleportation as an abstract quantum automaton
To complete the paper let's consider the quantum teleportation process and let's show
that it can be described by an abstract quantum automaton.
Quantum teleportation is a process by which a qubit state can be transmitted
exactly from one location to another, without the qubit being transmitted through the
intervening space. This phenomenon has been confirmed experimentally [1, 2].
The control graph of the automaton is shown in Fig. 3.
Let's define Wc : H 2 H 2 H 2 H 2 H 2 H 2 , where the first qubit is
Alice's qubit, the second and the third qubits are the first and the second qubits of the
entangled pair respectively, by the formulae
Wc 0 k = 0 k , where k 0,1 ,
Wc 1 0 = 1 1 ,
Towards the Notion of an Abstract Quantum Automaton 31
Wc 1 1 = 1 0 .
Further, Out(m) = {00, 01,10,11} and the corresponding isometric operator is
defined by formulae
Wm 0 0 = 0 0 00 ,
Wm 0 1 = 0 1 01 ,
Wm 1 0 = 1 0 10 ,
Wm 1 1 = 1 1 11 .
Fig. 3. Teleportation
By direct calculation one can prove that the initial state for an
arbitrary S4 is transformed by the automaton into the state
1
4
0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 .
Conclusion
Summarising the above we can conclude:
─ our attempt to solve the Yu. Manin's problem led us towards the notion of an
abstract quantum automaton;
─ this notion is based on a computational model known as a machine of A.
Kolmogorov and V. Uspensky;
32 M. Alobaidi, A. Batyiev and G. Zholtkevych
─ abstract quantum automata can be used for formal specification of quantum
information processes including non-invertible processes like qubit cleaning,
entangled pair preparing and quantum teleportation.
The authors know that quantum algorithms can be specified by using abstract
quantum automata but corresponding results are not given in the paper because they
are cumbersome.
References
1. Bouwmeester, D., Pan, J.--W., Mattle, K., Eible, M., Weinfurter, H., Zeilinger, A.:
Experimental quantum teleportation. Nature, 390, 575 -- 579 (1997)
2. Boschi, D., Branca, S., De Martini, F., Hardy, L., Popescu, S.: Experimental Realization of
Teleporting an Unknown Pure Quantum State via Dual Classical and Einstein--Podolsky--
Rosen Channel. Phys. Rev. Lett., 80, 1121 -- 1125 (1998)
3. Church, A.: An unsolvable problem of elementary number theory. Amer. J. Math., 58(2),
345 -- 363 (1936)
4. Feynman, R.P.: Simulating Physics with Computer. Int. J. Theor. Phys., 21, 467 -- 488
(1982)
5. Feynman, R.P.: Quantum Mechanical Computers. Found. Phys., 16, 507 -- 531 (1986)
6. Fortnow, L., Homer, S.: A Short History of Computational Complexity. Bull. EATCS, 80,
95 -- 133 (2003)
7. Gurevich, Y.: Evolving Algebras 1993: Lipari Guide, E. Börger (ed.) Specification and
Validation Methods. Oxford University Press, 9 -- 36 (1995)
8. Gurevich, Y.: Sequential Abstract State Machines capture Sequential Algorithms. ACM
Trans. Comp. Logic, 1, 77 -- 111 (2000)
9. Holevo, A.S.: Probabilistic and Statistical Aspects of Quantum Theory. North-Holland
Publishing Company, Amsterdam (1982)
10.Kolmogorov, A.N., Uspensky, V.A.: On the Definition of an Algorithm. AMS Transl., ser.
2, 21, 217 -- 245 (1963)
11.Manin, Yu.I.: Computable and Uncomputable (Cybernetics), (in Russian). Sovetskoe radio,
Moscow (1980)
12.Manin, Yu.I.: Mathematics as metaphor: selected essays of Yuri I. Manin. AMS (2007)
13.Nielsen, M.A. and Chuang, I.L.: Quantum Computation and Quantum Information.
Cambridge University Press, Cambridge (2000)
14.Post, E.L.: Finite Combinatory Processes -- Formulation 1. J. Symb. Logics, 1(3), 103 -- 105
(1936)
15.Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem.
Proc. Lond. Math. Soc., 2(42), 230 -- 265 (1936)
16.Turing, A.M.: Computability and -Definability. J. Symb. Logics, 2(4), 153 -- 163 (1937)
17.White, S.: A Brief History of Computing. http://trillian.randomstuff.org.uk/stephen/history/