The deep structure of constraint satisfaction problems explains the association of hard search instances with a phase transition in problem solubility. This structure is also the basis of a quantum search algorithm exhibiting the phase trausition. In this paper, this algorithm is modified to incorporate additional problem structure. This modification is an example of a general method for inchding heuristics in quantum search. The new algorithm is evaluated empirically for random 3SAT, illustrating how quantum searches can benefit from using problem structure, on average.