4
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ "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. $\endgroup$
    – jmite
    May 12, 2016 at 1:15
  • $\begingroup$ @jmite Until the patent expires, sure. After that, competition between suppliers would drive the price down to the marginal cost of production. $\endgroup$
    – tparker
    May 12, 2016 at 2:08
  • $\begingroup$ 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? $\endgroup$
    – Gilles 'SO- stop being evil'
    May 12, 2016 at 7:50
  • $\begingroup$ @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 $\endgroup$
    – tparker
    May 12, 2016 at 16:10

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.