What is an exact quantum algorithm?

In the literature, there is a distinction between exact and error-bounded quantum algorithms. The former must solve a problem with a zero probability of error, whereas the latter only needs to bound the probability of error away from some constant (typically strictly less than $$\frac{1}{3}$$).

My questions are these:

1. How do algorithms of each type differ?
2. What are examples of exact algorithms?
3. Can you use amplitude amplification in an exact algorithm?
• please stick to a single question per post. This makes it easier to give good quality answers and generally improves the reusability of the posts
– glS
Jan 31, 2020 at 10:04
• @glS you're right, sorry about that. Still getting the hang of posing good questions on here. My question is the title of the post and I intended for the series of subquestions more or less to give people a sense of what I'm having trouble with. (Although they appear more concrete now, after an edit.)
– TWal
Feb 1, 2020 at 16:47

Only a partial answer, the Deutsch-Jozsa algorithm is an example of an exact algorithm.

In my view, the algorithms differ exactly in how the answer is given. Either with probability 1 for exact algorithms, or with a bounded probability for approximate ones.

I would say you cannot use amplitude amplification in exact algorithms, as this would imply that states not corresponding to the answer have non-zero probability. I'm not sure about this point though. (note that Grover's algorithm for $$4$$ states uses amplitude amplification and gives an exact answer. This is an exception though I would say)

• Amplitude amplification can be performed exactly when the success probability is known. See Section 2.1 from "Quantum amplitude amplification and estimation" by Brassard et al. Jan 31, 2020 at 11:53
• @nippon I agree; Deutsch-Jozsa is the paradigmatic example of an exact algorithm. Could you elaborate more on why you consider Grover's algorithm for 4 states an exact algorithm? Everyone considers Grover's an exact algorithm, but even it's vanilla version only gets the output vector so close to the true search vector after $O(\sqrt{N})$ iterations
– TWal
Feb 1, 2020 at 16:51
• For four states, after one iterations of Grover's algorithm the probability of the correct state is exactly 1. Feb 3, 2020 at 13:17
• I don't get a probability of 1 when I work the math out myself. However, I've been known to screw these calculations up from time to time. Could you add a proof of your assertion to your answer or point me towards a source?
– TWal
Feb 3, 2020 at 17:06
• The math is quite simple and you should find the result with a single Grover iteration. See also this circuit: tinyurl.com/vnwjbpy The state $00$ is recovered with certainty. Feb 5, 2020 at 7:55

Say you want to factorise a large integer $$N$$. We know (inefficient) classical algorithms to do this, a naive example being: just check all combinations of smaller numbers until you find one that multiplies to $$N$$. You can make this into a quantum algorithm by simply converting each operation in your classical algorithm into a reversible one (there are standard ways to do this). This leaves you with an (inefficient) quantum algorithm that solves the problem deterministically.

Here, deterministic means that the output of the algorithm is 1) fully determined by its input and 2) gives you the answer directly. For example, in the factoring case, the output of the device might be a series of qubits. You know the output by measuring these qubits and thus getting a sequence of bits, which you can put together to know your answer (exactly like what you do in the classical case).

This is clearly, however, not a very useful quantum algorithm (you might as well just use a classical computer instead). So one can try something different, e.g. Shor's algorithm. Now, this is efficient, but not deterministic. This means that running the algorithm just once will not, in general, be enough to solve the problem. To simplify, you can imagine that each run of the algorithm will give you a different output, but that having enough of these outputs you can put them together to get your answer (with the whole process being still more efficient than the classical solution).

An example of a less artificial deterministic quantum algorithm would be Deutsch-Jozsa.

Can you use probability amplification in an exact algorithm? If so, are they really all that different?

What would be the point? If the algorithm is exact/deterministic, then there is nothing to amplify. If anything, you might want to use amplitude amplification with a non-exact algorithm, to amplify the success probability. Bear in mind however that even just running non-exact algorithms enough times is usually enough to get the right answer with probability close to one.

• @gIS I agree with your interpretation. Do you know of any literature that supports it? There's no mention of "exact algorithm" in Nielsen/Chuang or Kitaev's book and the papers I've read so far are not all that careful with this deterministic quality of exact algorithms
– TWal
Feb 1, 2020 at 16:59
• @gIS Here's a well-known paper that specifies an exact quantum algorithm which makes explicit use of a form of probability amplification, seemingly contradicting your position
– TWal
Feb 1, 2020 at 18:50
• @TWal I think this boils down to semantics. When you say "use probability estimation in an exact algorithm", I think of using the amplitude amplification (AA) algorithm at the end of the exact algorithm to amplify its success prob. In that paper, they seem to use techniques similar (or equal, I haven't read the paper enough tbh) to those of AA to build the (exact) algorithm itself. But then AA is an integral part of the exact algorithm. If your question was about using AA in such a way, then sure I guess it's doable, but it becomes less of a well-posed/answerable question imo
– glS
Feb 2, 2020 at 18:58
• @MarkS in fairness, the paper does mention using AA for their algorithm. See Main ideas in pag 3 of arxiv version and lemmas 2 and 3. Although to be honest I'm not clear as to how AA can make for an exact algorithm. Unless they are just using it in those specific cases in which one can get exactly to the target state with a known number of iterations.
– glS
Feb 2, 2020 at 19:04
• @gIS I'm still working out how they use AA to get a probability of 1. Though, I suspect that your last sentence is spot on -- they must tailor AA to the problem s.t. they get exactly the target state with a known number of iterators. Also, I see what you're getting at when you say it "boils down to semantics". However, I have to disagree with you about the well-posedness of my question. You either can or cannot use AA in an exact quantum algorithm. It's not just a matter of opinion or semantics.
– TWal
Feb 3, 2020 at 17:11

I asked basically the same question on CS stack exchange before this community was created. The answer is that the class of exact quantum algorithms has a name (EQP) but isn't very natural to study theoretically, because whether or not an exact algorithm can be executed depends entirely on the gate set that you have available, and moreover there's no universal gate set for this class of algorithms.

That having been said, one odd quirk of Grover's algorithm is that it's exact (in the sense that it's guaranteed to give a non-unique correct answer) if exactly one-quarter of the database is a valid solution. Of course, this is utterly useless in practice, because if you somehow knew that exactly one-quarter of the database was valid, then it would be much, much, much easier to just classically randomly query it, and you'd only need to to do so twice (in expectation) before finding a valid element.