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

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. – Yuval Filmus Mar 4 at 11:23
• @YuvalFilmus How is it related with classical computation? – porton Mar 4 at 11:54
• BQP contains BPP. You can simulate classical probabilistic computation using quantum computation. – Yuval Filmus 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. – porton 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. – Yuval Filmus Mar 4 at 16:17

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.