ЯДЕРНАЯ ФИЗИКА, 2011, том 74, № 7, с. 1069-1074
= ЭЛЕМЕНТАРНЫЕ ЧАСТИЦЫ И ПОЛЯ
REGULAR METHOD OF CONSTRUCTION OF THE REVERSIBLE DYNAMICAL SYSTEMS AND THEIR LINEAR EXTENSIONS - QUANPUTERS
©2011 N. V. Makhaldiani*
Joint Institute for Nuclear Research, Dubna, Russia Received July 19,2010
Quantum computers are considered as a part of the family of the reversible, linearly extended, dynamical systems — Quanputers. Original method of construction of the quanputers is given. Application of this method for finite- and infinite-dimensional systems is shown. New (de)coherence criterion is formulated.
1. INTRODUCTION
Computers are physical devices and their behavior is determined by physical laws. The Quantum Computations [1, 2], Quantum Computing, Quan-puting [3], is a new interdisciplinary field of research, which benefits from the contributions of physicists, computer scientists, mathematicians, chemists, and engineers.
The quantum many-body system (QMBS) is the important mathematical model for description of physical systems of condensed state physics, quantum chemistry, biochemistry. QMBS cannot be solved exactly, computationally exactly, i.e. with controllable approximations and required precision on classical computers as the size of the state space of the system grows exponentially with the number of particles. QMBS may be simulated on a Quanputers, with polynomially rising resources with the system size.
Quanputers can help also in the solution of basic problems of computer science, such as the prime-factorization problem, for which Quanputing provides an exponential speedup with respect to any known classical computation [4]. Today, cryptographic schemes extensively used such as RSA are based on the conjecture that, given a composite odd positive integer, it is hard to find its prime factors; hence a large scale Quanputer, if constructed, would break the RSA encryption scheme. For some problems, e.g., searching a marked item in an unstructured database, Quanputing leads to an algebraic speedup [5].
The standard model of quanputers (SMQ) based on the finite-dimensional state space, can be simulated on the classical Turing machine, so the class
E-mail: mnv@jinr.ru
of problems solvable on the finite-dimensional quan-puters and on the classical computers are the same. Infinite-dimensional quantum state space quanput-ers and quanputers based on nonlinear quantum theories may have other possibilities.
The power of quanputing is in their inherent quantum parallelism associated with the superposition principle. A quanputer can process a large number of classical inputs in a single run. This implies also a large number of possible outputs, and the task of the algorithms for quanputers is to find desired output effectively using the quantum parallelism.
The superposition principle for quanputers can be (slightly) violated, dynamics of quanputers can be (slightly) nonlinear. With these quanputers the classes of problems NP and # P (including oracle problems) may be solved in polynomial time [6].
The NP class is the set of problems for which, once given a potential answer, one can determine in polynomial time if the potential answer is in fact a solution. These include all problems in the P class, those that can be solved in polynomial time, as well as the NP-complete problems (those to which reduce other NP problems in polynomial time, i.e. universal NP problems), e.g., the traveling salesman, satisfiability, and sub-graph isomorphism, for which no known polynomial time algorithms exist [7].
Note that, in the standard perturbation theory, the number of diagrams with the number of loops n rise as n!; the finite-dimensional, singular, integral corresponding to a given diagram also become more complicated, so usual algorithms of calculations are not polynomial. It is important that there are alternative algorithms, string-inspired algorithms, for which in each perturbative order we have just one diagram, which already contains contribution of n! diagrams of Quantum Field Theory (QFT)!
This is an important example from the higher-energy theoretical physics, where nonpolynomial computational problem was transformed to the polynomial one by modification of the problem, when we take string theory regularization of the QFT, or by string-inspired perturbation theory instead of the ordinary one [8].
2. DISCRETE DYNAMICAL SYSTEMS
Contemporary digital computer and its logical elements can be considered as a spatial type of discrete dynamical systems [9]
Sn (k + 1) = $n(S (k)), (1)
where
Sn(k), 1 < n < N (k),
(2)
is the state vector of the system at the discrete time step k. Vector S may describe the state and $ transition rule of some Cellular Automata [10]. The systems of the type (1) appears in applied mathematics as an explicit finite difference scheme approximation of the equations of the physics [11].
Definition: We assume that the system (1) is time-reversible if we can define the reverse dynamical system
Sn(k) = $-1(S (k + 1)). (3)
In this case the following matrix
d$n(S (k))
Mnm —
dSm(k)
(4)
is regular, i.e. has an inverse. If the matrix is not regular, this is the case, for example, when N(k + 1) = N(k), we have an irreversible dynamical system (usual digital computers and/or corresponding irreversible gates).
Let us consider an extension of the dynamical system (1) given by the following action function
A = ln(k)(Sn(k + 1)- $n(S(k))) (5)
kn
and corresponding motion equations Sn(k + 1) = $n(S (k)) =
ln (k - 1) = lm(k)
dH
dln (к)' d<S>m(S(k)) =
dSn(k)
— lm (k)Mmn(S (k)) —
dH
dSn(k):
where
H — ^ L(k^n(S(k))
is discrete Hamiltonian. In the regular case, we put system (6) in an explicit form
Sn (k + 1) = $n(S (k)), (8)
ln (k + 1) = lm (k)M-n (S (k + 1)).
From this system it is obvious that, when the initial value ln(k0) is given, the evolution of vector l(k) is defined by evolution of the state vector S(k). The equation of motion for ln(k) — linear and has an important property that a linear superpositions of the solutions are also solutions.
Statement: Any time-reversible dynamical system (e.g., a time-reversible computer) can be extended by corresponding linear dynamical system (quantum-like processor) which is controlled by the dynamical system and has a huge computational power [3, 9, 12].
Continual Time Approximation
In the continual time approximation, the discrete system (8) reduces [9] to a corresponding continual one [13, 14]:
dv
Xn(t) = Vn{x), pn(t) = (9)
UXn
Indeed, let us change the dependent variables,
Sn(k) = Xn(tk), ln(k) = Pn(tk), (10) tk = kT, T ^ 1.
Then the action functional (5) can be transformed as follows:
A — J2 Pn (tk )(xn (tk + T) - §n(x(tk))) ^ (11)
TPn(tk)(Xn(tk) - Vn(x(tk))) ^
i
^ j dtpn(t)(xn - Vn(x)),
kn
(6)
(7)
where
Vn(x(tk)) = ($n(x(tk)) - Xn(tk))/t (12)
and corresponding motion equations are presented by system (9). System (9) is Hamiltonian,
Xn = {Xn ,H}, pn = {pn,H}, (13)
with Hamiltonian and canonical Poisson bracket
H = ^ PnVn(X), {Xn, Pm} = Km. (14)
kn
n
REGULAR METHOD OF CONSTRUCTION ...
1071
3. INFINITE-DIMENSIONAL DYNAMICAL SYSTEM
For the following (infinite-dimensional) equation of motion [15]
iVt = AV- ¿V2,
i^t = -A^ + V
A = / dtdaxV iVt - AF + - V'
(15)
the corresponding linear subsystem is nothing but the familiar Schrodinger equation,
= J dtddxV \^iipt - A^ + Vrip + -(»'
Corresponding motion equations are
i^t = -A^ + Vr ^ + VV,
(21)
(16)
The extended system
iVt = AV-^V2, itPt = -AiP + V'iP, (17)
can be obtained from the following action functional
1
(18)
and is mathematically and physically complete, as potential is not an external function, but is part of the Hamiltonian dynamical model [15],
iVt = {V(t,x),H}, i^t = {*(t,x),H}, (19)
H = J ddx^(t, x) [~AV{t, x) + , Mt,x),V(t,y)} = 5d(x - y).
For each solution of the pre-potential equation, for each potential Vr, we have corresponding quantum mechanics (in linear approximation) and (approximate) conservation of the probability (current-charge). Such a theory which unifies different string theories was named as M theory (see, e.g., [ 16]). Our model is a toy M theory for quantum mechanics. Here we can ask and obtain answer in the simpler case on the questions of M theory. Note that string M theory is not constructed yet, our model gives an explicit example of realization of M-theory idea.
4. DISCRETE (SPACE-)TIME APPROXIMATION
If we take discrete time derivative in the action (18),
Vt
V (kr + r, x) - V (kr,x)
(22)
Pre-Potential, (Non)Conservation of the Probability Current or Charge and Toy M Theory
Let us take some solution of the equation of the "Pre-potential" V, Vr, and change variable as
V = Vr + V, (20)
A = f dtddxtf (iVt — AV + lv2 ) =
we obtain the following infinite-dimensional discrete time dynamical model
A = Î dd x^ V(k,x)(V (k + l,x) k
- $(V(k,x), AV(k,x))). If we take also discrete space derivative
(23)
AV(k,x) ^
m=l
V(k, ni,...,nm + l,...,nd)- 2 V(k, n) + V(k, m,..., nm - 1,..., nd)
h2
V(k,n) ^ ln(k), V(k,n) ^ Sn(k),
(24)
we will have a model of type (1).
5. (DE)COHERENCE CRITERION
Let us consider motion equations (6). In the continual approximation, we have
(k + 1)= xn(tk + t ) = (25)
= xn(tk) + x,n(tk )t + O(T2),
x n(tk )= Vn (x(tk )) + O(r ), tk = kr, Vn(x(tk)) = ($n(x(tk)) - xn(tk))/r;
pvm (x(tk ))
Mmn(x(tk)) = L + t-
dxn(tk )
(De)Coherence criterion: The system is reversible, the linear (quantum, coherent, soul)
ftŒPHAfl OH3HKA tom 74 № 7 2011
subsystem exists, when the matrix M is regular,
dvn
(26)
For the Nambu—Poisson dynamical systems (see, e.g., [17])
Vn(x) = e
dHi dH2 dHp
nmi m2...m,p
dxmi dxm2
dXm
(27)
P = 1, 2, 3
dvn dxn
£
,N - 1, = divv = 0.
6. CONSTRUCTION OF THE REVERSIBLE DISCRETE DYNAMICAL SYSTEMS
Let me motivate an idea of construction of the reversible dynamical systems by a simple example from field theory. There are renormalizable models of scalar field
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.