Are there any useful deterministic quantum algorithms for decision problems? 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 :-) .)
There are some query complexity results that mention exact quantum algorithms. See this blog post about the paper "Separations in Query Complexity Based on Pointer Functions":


  a total boolean function $g$ on $n$ variables that has [...] exact quantum query complexity [...] $Q_E(g) = \tilde O(\sqrt n)$.




More generally, the complexity class you're looking for is called EQP: Exact Quantum Polynomial-Time.

EQP is not a very "nice" complexity class, especially compared to BQP. There's two big reasons for that:


Theoretical-side, there's no universal set of gates. EQP circuits may require a gate with irrational coefficients such as $\begin{bmatrix} \cos(10^\circ) &amp; -\sin(10^\circ)\\ \sin(10^\circ) &amp; \cos(10^\circ)\end{bmatrix}$, and approximations via other gates aren't allowed. So you end up with a bunch of different $\text{EQP}_{my\_favorite\_gate\_set}$s instead of a nice unified one.
Practical-side, there's no possibility of error correction. EQP lives in a world without errors, because otherwise it wouldn't be exact. Error correction is expected to be a necessity in practice, so if you care about actual implementation then you don't care much about EQP.