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.

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 monograph 1 [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 N e 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.

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 [10]. Theory of abstract state machine (ASM) is the further development of the approach [7,8].

Preliminary definitions( ) ( ) = .  I T  A 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 C N A 2 is called a run of the algorithm if it satisfies the following conditions ─ (0) ( );  I C A ─ if ( )   C t for some  N t then ( )    C t for all   N t such that < ;  t t ─ if ( 1)    C t for some  N t then ( 1) = ( ( ))  C t C t  A ; ─ if ( ) ( )   T C t A then ( 1) =   C t .

From this definition it follows immediately that the domain of an arbitrary run is the set N or some set 0 ..

= { | }   N T t t T

, where T is a non-negative integer. In the first case the algorithm diverges on the initial state (0) C (this is denoted by

( (0))  C A

).

In the second case the algorithm converges on the initial state (0)

C to ( ) C T (this is denoted by ( (0)) ( )  C C T A

).

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.

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 ( , , dom, codom) In this case we shall use the notation:

N1 1 1     a a k k n n  . Definition 5. Let 1 1 1 =     a a k k n n   be a walk in the directed multigraph = ( , ,dom,codom) G N A

and n be its node, then we shall say that

─ n is the initial node of  (it is denoted by dom( ) = n  ) if 1 = n n ; ─ n is the terminal node of  (it is denoted by codom( ) = n  ) if 1 =  k n n ; ─  traverses n if─ 0  n 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 0 n , its terminal node belongs to F , and it traverses n .

Note that for the control graph 0 ( , , dom, codom, , )

N A n F and each \  N n F the set Out( ) = { | dom( ) = }  A n a

a n is not empty. Let's assume that for an arbitrary algorithm A the set of states has the next structure ( ) = ( )

( )  C N S A

A 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

0 ( ) ={( , ) | ( )}  I S n S S A A

and the set of terminal states is the following set

( ) ={( , ) | & ( )}   T S n S n F S A A.

This supposition leads us to the next representation of the map  A :

( , ) = ( ( , ), ( , )) n S n S n S    A A A

, where :

( ) ( ) ( )   N S N  A A A A and : ( ) ( ) ( )   N S S  A A A A(2)

Suppose now that the map  A has property of locality. It means that for each ( , ) = codom( ( ));

( ) \  N n F An n S h S  A (3) ( ) ( , ) = ( ). h S n n S g S  A(4)

From ( 2), (3), and (4) it follows

( ) ( , ) = (codom( ( )),( ))

.

n h S n n S h S g S  A(5)

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 n h 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

─ if ( )   C t for some  t N then ( )    C t for all   t N such that <  t t ; ─ if ( 1) = ( , )      C t n S for some  t N and ( ) = ( , ) C t n S then there exists Out( )  a n such that Pr( | , ) > 0 a n S , = codom( )  n a, and = ( )  a S g S ; ─ if ( ) = ( , )   C t n S for  n F and  S S then ( 1) =   C t .

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 .

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].

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 orthoprojector   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  

: = 1, , k k k m    with respective probabilities   : =1, , k p k m  . We shall call   , : =1 , , k k k p k m    an ensemble of pure

states. The density operator for the system is defined by the equation

=1 =  m k k k k p    .

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 = 1, , k 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

  = ( ):  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 formula5

    Pr | = Tr ( ) ( )  x K x K x  (7)

and the state of the system immediately after the measurement is described by the density operator

    ( ) ( ) Eff | = Tr ( ) ( )   K x K x x K x K x   (8)

Any Kraus' family

  = ( ):  K K x x X satisfies the completeness condition ( ) ( ) =    x X K x K x 1(9)

which ensures correctness of the definitions given by formulas ( 7) and (8).

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

  2 ( ) :   H H n n J x l X by the formula ( ) =  J x x  (10)

where

  2  x l X such that   ( ) = ,   x x  .

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   ( ) ( ) = ( )       x X J x x x x  (11)( ) ( ) = ( , )       J x J x x x  1 (12) ( ) ( ) =       J x J x x x 1(13)

Now using a Kraus' family = { ( ) : }  K K x x X for some measurement let's define an operator 2 : ( )

  K H H n n W l X by the formula = ( )      K x X W Kx x  (14)Proposition 2. Let   = ( ):  K K x

x X be a Kraus' family, and K W be the operator that is built by the formula ( 14), then K W is an isometric operator and the next identities hold for all 

x X :

( ) = ( )  K K x J x W (15) Proof. Let | 0 , ,| 1    n 

be some orthonormal basis in H n , then for any = 0, , 1

 k n  from (14) we have = ( )      K x X W k K x k x Hence,   1 0 = ( )          K n k x X W Kx k x k and   1 0 = ()            K n k x X W k kKx x Therefore,     1 1 0 0 = ( ) ( ) =                                    K K n n l k x X W W l l K x x K x k x k 1 1 , 0 , 0 ( ) ( ) = ( ) ( )                       n n k l x x X k x X l l K x K x k x x k K x K x k k ( ) ( )      x X K x K x .

Using the completeness condition one can obtain that =

 K K W W 1 .

The last equation ensures that K

W is an isometric operator. Equation ( 15) is proved by the direct calculation:

  ( ) = ( ) ( ) = ( )        K x X J x W J x K x x K x   .

