INTRODUCTION
The biological aspects considered to imitate natural mechanisms governing the
macroscopic world span from the human brain to the behavior of swarms, as for
instance that of ant colonies. Taking as inspiration the macroscopic world,
the solutions are individuals belonging to a population. Their number is only
a small fraction of the entire set of possible individuals. These individuals
can be represented by points in a suitable space, the solution space. The bioinspired
mechanisms of optimization move the population in this space by specific interactions
among the individuals for exploitation and exploration of all the possible alternatives
(Goldberg, 1989; Eberhart et al.,
2001; Hassan et al., 2005; Panella,
2011).
A completely different situation characterizes the microscopic world governed
by quantum mechanics. All the possible solutions exist simultaneously in a superposition
and the determination of the optimal one is a problem of extracting it from
the superposition. Hence, to mimic nature in this case requires applying basic
mechanisms of quantum mechanics, i.e. the tools that nature exploits for attaining
optimal solutions: superposition and entanglement. As a consequence of this,
the evolutionary strategy must be replaced by a different one, passing from
the macroscopic to the microscopic world, in such a way that the quantum approach
can be considered as a microscopic natureinspired strategy. A proof is given
in the paper that the new strategy corresponds to an exhaustive search of the
optimal solution.
It should be emphasized that quantum computing is presently not supported by
sufficient technological achievements and there are serious difficulties of
physical feasibility. Emerging technologies in this regard are those based on
superconducting loops, cavity quantum electrodynamicsQED and, above all, ion
traps, nuclear magnetic resonance, silicon spintronic and phosphorousinsilicon
systems (Gershenfeld and Chuang, 1997; Stick
et al., 2006; Das, 2011a, b).
In spite of this inconvenience, quantum processing is partially imitated since
it is widely believed that the exploitation of quantum principles is very useful
for increasing the efficacy of the algorithms to be applied to information processing.
Consequently, the quantum inspiration has been frequently followed for improving
classical stochastic algorithms. There are very numerous contributions in the
technical literature in this regards, labeled either with the correct label
‘quantuminspired’ or simply with the label ‘quantum’. The
resulting algorithms however do not fully exploit the inherent power of quantum
processing. Two clear examples in this direction are respectively the quantum
neural (QNN) and quantum neurofuzzy networks (QNF) (Ventura,
1998; Narayanan and Menneer, 2000; Ezhov
and Ventura, 2000; Gupta and Zia, 2001; Ricks
and Ventura, 2003) as well as Quantum Evolutionary Algorithms (QEA) (Han
and Kim, 2000, 2002; Giraldi et
al., 2004). This partial exploitation of quantum processing power is
still present in the recent technical literature, as clearly evidenced by Abs
da Cruz et al. (2007), Platel et al. (2009),
Huo et al. (2010), Yanguang
et al. (2010), Mani and Patvardhan (2010),
Nie et al. (2010), Abs da
Cruz et al. (2010), Lu and Juang (2011),
Mukherjee et al. (2011) and Ibrahim
et al. (2011, 2012).
However, also if quantum technology is still far from actual application, it
is necessary to be ready to fully exploit its power. This remark motivates the
development of the few contributions recently devoted to the fully exploitation
of quantum computing (Panella and Martinelli, 2007,
2009, 2011; Fan
et al., 2008; Malossini et al., 2008;
Xiao et al., 2010; Zhang,
2011; Dong et al., 2012). Particularly interesting
are the algorithms proposed in the case of QNN’s and QNF’s based on
the use of both linear and nonlinear quantum operators. The use of the nonlinear
operators is mandatory to an exhaustive optimization process. In fact, a new
methodology is proposed in this paper in order to design a hardware architecture
consisting of a suitable number of linear and nonlinear quantum gates which
is able to solve the basic problems related to optimization (Goldberg,
1989; Panella, 2012).
QUANTUM ARCHITECTURES FOR THE EXHAUSTIVE OPTIMIZATION OF A PROBLEM
Exhaustive optimization of a problem is carried out by considering all its
possible solutions and by determining the one(s) scoring the best performance.
The number of possible solutions of a problem is however very large and hence,
the consideration of all of them cannot be undertaken with a reasonable computational
cost by applying the optimization procedures available outside the quantum world.
Exhaustive optimization is instead feasible by pursuing the inherent properties
of quantum mechanics where suitable quantum operators are involved, each corresponding
to welldefined set of physical quantum gates. In the present study this possibility
is proved by developing a suitable quantum hardware architecture; it consists
of a set of linear and nonlinear quantum gates connected among them for achieving
the said goal of exhaustive optimization. The structure of the proposed quantum
architecture will be successively justified in the study.
It is important to notice that, in the case of a specific problem, there are
several ancillary operations to be necessarily undertaken in order to exploit
the proposed architecture for the exhaustive optimization of the problem. These
operations depend on the problem of interest and constitute a relevant portion
of the entire computational procedure. No general rules can be devised in this
regard because of the excessive diversity of situations arising in the field
of information processing. In order to clarify this point, a specific problem
is focused is the following by considering in this case the entire procedure.
Nonetheless, most of the optimization problems faced in the field of information
processing can be eventually reduced to find the maximum (minimum) in a set
of positive integers, each constituted by a suitable string of bits. These integers
represent the performances obtained in relation with all the possible solutions
of a problem of interest. Hence, the exhaustive optimization of the latter requires
the determination of the maximum (minimum) of the said integers. Taking into
account this remark, the following three points should be focused:
• 
The problem of interest must be tailored to the rules of quantum
processing. Namely, the problem of interest must be formulated in terms
of Boolean variables and Boolean functions by using suitable strings of
bits. A particular attention should be addressed to the choice of the number
of bits required for attaining an acceptable accuracy (Papageorgiou
and Traub, 2005) 
• 
All the solutions of the problem of interest along with their
performances must be known simultaneously. This result is obtained by exploiting
the superposition and entanglement properties of quantum processing. In
this regard it is necessary: 

