# 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?

• You can simulate classical probabilistic computation using "deterministic" quantum computation. Therefore probabilistic quantum computation is the same as "deterministic" quantum computation. Mar 4 at 11:23
• @YuvalFilmus How is it related with classical computation? Mar 4 at 11:54
• BQP contains BPP. You can simulate classical probabilistic computation using quantum computation. Mar 4 at 12:00
• @YuvalFilmus The question wasn't whether we can simulate classical probabilistic computation using quantum computation, but whether there is something relating to quantum computation like classical probabilistic computation relates to classical computation. Mar 4 at 14:57
• You can always simulate randomness in the usual quantum model. It’s like asking whether there is a randomized analog of randomized Turing machines. Mar 4 at 16:17

## 1 Answer

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.