Nsryjdtyk

Let me take Grover's algorithm as an example. In most cases, Grover's algorithm is able to yield with a high probability the desired term of the superposition. When the superposition has more than 4 terms, there's a small chance we will not obtain the desired term of the superposition, in which case we can repeat the procedure and measure it again, until we really get the desired result.

Although the probability of not getting the desired result decreases exponentially, it is technically not guaranteed that one will ever get the desired measurement. Therefore, we cannot prove that Grover's algorithm is an algorithm because we cannot prove it terminates with the correct answer in a finite number of steps.
(Otherwise, what part of the definition of "algorithm" I'm missing here?)

We can however define Grover's algorithm as a Las Vegas algorithm because if we do not measure the desired result, we could produce a "failure" result, satisfying therefore the definition of "Las Vegas algorithm".

Surely a quantum computer is able to calculate everything a classical computer can, so quantum computers can execute algorithms in the formal sense of the word. But is there an algorithm (not a Las Vegas algorithm) that uses true quantum features like superpositions and entanglement always producing the right answer in a finite number of steps and is not a Las Vegas algorithm? That's what I'm after. I appreciate any light on this direction.

It sounds like you're looking for algorithms that succeed deterministically with probability 1, instead of probabilistic algorithms that succeed with probability bounded from a 1/2 by a finite amount, say 2/3.

Exact is the keyword for deterministic quantum algorithms, such as in this paper Exact quantum algorithms have advantage for almost all Boolean functions by Andris Ambainis, Jozef Gruska, Shenggen Zheng that answers your question in the affirmative.

Although the probability of not getting the desired result decreases exponentially, it is technically not guaranteed that one will ever get the desired measurement. Therefore, we cannot prove that Grover's algorithm is an algorithm because we cannot prove it terminates with the correct answer in a finite number of steps. (Otherwise, what part of the definition of "algorithm" I'm missing here?)

It is important that an 'algorithm' terminates, but it is possible to consider slightly more flexible final conditions than you are considering when it does terminate. This is true of classical algorithms as well as quantum algorithms.

A Las Vegas algorithm is one which can 'succeed' or 'fail', and which produces a correct result whenever it 'succeeds' (so that it is meaningful to say that it has succeeded). We look for the probability of failure to be low, ideally — and this can be achieved in principle by trying again if you don't succeed (though in some cases you may end up trying many times).

This idea is taken seriously enough that there is a Las Vegas version of the complexity class P, known as ZPP. (It does not do to take complexity class names too seriously, but the acronym stands for "zero error probabilistic polynomial-time", as it is the class of decision problems solvable in polynomial time, using randomness, and without error — allowing however for a bounded probability of failing to produce a YES/NO answer at all.) This is a class between P and BPP.

There is an analogous class, ZQP, of problems solvable with an idealised quantum computer in polynomial time with zero error, which happens to contain integer factorisation (due to a combination of Shor's algorithm, the fact that verifying integer multiplication is in P, and the fact that primality testing is in ZPP and indeed also in P). These of course are analogous to 'Las Vegas' algorithms in the sense that they are zero error (though 'Las Vegas' would usually only be used for classical randomised algorithms) — and in particular, they are indeed algorithms.

Firstly, I would say that when you embrace quantum computing, you are considering probabilistic programming and not deterministic if I may say so (so your definition of algorithm depends on the kind of programming/computing you are doing). It will still be an algorithm though because you create a circuit (which is what we call an algorithm in quantum computing with the circuit model). A quantum algorithm through its quantum operations change the quantum state of a circuit(and this is the definition of quantum computing). Briefly said, this is just a different kind of computing.

If you are looking for deterministic output though from a quantum algorithm, we can take quantum circuits for arithmetic operations like adder circuits. You have also the common quantum phase estimation in the case you input one eigenvector of the unitary operation of interest. In that case, it outputs the phase (approximately) associated with the eigenvector provided exactly.