   Next: Phases for Nogoods Up: A Search Algorithm Previous: A Search Algorithm

### The Problem-Independent Mapping

To take advantage of the potential cancellation of amplitude in nogoods described above we need a unitary mapping whose behavior is similar to the ideal mapping to supersets. There are two general ways to adjust the ideal mapping of sets to supersets (mixtures of these two approaches are possible as well). First, we can keep some amplitude at the same level of the lattice instead of moving all the amplitude up to the next level. This allows using the ideal map described above (with suitable normalization) and so gives excellent discrimination between solutions and nonsolutions, but unfortunately not much amplitude reaches solution level. This is not surprising: the use of random phases cancel the amplitude in nogoods but this doesn't add anything to solutions (because solutions are not a superset of any nogood and hence cannot receive any amplitude from them). Hence at best, even when all nogoods cancel completely, the amplitude in solutions will be no more than their relative number among complete sets, i.e., very small. Thus the random phases prevent much amplitude moving to nogoods high in the lattice, but instead of contributing to solutions this amplitude simply remains at lower levels of the lattice. Hence we have no better chance than random selection of finding a solution (but, when a solution is not found, instead of getting a nogood at the solution level, we are now likely to get a smaller set in the lattice). Thus we must arrange for amplitude taken from nogoods to contribute instead to the goods. This requires the map to take amplitude to sets other than just supersets, at least to some extent.

The second way to fix the nonunitary ideal map is to move amplitude also to non-supersets. This can move all amplitude to the solution level. It allows some canceled amplitude from nogoods to go to goods, but also vice versa, resulting in less effective concentration into solutions. This can be done with a unitary matrix as close as possible to the nonunitary ideal map to supersets, and that also has a relatively simple form. The general question here is given k linearly independent vectors in m dimensional space, with , find k orthonormal vectors in the space as close as possible to the k original ones. Restricting attention to the subspace defined by the original vectors, this can be obtained using the singular value decomposition  (SVD) of the matrix M whose columns are the k given vectors. Specifically, this decomposition is , where is a diagonal matrix containing the singular values of M and both and B have orthonormal columns. For a real matrix M, the matrices of the decomposition are also real-valued. The matrix has orthonormal columns and is the closest set of orthogonal vectors according to the Frobenius matrix norm. That is, this choice for U minimizes among all unitary matrices. This construction fails if since an m-dimensional space cannot have more than m orthogonal vectors. Hence we restrict consideration to mappings in the lattice at those levels i where level has at least as many sets as level i, i.e., . Obtaining a solution requires mapping up to level L so, from Eq. 1, this restricts consideration to problems where .

For example, the mapping from level 1 to 2 with given in Eq. 14 has the singular value decomposition with this decomposition given explicitly as The closest unitary matrix is then While this gives a set of orthonormal vectors close to the original map, one might be concerned about the requirement to compute the SVD of exponentially large matrices. Fortunately, however, the resulting matrices have a particularly simple structure in that the entries depend only on the overlap between the sets. Thus we can write the matrix elements in the form (r is an (i+1)-subset, is an i-subset). The overlap ranges from i when to 0 when there is no overlap. Thus instead of exponentially many distinct values, there are only , a linear number. This can be exploited to give a simpler method for evaluating the entries of the matrix as follows.

We can get expressions for the a values for a given N and i since the resulting column vectors are orthonormal. Restricting attention to real values, this gives where is the number of ways to pick r with the specified overlap. For the off-diagonal terms, suppose then, for real values of the matrix elements, where is the number of sets r with the required overlaps with and , i.e., and . In this sum, x is the number of items the set r has in common with both and . Together these give equations for the values of , which are readily solved numerically . There are multiple solutions for this system of quadratic equations, each representing a possible unitary mapping. But there is a unique one closest to the ideal mapping to supersets, as given by the SVD. It is this solution we use for the quantum search algorithm , although it is possible some other solution, in conjunction with various choices of phases, performs better. Note that the number of values and equations grows only linearly with the level in the lattice, even though the number of sets at each level grows exponentially. When necessary to distinguish the values at different levels in the lattice, we use to mean the value of for the mapping from level i to .

The example of Eq. 14, with and , has for Eq. 17 and for Eq. 19. The solution of these unitarity conditions closest to Eq. 14 is corresponding to Eq. 16.

A normalized version of the ideal map has and all other values equal to zero. The actual values for are fairly close to this (confirming that the ideal map is close to orthogonal already), and alternate in sign. To illustrate their behavior, it is useful to consider the scaled values , with evaluated using Eq. 18. The behavior of these values for is shown in Fig. 2. Note that is close to one, and decreases slightly as higher levels in the lattice (i.e., larger i values) are considered: the ideal mapping is closer to orthogonal at low levels in the lattice. Figure 2:  Behavior of vs. k on a log scale for N=10. The three curves show the values for i=4 (black), 3 (dashed) and 2 (gray).

Despite the simple values for the example of Eq. 16, the values in general do not appear to have a simple closed form expression. This is suggested by obtaining exact solutions to Eqs. 17 and 19 using the Mathematica symbolic algebra program . In most cases this gives complicated expressions involving nested roots. Since such expressions could simplify, the values were also checked for being close to rational numbers and whether they are roots of single variable polynomials of low degree . Neither simplification was found to apply.

Finally we should note that this mapping only describes how the sets at level i are mapped to the next level. The full quantum system will also perform some mapping on the remaining sets in the lattice. By changing the map at each step, most of the other sets can simply be left unchanged, but there will need to be a map of the sets at level other than the identity mapping to be orthogonal to the map from level i. Any orthogonal set mapping partly back to level i and partly remaining in sets at level will be suitable for this: in our application there is no amplitude at level when the map is used and hence it doesn't matter what mapping is used. However, the choice of this part of the overall mapping remains a degree of freedom that could perhaps be exploited to minimize errors introduced by external noise.   Next: Phases for Nogoods Up: A Search Algorithm Previous: A Search Algorithm