next up previous
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 tex2html_wrap2756 , 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 obtainedgif using the singular value decomposition [24] (SVD) of the matrix M whose columns are the k given vectors. Specifically, this decomposition is tex2html_wrap2757 , where tex2html_wrap_inline2838 is a diagonal matrix containing the singular values of M and both tex2html_wrap2758 and B have orthonormal columns. For a real matrix M, the matrices of the decomposition are also real-valued. The matrix tex2html_wrap2759 has orthonormal columns and is the closest set of orthogonal vectors according to the Frobenius matrix norm. That is, this choice for U minimizes tex2html_wrap2760 among all unitary matrices. This construction fails if tex2html_wrap2761 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 tex2html_wrap2655 has at least as many sets as level i, i.e., tex2html_wrap2763 . Obtaining a solution requires mapping up to level L so, from Eq. 1, this restricts consideration to problems where tex2html_wrap2764 .

For example, the mapping from level 1 to 2 with tex2html_wrap2694 given in Eq. 14 has the singular value decomposition tex2html_wrap2757 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 tex2html_wrap2767 (r is an (i+1)-subset, tex2html_wrap_inline2856 is an i-subset). The overlap tex2html_wrap2768 ranges from i when tex2html_wrap2769 to 0 when there is no overlap. Thus instead of exponentially many distinct values, there are only tex2html_wrap2655 , 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




is the number of ways to pick r with the specified overlap. For the off-diagonal terms, suppose tex2html_wrap2771 then, for real values of the matrix elements,




is the number of sets r with the required overlaps with tex2html_wrap_inline2518 and tex2html_wrap_inline2856 , i.e., tex2html_wrap2772 and tex2html_wrap2773 . In this sum, x is the number of items the set r has in common with both tex2html_wrap_inline2518 and tex2html_wrap_inline2856 . Together these give tex2html_wrap2655 equations for the values of tex2html_wrap2775 , which are readily solved numericallygif. 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 algorithmgif, 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 tex2html_wrap2776 to mean the value of tex2html_wrap2777 for the mapping from level i to tex2html_wrap2655 .

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

A normalized version of the ideal map has tex2html_wrap2784 and all other values equal to zero. The actual values for tex2html_wrap2776 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 tex2html_wrap2786 , with tex2html_wrap2787 evaluated using Eq. 18. The behavior of these values for tex2html_wrap2788 is shown in Fig. 2. Note that tex2html_wrap2789 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 bik 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 tex2html_wrap2777 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 [54]. In most cases this gives complicated expressions involving nested roots. Since such expressions could simplify, the tex2html_wrap2777 values were also checked for being close to rational numbers and whether they are roots of single variable polynomials of low degreegif. 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 tex2html_wrap2655 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 tex2html_wrap2655 will be suitable for this: in our application there is no amplitude at level tex2html_wrap2655 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 up previous
Next: Phases for Nogoods Up: A Search Algorithm Previous: A Search Algorithm

Tad Hogg
Wed Mar 20 16:29:17 PST 1996