To motivate the mapping described below, we consider an idealized version. It shows why paths through the lattice tend to interfere destructively for nonsolution states, provided the constraints are small.
The idealized map simply maps each set in the lattice equally to
its supersets at the next level, while introducing random phases for
sets found to be nogood. For this discussion we are concerned with the
relative amplitude in solutions and nogoods so we ignore the overall
normalization. Thus for instance, with 
, the state 
will map to an unnormalized superposition of its four
supersets of size 3, namely the state 
.
With this mapping, a good at level
j will receive equal contribution
from each of its j subsets at the
prior level. Starting with amplitude of 1 at level 0 then gives an
amplitude of 
for goods at level
j. In particular, 
for solutions.
How does this compare with contribution to nogoods, on average?
This will depend on how many of the subsets are nogoods also. A simple
case for comparison is when all sets in the lattice
are nogood (starting with those at level
k given by the size of the
constraints, e.g., 
for problems with binary constraints). Let
be the expected value of the magnitude of the
amplitude for sets at level j. Each
set at level k will have
(and a zero phase) because all smaller subsets will
be goods. A set s at level
will be a sum of j
contributions from (nogood) subsets, giving a total contribution of
where the 
are the subsets of
s of size 
and the phases 
are randomly selected. The 
have expected magnitude 
and some phase that can be combined with
to give a new random phase 
. Ignoring the variation in the magnitude of the
amplitudes at each level this gives
because the sum of j random phases is
equivalent to an unbiased random walk [30] with j
unit steps which has expected net distance of 
. Thus 
or 
for .
This crude argument gives a rough estimate of the relative
probabilities for solutions compared to complete nogoods. Suppose there
is only one solution. Then its relative probability is 
. The nogoods have relative probability
with 
given by Eq. 1. An interesting
scaling regime is 
with fixed b,
corresponding to a variety of well-studied constraint satisfaction
problems. This gives
This goes to infinity as problems get large so the enhancement of solutions is more than enough to compensate for their rareness among sets at the solution level.
The main limitation of this argument is assuming that all subsets of a nogood are also nogood. For many nogoods, this will not be the case, resulting in less opportunity for cancellation of phases. The worst situation in this respect is when most subsets are goods. This could be because the constraints are large, i.e., they don't rule out states until many items are included. Even with small constraints, this could happen occasionally due to a poor ordering choice for adding items to the sets, hence suggesting that a lattice restricted to assignments in a single order will be much less effective in canceling amplitude in nogoods. For the problems considered here, with small constraints, a large nogood cannot have too many good subsets because to be nogood means a small subset violates a (small) constraint and hence most subsets obtained by removing one element will still contain that bad subset giving a nogood. In fact, some numerical experiments (with the class of unstructured problems described below) show that this mapping is very effective in canceling amplitude in the nogoods. Thus the assumptions made in this simplified argument seem to provide the correct intuitive description of the behavior.
Still the assumption of many nogood subsets underlying the above argument does suggest the extreme cancellation derived above will least apply when the problem has many large partial solutions. This gives a simple explanation for the difficulty encountered with the full map described below at the phase transition point: this transition is associated with problems with relatively many large partial solutions but few complete solutions. Hence we can expect relatively less cancellation of at least some nogoods at the solution level and a lower overall probability to find a solution.
This discussion suggests why a mapping of sets to supersets along
with random phases introduced at each inconsistent set can greatly
decrease the contribution to nogoods at the solution level. However,
this mapping itself is not physically realizable because it is not
unitary. For example, the mapping from level 1 to 2 with
takes the states 
to 
with the matrix
Here, the first column means the state 
contributes equally to and 
, its supersets, and gives no contribution to
. We see immediately that the columns of this matrix
are not orthogonal, though they can be easily normalized by dividing the
entries by 
. More generally, this mapping takes each set at level
i to the 
sets with one more element. The corresponding matrix
M has one column for each
i-set and one row for each
( 
)-set. In each column there will be exactly
1's (corresponding to the supersets of the given
i-set) and the remaining
entries will be 0. Two columns will have at most a single nonzero value
in common (and only when the two corresponding
i-sets have all but one of
their values in common: this is the only way they can share a superset
in common). This means that as N gets
large, the columns of this matrix are almost orthogonal (provided
, the case of interest here). This fact is used below
to obtain a unitary matrix that is fairly close to
M.
