polynomial time) problem. See more on this topic, for instance in: http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP. Quantum database search algorithms The problem to solve here is quite basic: how to identify an item out of an unsorted database of N distinct elements? On average, such a task would require N/2 searches, with a worst case of N searches and a luckiest case of one single search. The computation time to find any item is, therefore, of the order of N, or O(N). As we shall see, the beauty in the GQDS algorithm is that the complexity of the search task becomes O(NN), which means a quadratic increase in computing speed. Here, I shall first describe the GQDS algorithm and then analyze its elementary quantum-circuit implementation and requirements.5 There is no loss in generality in assuming that the size of the database is N = 2n, where n is some nonzero integer. We require a quantum space V of dimension N > 2, and a known observable So on this space. This observable defines an orthonormal basis of N eigenstates /x) labeled |0), |1) |N - 1), and known eigenvalues labeled 20, A1, , AN-1. Then we shall associate a unique eigenstate or eigenvalue with each item in the database. The database search problem is now a matter of measuring an eigenvalue of interest, call it No, associated with the state /w), which represents some specific item W in the original database, and which we want to find through the search algorithm. As I will show further on, it is possible to construct the eigenstate superposition (19.34) noting that (s/s) = 1 since the eigenstate basis {|x> }x=0...N-1 is orthonormal. Any eigen- state /w) has the same projection (w/s) = 1/N, and given our item w, the probability of measuring No (or finding |s) in the state /w)) is |(w/s)|2 = 1/N, consistently with a classical database search algorithm. Let us then introduce a unitary operator Uw, referred to as the "oracle," and defined by (19.35) It is immediately verified that the oracle has the following properties: Uwlx)==|w if = = /x) if x 