Is there a concept of probabilistic quantum computers?

Answering my question Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above polynomial.

Accordingly a Quora answer

Quantum computation is fully deterministic. A given computation applied to a given starting state will always produce the same final state, every time. What is potentially non-deterministic is extracting the output in classical terms.

So, it looks like it makes sense to introduce probabilistic quantum computation (as opposed to "fully deterministic"). Does it make sense? Does such thing as probabilistic quantum computation exist in physics?

So maybe, for probabilistic quantum computation there is no known proof that there are computable functions of (probabilistic) quantum time complexity strictly above polynomial, is there?

It is true that unitary gates used in quantum algorithms (and indeed any unitary evolution in quantum mechanics generally) is deterministic and measurements are the only non-deterministic elements in a quantum algorithm (and indeed in quantum mechanics generally). However, it is not true that measurement is always the final step in a quantum algorithm, see for example my answer to this question for a few prominent instances of the use of intermediate measurements. The misconception might originate in the principle of deferred measurement which says that any quantum algorithm with intermediate measurements is equivalent to one where all measurements are moved to the final step. In particular, the principle enables us to replace classical control of quantum gates based on results of intermediate measurements with quantum controlled gates.

Returning to the question of probabilistic quantum computation, note that any probabilistic quantum algorithm (understood here as one that chooses gates to apply based on random bits) can be simulated by a quantum algorithm with intermediate measurements. This follows from the fact that measurement of the state $|+\rangle = (|0\rangle + |1\rangle)/\sqrt{2}$ in the computational basis generates a random bit which can subsequently be used to make random choices about which quantum gates to apply. By the principle of deferred measurement we can turn such a probabilistic quantum algorithm into a quantum algorithm where all measurements are terminal. In conclusion, probabilistic quantum computing is subsumed by regular quantum computing. This is why no distinction is generally made between probabilistic and deterministic quantum algorithms.

StackExchange Computer Science Q#136178, answer score: 5