• 
To implement a Boolean function for determining the performance
corresponding to a solution under the form of a positive integer 

• 
To map the previous Boolean function into the quantum field. This is always
possible by means of linear quantum gates (Rieffel and
Polak, 2000). A quantum operator is hence obtained for performing this
task 

• 
To map the Boolean representation of solutions, i.e., M strings of a suitable
number of bits each representing a solution of the problem of interest,
in a quantum superposition S〉 of a same number of qubit strings 

• 
To apply the previously obtained quantum operator to S〉 so that
a new superposition S, P〉 is generated, being P〉 the superposition
entangled to S〉 containing the performances scored by the M solutions
present in S〉. It is important to point out that M is very large in
order to explore exhaustively the solution space and that, if the M performances
take on almost M distinct values, each performance should be represented
by a string of λ qubits where λ is on the order of log_{2}
M. However, this is not the practical case, since the performances do not
need to be represented with high accuracy. Consequently, λ is usually
much less than log_{2} M 
• 
The optimal solution corresponds to the maximum (minimum)
item in the superposition P〉. Its determination must be performed
at a reasonable cost. The latter condition rules out previous quantum algorithms
available in the technical literature, as those suggested in study of Durr
and Hoyer (1998), which is based on linear quantum operators only. They
in fact require a computational cost on the order of .
This cost is too large for undertaking an exhaustive search of the optimum.
A possible quantum architecture for carrying out this job is successively
described in the paper; it has a computational cost equal to O(λ) where,
as said, it is also possible to obtain λ<<log_{2} M without
actually impairing the results available by the exhaustive search of all
the solutions. 
SOME BASIC QUANTUM GATES AND OPERATORS
For what previously introduced, this study focuses on the algorithms that allow
obtaining the solution of a problem by a suited sequence of logical (Boolean)
operators. The corresponding architectures of quantum circuits are considered
as well, in particular the methodology for determining a suited topology by
using wellknown mappings of Boolean functions into the quantum field. This
is confirmed by the proposed quantum network successively illustrated.
By the way, it is worth summarizing some notations, definitions and properties,
as they will be used in the following of the paper. They are regarding to the
processed quantum data and the linear and nonlinear quantum gates and operators.
More details about basic concepts can be found, for instance, in the study by
Rieffel and Polak (2000):
• 
Data: The data to be handled are strings of qubits
(quantum bits) which play the same role as bits of the classical logic circuits.
A qubit is a unit vector in a two dimensional complex vector space. Unlike
classical bits, qubits are in superposition of 0〉 and 1〉 as
(a0〉+b1〉), where a and b are complex numbers such that a^{2}+b^{2}
= 1. If the qubit is measured, the probability that the measured value is
0〉 is a^{2 }and, similarly, the probability to be 1〉
is b^{2}. A string of n qubits has a state space of 2^{n}
dimensions with 2^{n} basis vectors. The extraction of a specific
state from the superposition is carried out in a probabilistic manner through
measurement. After the measurement, the original superposition is destroyed
since the process of measurement changes the state of the superposition
to that measured. Only one result is obtained and worse still one cannot
even choose which result one gets 
• 
Linear quantum gates and operators: They are the ordinary components
of a quantum architecture and they implement unitary transformations which
can be thought as being rotations in a complex vector space. There are several
gates, most of them are obtained by mapping into the quantum field a valid
Boolean function. If f(x) is the Boolean function to be handled, whose output
is defined by q bits and the input x by m bits, then the corresponding quantum
operator U is as follows: 
where, x〉, f(x)〉 is an entangled pair and 0_{q}〉
represents a string of q qubits all equal to 0〉. The result x, f(x)〉
is characterized by a string of (q+m) qubits
In the following the wellknown Toffoli gate will be used; it implements into
the quantum field the AND operator (∧):
The inputs are the 3 qubits x〉, y〉, 0〉 and the output
is constituted by the first 2 qubits and a third qubit, entangled with them
which is coincident with their AND. Because of the entanglement, the three outputs
are strictly connected and cannot be used separately. The previous operator
is also valid in the case y〉 is a string of qubits; in this case the
third output is also a string.
The unitary property of linear quantum processing implies that quantum states
cannot be copied or cloned by linear quantum operators. This property is a formidable
drawback of linear quantum processing, taking into account the probabilistic
nature of the extraction of a component from a superposition. More measurements
should be required for obtaining the component of interest. However, one cannot
repeat the measurement since it destroys the superposition. The only possibility
for repeating a measurement is to use different exemplars of a same superposition,
obtained independently of each other.
• 
Nonlinear quantum operators: They are the basis of
algorithms for overcoming the difficulties connected with the ordinary linear
quantum components (Panella and Martinelli, 2009).
The second (nonlinear) algorithm proposed by Abrams
and Lloyd (1998), denoted as ‘NAL algorithm’, will be used
in the following. It regards a superposition of the type: 
where, Φ^{(k)}〉 is a string of qubits, their number can
be any integer greater than or equal to 1, c^{(k)}〉 is a single
qubit entangled with Φ^{(k)}〉 and M is the number of elements
in the superposition.
The NAL algorithm can ascertain with certainty if in the superposition (3)
all c^{(k)}〉 are equal to 0〉 or there is present at least
one of them equal to 1〉. Namely, after the application of the NAL algorithm,
the resulting superposition in the two cases is equal either to:
or to:
respectively. Therefore, by measuring the first qubit either 0〉 or 1〉
is obtained with certainty.
The NAL algorithm requires, for undertaking this job in polynomial time, the
iterative application of ordinary unitary gates and a sequence of nonlinear
operations partly disentangling the state of the quantum processor. This is
obtained by transformations of type:
The nonlinear operator is moreover feasible by the help of ordinary unitary
operations and much simpler and more natural single qubit nonlinear operators.
Improved justifications and other versions of the NAL algorithm are available
in study of Czachor (1998a, b),
where the unphysical effects associated with the original version are eliminated.
SYNTHESIS OF A QUANTUM ARCHITECTURE FOR DETERMINING THE MAXIMUM/MINIMUM IN A SET OF POSITIVE INTEGERS
The procedure proposed in the following pertains to the design of a quantum
architecture for determining the maximum value in a set of M positive integers
and it is based on the NAL algorithm. The integers are denoted as ξ^{(k)},
k = 1…M, and represented by a
string of n qubits as follows:
where, b_{1}^{(k)}〉 is the most significant qubit. The
set of ξ^{(k)}〉 is stored in a superposition Ω〉:
where, Ω〉 is usually managed in the steps of the specific algorithm
that is used for solving the problem of interest. When the problem is the search
of the maximum in a set of integers, then they can be preliminarily stored following,
for instance, the procedure suggested by Trugenberger (2001).
The reference algorithm: The determination of the maximum value ξ^{(max)}〉
= b_{1}^{(max)} b_{2}^{(max)}…b_{n}^{(max)}〉
can be carried out by using the NAL algorithm in the following procedure. Its
computational cost is polynomial since it requires n applications of the NAL
algorithm and n measurements:
• 
Initialization: Let S_{1}〉 be a superposition
such that S_{1}〉 = Ω〉 as in Eq.
6. It can be represented in a compact form using the following general
notation: 
where, b_{1,j}^{(k)}〉 = b_{j}^{(k)}〉
for j= 1 …n.
The application of the NAL algorithm with the measurements applied in the next
steps destroys the processed superposition. Since, this inconvenience happens
in all the n steps of the procedure, it is necessary to start the procedure
with n exemplars of S_{1}〉, obtained preliminarily and independently
because of the no cloning property; they will be denoted as S_{1}^{(h)}〉,
h = 1…n.
• 
Step p, p = 1...(n2): Apply the NAL algorithm to the
first instance of S_{p}〉 that is S_{p}^{(1)}〉.
Considering the notations of Eq. 3, it is c^{(k)}〉
= b_{p,1}^{(k)}〉 and Φ^{(k)}〉
= b_{p,2}^{(k)}〉. The choice of a single qubit for
Φ^{(k)}〉, thus not considering the remaining qubits
of the superposition, is suggested by the convenience of reducing the number
of qubits of Φ^{(k)}〉 to a minimum without impairing
the result. The NAL algorithm ascertains the existence of one of the following
two cases for S_{p}^{(1)}〉: 

