Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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:
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)
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.
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.
