  In the black-box model, problems constrained by a `promise' are the only ones
that admit a quantum exponential speedup over the best classical algorithm in
terms of query complexity. The most prominent example of this is the
Deutsch-Jozsa algorithm. More recently, Wim van Dam put forward an algorithm
for unstructured problems (i.e., those without a promise). We consider the
Deutsch-Jozsa algorithm with a less restrictive (or `broken') promise and study
the transition to an unstructured problem. We compare this to the success of
van Dam's algorithm. These are both compared with a standard classical sampling
algorithm. The Deutsch-Jozsa algorithm remains good as the problem initially
becomes less structured, but the van Dam algorithm can be adapted so as to
become superior to the Deutsch-Jozsa algorithm as the promise is weakened.
