the intended result. This is called *probability amplitude amplification* [Gruska 
(1999)]. 

- *Grover's Algorithm:* It searches N=2n items superimposed on a quantum register of n qubits using a certain state as a search key. It is able to search an unordered set of items in ( NO ) time [Grover (1997)]. 

- *Quantum Fourier Transform (QFT):* A basic subroutine in many specialized algorithms concerning factoring prime numbers and simulating actual quantum systems. QFT is a unitary operation acting on vectors in the Hilbert space. By altering their phases and probability amplitudes it can reveal periodicity in functions just like its classical analog [Coppersmith (1994)]. 

- *Shor's Algorithm:* It finds the period of a periodic function in polynomial time, a problem directly related to factorization of large integers [Shor (2004)]. This algorithm is famous for making obsolete the current public-key encryption systems. 

## 4. On Quantum Artificial Intelligence

One of the first contributions that QC offers to AI is the production of truly random numbers. True randomness has been reported to cause measurable performance improvement to genetic programming and other automatic program induction methods [Rylander et al. (2001)]. Monte-Carlo, simulated annealing, random walks and other analogous search methods are expected to benefit from that as well. A truly random number of N bits can be produced by applying the Hadamard transformation to a N-qubit quantum register thus producing the superposition of all basis states 2 0 1 N
=
12
∑
−
k N
k . Then just by measuring this state we get a truly random number in the range of [0, 2N-1]. Since the process can be repeated n times to produce a nN-bit random number, it is generally possible to produce N-bit random numbers using a Mqubit quantum register where M<<N. Thus, in principle even just one qubit (M=1) is adequate. However, random search methods in QC indicate a completely different approach than in classical computation. The quantum analog of a classical random walk on a graph, i.e. the quantum random walk, even in one dimension is a much more powerful computational model [Ben-Avraham et al. (2004)]. While the classical random walk is essentially a Markov process, in a quantum random walk propagation between node pairs is exponentially faster, thus enabling the solution of NP-complete problems as well [Childs et al. (2002)]. Moreover, as mentioned by [Shor (2004)], combinations of quantum random walks with Grover's algorithm have managed to confront efficiently some real-world problems like database element comparison and dense graph search [Childs et al. (2003)]. 