• 
The value of b_{p,1}^{(k)}〉 in all
the components of S_{p}^{(1)}〉 is equal to 0〉
and hence, it results b_{p}^{(max)}〉 = 0〉 

• 
There are some values of b_{p,1}^{(k)}〉 equal
to 1〉, then it results b_{p}^{(max)}〉 =
1〉 
The superposition to be examined in the successive step of the procedure is
different in the two previous cases. Namely, using the notation S_{p+1}〉,
it is defined as follows:
• 
First case: all the integers under investigation have
b_{p,1}^{(k)}〉 equal to 0〉. Hence, the determination
of the maximum should be addressed to the successive most significant qubits.
Since, the superposition S_{p}^{(1)}〉 is destroyed
by the previous measurement, it must be replaced by another exemplar of
S_{p}〉. For instance, it is considered as S_{p}^{(2)}〉
and hence, the procedure continues by determining the maximum of the integers
constituted by (np) qubits stored in S_{p+1}〉. It will be
represented in a compact form as follows: 
where, b_{p+1,j}^{(k)}〉 = b_{p,j+1}^{(k)}〉
for j = 1…(np).
• 
Second case: some of the integers under investigation
have b_{p,1}^{(k)}〉 equal to 1〉. Hence, the
maximum value to be found is among them. Also in this case, the determination
of the maximum in the next step is addressed to the successive most significant
qubits of S_{p}^{(2)}〉. However, the investigation
should be limited only to the components of S_{p}^{(2)}〉
having b_{p,1}^{(k)}〉 = 1〉. This objective is
attained by setting to 0〉 the qubit b_{p,2}^{(k)}〉
of the components of S_{p}^{(2)}〉 having b_{p,1}^{(k)}〉
equal to 0〉. This result is obtained by applying the Toffoli gate
to the qubits b_{p,1}^{(k)}〉 and b_{p,2}^{(k)}〉
as in Eq. 2, i.e.: 
By applying the Toffoli gate to such specific qubits of the whole superposition
S_{p}^{(2)}〉, the following one is obtained:
where,
In this case, S_{p+1}〉 will be represented in a compact form
as follows, taking only the qubits to be used in the successive steps and using
a suited permutation of the qubit order in Eq. 10:
where, b_{p+1,1}^{(k)}〉 = w_{p+1}^{(k)}〉
and b_{p+1,j}^{(k)}〉 = b_{p, j+1}^{(k)}〉
for j = 2… (np).
Finally, it is important to notice that the NAL algorithm will be applied similarly
also in the successive np steps. Therefore, np superpositions S_{p+1}〉
must be determined as illustrated in the previous operation. More precisely,
they are obtained using np exemplars of S_{p}〉 that is S_{p}^{(h+1)}〉,
h = 1…(np), and they will be
denoted as S_{p+1}^{(h)}〉.
• 
Step n1: The same operations of the previous generic
step are applied, considering in this case the specific value p = n1. In
particular Eq. 10 becomes: 
where,
However, in this case, the next superposition S_{n}〉 will be
still formed by two qubits instead of only one. More precisely:
where, b_{n,2}^{(k)}〉 = b_{n1,1}^{(k)}〉
and:
• 
b_{n,1}^{(k)}〉 = b_{n1,2}^{(k)}〉
in the first case, when b_{n1}^{(max)}〉 = 0〉 
• 
b_{n,1}^{(k)}〉 = w_{n}^{(k)}〉
otherwise that is in the second case when b_{n1}^{(max)}〉
= 1〉 
At the end of this step, there is only one exemplar of S_{n}〉.
• 
Step n: Apply the NAL algorithm to S_{n}〉
considering, with the notations of Eq. 3, c^{(k)}〉
= b_{n,1}^{(k)}〉 and Φ^{(k)}〉 =
b_{n,2}^{(k)}〉. The two cases obtained by applying
the NAL algorithm and then measuring b_{n,1}^{(k)}〉
will determine the value of the nth qubit of the solution. Namely, in the
first case it is b_{n}^{(max)}〉 = 0〉 while in
the second case it is b_{n}^{(max)}〉 = 1〉 
Determination of the quantum architecture in a toy case: The methodology
to determine the quantum architecture able to find the maximum in a set of positive
integers is illustrated by the following simple example.