Proof is complete. Using Proposition 2 one can rewrite formulae ( 7) and ( 8) in the following way:

      Pr | = Tr   K K x W W x x   1 . (16)       ( ) ( ) Eff | = Tr     K K K K J x W W J x x W x x W    1 . (17)

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

  2 :   H H n n

W l 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,

  2 :   H H n n

W l 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. = K W W .

Proof. To prove the completeness condition let's calculate the left side of ( 9) using ( 13) and the isometry property

( ) ( ) = ( ) ( ) = ( | |) = =              x X x X x X K x K x W J x J x W W x x W W W 1 1 .

To prove the second statement let's calculate using ( 13)

  | = ( ) = ( ) ( ) =       K x X x X W Kx x JxKx          ( ) ( ) = ( ) ( ) = =          x X x X x X J x J x W J x J x W x x W W     1 .

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

  2 1 2 , :   H H n n W W l X are called equivalent if for all 

x X and for any density operator  the following equalities are true

        1 1 2 2 Tr = Tr     W x x W W x x W   1 1 ,(19) 1 1 2 2 ( ) ( ) = ( ) ( )    J x W W J x J x W W J x   .(20)

Classes of this equivalence will be called quantum operations with a set of outcomes X .

Easy to see that isometric operators

  2 1 2 , :   H H n n W W l X describe the same quantum operation if ( )2 1

( ) = e ( )

  i x J x W J x W  for any : [0,2 )  X 

 . 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,

  2 1 2 , :   H H n n W W l X be equivalent isometric operators then ( )2 1 ( ) = e ( )  i x J x W J x W  for some : [0,2 )  X   . Proof. It is evident, that each isometric operator   2 :   H H s n n W l X , where = 1, 2 s

, can be represented by the formula

  1 ( ) 0 = ()       n s s k x X k W x x k  ,(21)

where {| 0 , ,|

   n  is an orthonormal basis in H n and ( ) ( ) = ( ) |   s s k x J x W k  for = 0, , 1  k n  and  x X .1 }

Using representation (21) we calculate  

Pr | x k k for s W where = 1, 2 s .       Pr | Tr = | ( | |) ) | =          s s s s x k k k k W x x W k W x x W k 1 1       1 ( ) ( ) 0 ( ) = ( ) =             n s s s s l k x X l k W x x x x l k k W x x   1   1 2 ( ) ( ) ( ) 0 ( ) ( ) = ( )         n s s s l k k x X l k l x x x x x    .

Using this and identity (19) one can derive that for all = 0, , 1

 k n  and  x X the next equality holds 2 2 (1)(2)

( ) = ( )

k k x x   (22) Let   ( ) ( ) = | 0 < , ( ) 0   s s k I x k k n x  for each  x X and = 0,1 s . From (22) it

follows that 1 2 ( ) = ( ) I x I x , hence, we can denote this set by ( ) I x . From (20) one can derive that for all 

x X and ( )

 k I x (2)(2) (1) (1) ( ) ( ) = ( ) ( )k k k k x x x x     . (23)

The next equality is obtained by multiplying equality (23) from left by (1) ( ) k x  and from right by (1) ( ) k x  and using equality (22):

2 2 2 (2) (1) (2) (1) ( ) ( ) = ( ) ( )  k k k k x x x x     . (24)

From the (24) and ( 22) it follows that for all  x X and ( )

 k I x (2) (1) ( , ) ( ) = e ( ) i k x k k x x    , where 0 ( , )< 2  k x   . (25)

Further, from (20) it follows that for all  x X and , ( )  k l I x the next equality is true:

(2) (2) (1)(1)( ) ( ) = ( ) ( ) k l k l x x x x     .

Therefore,

(1) ( ( , ) ( , )) e () ()= () ()

 i k x l x k l k l x x x x       and ( ( , ) ( , )) e = 1  i k x l x  

. In summary, we obtain the next equality for all 

x X and ( )

 k I x (2) (1) ( ) ( ) = e ( ) i x k k x x    . (26)

Using (24) for  x X , ( )  k I x and the equality (2) (1)

( ) = ( ) = 0 l l x x   for {0, , 1} \ ( )   l n I x 

one can get that equality (26) is true for all 0 <  k n. Therefore,

( )2 1

( ) = e ( )

  i x J x W J x W  for some : [0,2 )  X   .

Corollary 1. Two isometric operators

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.

(0) = ( , ) C n  , where  m  S ; ─ if ( )   C t for some  t N then ( )    C t for all   t N such that <  t t ; ─ if ( 1) = ( , )      C t n  for some  t N and ( ) = ( , ) C t n  then there exists Out( )  a n such that       Pr | , = Tr > 0   n n a n W a a W   1 , = codom( )  n a,

and

    ( ) ( ) = Eff | , = Pr | ,    n n J a W W J a n a a n     ; ─ if ( ) = ( , )   C t n  for  n F and  m  S then ( 1) =   C t .

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. :

 H H f W . Let's define = 0 1 1 0  f W    .

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.

    1 0 = 0 1 2    h W   ,     1 1 = 0 1 2    h W   ,

and define Easy to see that for an arbitrary initial state of a qubit pair its state after handling by the automaton is equal to

    1 0 0 1 1 0 0 1 1 2       .

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.

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 , 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

  0 =0     c W k k   , where 0,1  k ,   1 0 = 1 1     c W   ,   1 1 = 1 0     c W   .

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;