  We investigate the generalisation of quantum search of unstructured and
totally ordered sets to search of partially ordered sets (posets). Two models
for poset search are considered. In both models, we show that quantum
algorithms can achieve at most a quadratic improvement in query complexity over
classical algorithms, up to logarithmic factors; we also give quantum
algorithms that almost achieve this optimal reduction in complexity. In one
model, we give an improved quantum algorithm for searching forest-like posets;
in the other, we give an optimal O(sqrt(m))-query quantum algorithm for
searching posets derived from m*m arrays sorted by rows and columns. This leads
to a quantum algorithm that finds the intersection of two sorted lists of n
integers in O(sqrt(n)) time, which is optimal.