Fig. 1: 
Quantum architecture obtained for the toy case: the figure
refers to its operation in the step 1, Wide arrows: A set of entangled qubits,
Tiny arrows: Single disentangled qubits, Dashed lines: Signals of control
logic 
Let {4, 6, 2, 0} be the set of integers under consideration. Hence, being
M = 4 and n = 3, the superposition of Eq. 6 will be:
which will be also used for the initialization of superposition S_{1}〉
as in Eq. 7. Three identical and independent superpositions,
i.e., S_{1}^{(1)}〉, S_{1}^{(2)}〉
and S_{1}^{(3)}〉 will be generated.
The operations involved in the step 1 are clearly illustrated in Fig.
1. By using a suited generator of superpositions, S_{1}^{(1)}〉
will feed the quantum array implementing the NAL algorithm. It should be outlined
that qubits b_{1,1}^{(k)}〉, b_{1,2}^{(k)}〉
and b_{1,3}^{(k)}〉 are all entangled for any kth element,
k = 1...4, of the superposition. Only the first two qubits will be used as inputs
of the NAL gate; i.e., c^{(k)}〉 = b_{1,1}^{(k)}〉
and Φ^{(k)}〉 = b_{1,2}^{(k)}〉. Since,
there are some components of S_{1}^{(1)}〉 whose the first
and most significant qubit is 1〉, then b_{1}^{(max)}〉
= 1〉 and hence, the current situation is the “second
case”. This result can be clearly
stored and ascertained by a block that performs some branch instructions on
the basis of the actual case. In fact, the two output qubits of the NAL gate
are disentangled.
Successively, by applying the Toffoli gate to another copy S_{1}^{(2)}〉
as specified in Eq. 10, the following superposition is obtained:

