The vast majority of known interesting quantum algorithms are probabilistic. The only deterministic quantum algorithms that I know of (which aren't trivially equivalent to a classical algorithm) are (a) Deutsch's algorithm, in which the quantum speedup is pretty trivial, (b) the Deutsch-Josza algorithm, which solves a promise problem rather than a decision problem, and (c) this algorithm (which I found by Googling): http://arxiv.org/abs/1108.5848, which also doesn't solve a decision problem. Are there other known examples of "interesting"/"useful" deterministic quantum algorithms, especially for decision problems?
I know that this question isn't particularly well-formulated, because which algorithms you can use depends on which set of quantum gates you have available. Are there any interesting algorithms that use only a "realistic" set of quantum gates? (Say, only the quantum gates that can be currently purchased on Amazon for under $10 :-) .)