Are there any useful deterministic quantum algorithms for decision problems?

Question

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ドル :-) .)

• Joey Eremondi: "Say, only the quantum gates that can be currently purchased on Amazon for under \10ドル". If they were useful for practical problems, they would probably cost a lot more than 10ドル.
• tparker: @jmite Until the patent expires, sure. After that, competition between suppliers would drive the price down to the marginal cost of production.
• Gilles 'SO- stop being evil': I'm not sure I understand your last question: are you asking if there are any interesting algorithms that use no quantum gates at all? quantum gates that can be simulated for 10ドル worth of actual, existing (hence non-quantum) computers?
• tparker: @Gilles The reference to 10ドル was completely a joke - I was making the point that it's hard to say what will be a "realistic" quantum gate , considering we have not yet succeeded in creating any reliable quantum gates at all. For the purpose of my question, by "realistic quantum gate" I mean, say, the gates described in the page en.wikipedia.org/wiki/Quantum_gate

Answer 1

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:

1. 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) & -\sin(10^\circ)\\ \sin(10^\circ) & \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.

2. 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.

Answer 2

A small modification to Grover's algorithm can make it deterministic. So, you get a quantum algorithm that can search an unsorted database with quadratic speedup compared to a classical computer. Of course, as you pointed out, the usefulness of this algorithm very much depends on the set of gates we are allowed to use.

You can find the paper on arxiv.