Fig. 2: 
Quantum architecture for the toy case: the figure refers to
its operation in the step 2, Wide arrows: A set of entangled qubits, Tiny
arrows: Single disentangled qubits, Dashed lines: Signals of control logic 
Bearing in mind that this is the “second case”, a suited array will
perform the bit swapping and selection defined in Eq. 11,
in order to obtain the superposition S_{2}^{(1)}〉 for
the next step:
More precisely, since in the next step 2 two copies of the latter superposition
are necessary, i.e., S_{2}^{(1)}〉 and S_{2}^{(2)}〉,
they will be obtained by repeating the latter branch twofold and by using S_{1}^{(2)}〉
and S_{1}^{(3)}〉, respectively.
In the step 2 the same operations are performed, as illustrated in Fig.
2, where the NAL array is fed by the superposition S_{2}^{(1)}〉.
Similarly to the previous step, there is one component having its first qubit
equal to 1〉 and hence b_{2}^{(max)}〉 = 1〉.
The application of the Toffoli gate to the other instance S_{2}^{(2)}〉
of the superposition will yield by Eq. 12:
Being this the penultimate step, the sole exemplar of the last superposition
S_{3}〉 will be still formed by two qubits instead of only one.
More precisely, using Eq. 13:
Finally, in step 3 the NAL algorithm is applied to S_{3}〉 and
so b_{3}^{(max)}〉 = 0〉 is obtained, since all the
components have their first qubit equal to 0〉. As a result, the greatest
integer in the considered set is correctly identified to be 6 that is:
ξ^{(max)}〉 = b_{1}^{(max)}
b_{2}^{(max) }b_{3}^{(max)}〉 = 110〉 
CASE STUDY: DETERMINATION OF THE SHORTEST TOUR LENGTH IN THE TSP
The TSP regards the following NPcomplete problem. A salesman must visit N
cities. In order to optimize his job, the length of his tour should be as short
as possible. The tour should include all the cities but only one time in order
to be optimal. The distances between the cities are stored in a matrix D such
that D(i,j) is the distance from city i to city j. Matrix D is not necessarily
symmetric and has the terms of its main diagonal equal to zero by convention.
The present objective is the determination of the length L_{min} of
the shortest tour.
Quantum representation of a solution: The preliminary operation to be
carried out is the representation of solutions by means of strings of qubits
and then to store all the solutions in a suitable superposition. It is not important
to include in the superposition also strings that are insignificant, in the
sense that they do not represent a valid solution. They will be easily disregarded
by a suitable computation of the performance of interest. What is important
is the simplicity of the representation.
Each city is represented by a string η〉 of ρ qubits:
where, ρ is greater than or equal to log_{2} N. In the case ρ
is greater than log_{2} N, then there are strings that are not valid
since they do not correspond to cities. They will be denoted as σ^{(m)}〉,
m = 1…μ, μ = (2^{ρ}N).
All the solutions of the problem are stored in a superposition of strings whose
length is equal to ρN qubits:
where,
is a string of ρ qubits that should represent the city visited by the salesman
in the ith step of his tour; the sum is extended over any combination of qubits
(i.e., M addends). The components of the superposition Γ〉 are valid
solutions only if the N strings
correspond to different cities and to valid representations. Hence, in the computation
of the performance of the solution this constraint must be taken into account
introducing a suitable penalty in order to disregard the components that are
not valid.
Computation of the tour length and determination of its minimum value:
The length L of the tour is obtained by adding the distances of the successive
cities visited by the salesman. The value so obtained is then modified for taking
into account the validity of the tour: a penalty term D_{0} is added
to it when it is not valid. The introduction of this term is controlled by a
suitable flag qubit.
When the components of Γ〉 do not represent a valid solution, a
qubit d〉 must be introduced for marking them. As said, a solution is
not valid either if two or more than two cities
coincide between them or if anyone of them does not represent a city.
The first situation is ascertained by the following Boolean function g(·):
The function g(·) can be implemented as follows:
The second situation is ascertained by the following Boolean function q(·):
The function q(·) can be implemented as follows:
The two situations can be taken into account simultaneously by the Boolean
function p(·):
The Boolean function p(·) is then converted into a quantum operator
π which is applied to the superposition Γ〉 so as to obtain the
final superposition Θ〉 where the flag qubit d〉 is present and
entangled with Γ〉:
The matrix D of distances between cities, each measured by δ bits assuming
a suitable normalization and quantization of distances, is determined by a Boolean
function t(·) whose output is defined by δ bits and the inputs are
two cities, each defined by ρ bits:
When ρ is greater than log_{2} N, there are strings
that do not represent cities and they are denoted as .
The value of t(·) is set to zero when any of the
of Eq. 22 coincides with some .
The value zero is arbitrarily chosen, since this case is successively disregarded
by introducing a suitable penalty term. The Boolean function t(·) is
mapped into a quantum operator Δ:
where, the RHS of Eq. 23 is an entangled pair representing
the result characterized by a string of (2ρ+δ) qubits.
The length L of the tour is obtained by summing the distances between successive
cities. It is represented by λ bits, included the penalty. The said distances
are added each other, starting from the first one and following the procedure
suggested by Vedral et al. (1996) which is based
on the use of linear quantum gates only. With the notations of Vedral
et al. (1996):
where, D_{0} is the penalty term introduced in the case the component
of the superposition Γ〉 does not represent a valid solution (i.e.,
the corresponding flag qubit d〉 is 1〉).
The choice of D_{0} and λ can be reasonably based on the maximum
entry d_{max} of matrix D. Since, the length of the tour is less than
Nd_{max} and d_{max}<2^{δ}, λ can be chosen
as the smallest integer greater than or equal to δ+log_{2}N. Moreover,
D_{0} should be chosen equal to Nd_{max} in order to cause the
overflow of the previous sum when the solution is not valid. The final superposition
is then:
The minimum length L_{min} of the tour is determined by applying the
quantum architecture obtained as previously illustrated (considering the search
of a minimum rather than a maximum) with reference to the superposition of Eq.
25 and in particular, to the strings L_{h}〉.
Computational cost of the exhaustive optimization: The complexity of
the TSP is related to the number N of cities to be visited. For this reason,
the dependence on N of the computational cost of the exhaustive optimization
will be investigated in the following, either applying the previous quantum
architecture or when a direct procedure based on the NAL algorithm is followed.
The computational cost in the first case is O(λ), since λ is the
number of applications of the NAL algorithm and of the quantum measurements
as well. As said, λ is conveniently chosen on the order of δ+log_{2}N.
Reminding the discussion at the beginning of this paper, a coarse resolution
(i.e., relatively few δ bits) for representing the distances between cities
is necessary to reduce and control the overall computational complexity. Usually
this does not prevent the minimum length of the tour from being represented
among all the considered solutions of the problem. Hence, the computational
complexity can be considered on the order of O (log_{2}N).
In the second case, by following for instance the procedure described in the
Appendix and using a similar notation, it is necessary firstly to derive a superposition
Ω'〉 constituted by all and only all the M' valid solutions of the
TSP, where M' = N!. By directly applying the NAL algorithm, the resulting computational
cost will be on the order of O(log_{2}(N!)). In this case, in order
to reduce the complexity, the exhaustive optimization must be abandoned by shrinking
the number of explored solutions without considering if the remaining ones may
all correspond to poor results (high lengths of the tour).
Finally, it is important to point out that M' is much lower than the number
M of elements in the superposition Γ〉 reported in Eq.
15. In spite of this inconvenience, the dependence on N of the computational
cost attainable by the architecture proposed in this paper is much smaller than
the one associated with the direct application of the NAL algorithm to Ω'〉.
In fact, the former can be considered as O (log_{2} N) while the latter
is O (log_{2}(N!)); for instance, in the case N = 300 it is log_{2}N
= 8.2 and log_{2}(N!) = 2041, respectively.
DISCUSSION
Exhaustive search is obtained efficiently in this paper exploiting the properties
of quantum processing and using a suitable interconnection of linear and nonlinear
quantum gates. In this regard, actual problems can be reduced to the determination
of the maximum/minimum in a set of integers by using the strict relation that
exists between Boolean algebra and quantum processing. In both cases, in fact,
strings of binary quantities (bits in the Boolean case and qubits in quantum
processing) are needed to represent what is of interest. Moreover, valid Boolean
functions can be converted into quantum linear operators. What is completely
different in the two cases is the possibility offered by the quantum processing
to handle simultaneously all the possible alternatives or solutions of a problem.
The difficult step of extracting the optimal solution from the superposition
is solved by using a suitable quantum architecture constituted by linear and
nonlinear quantum operators.
Nonetheless, it should be noted that it is not known to be true and is generally
suspected to be false that quantum computers can solve NPcomplete problems
in polynomial time (Bernstein and Vazirani, 1997). In
fact, the assumption of nonlinearity in the quantum effects is very important
in this paper and so the applicability of the proposed approach is strictly
dependent on the feasibility to implement the designed quantum gates by using
the forthcoming technologies.
CONCLUSIONS
A significant contribution to the imitation of natural mechanisms of optimization
is represented by evolutionary algorithms. They rely on the efficacy of these
natural mechanisms. What is imitated belongs to the macroscopic world while
nature operates with the same efficacy at the microscopic level as well, where
the governing laws are those of quantum mechanics. Hence, it is quite reasonable
to investigate at this level the possibility of obtaining efficient optimization
algorithms.
In the present study a procedure is proposed for synthesizing a quantum hardware
architecture able to solve with a reasonable computational cost the basic problems
of operational research and optimization, in particular the determination of
the maximum/minimum in a set of integers. By means of this architecture it is
possible to pursue an exhaustive search of the optimal solution and to control
the overall computational cost without the necessity for iterative timeconsuming
procedures, as clearly proved by the example illustrated in this paper with
relation to the wellknown TSP problem.
APPENDIX
Direct application of the NAL algorithm to find the maximum in a set of
positive integers: The direct application of the NAL algorithm allows the
determination of the maximum in a string of positive integers. This is based
on the use of specific Boolean functions successively transformed into linear
quantum operators. Each of them must be elaborated by eventually arriving to
a suitable quantum architecture including the said linear operator. The latter
is usually much more complex than the simple Toffoli gate that is used in the
architecture proposed in this paper, as clearly proved by considering the function
f_{c}(·) required in the procedure described in the following.
Using the same notations previously introduced in the study, first the maximum
in the set of M positive integers ξ^{(k)}, k = 1…M,
is found. To do this, the following Boolean function is constructed:
Then the problem is mapped into the quantum field and the AbramsLloyd algorithm
is applied to the composed function f_{c}(Ω〉), where Ω〉
is the quantum superposition of the previous integers. If the maximum is greater
than or equal to c then AbramsLloyd will return YES, otherwise it will return
NO. If the result was YES, then double c and try again. If the result was NO,
then halve c and try again. In this manner the maximum ξ^{(max)}
is determined by a computational cost on the order of log_{2}(ξ^{(max)}).
Once ξ^{(max)} is known, the value of c is set to c = ξ^{(max)}
and then f_{c}(Ω〉) = 1 only at the maximum. To find this
maximum, the method of AbramsLloyd is used to search only on the domain {1,
2,…, M/2}. Depending on whether the answer is YES or NO, it is known whether
the maximum occurs in the first or second half of the range {1, 2,…, M}.
Then, the first half of that part can be searched and so on, each time narrowing
down the potential location of the maximum by a factor of two. After log_{2}
(M) repetitions the maximum is obtained and hence, the whole procedure to find
the maximum has a O[log_{2}(ξ^{(max)})+log_{2}(M)]
complexity.