2
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ You can simulate classical probabilistic computation using "deterministic" quantum computation. Therefore probabilistic quantum computation is the same as "deterministic" quantum computation. $\endgroup$ – Yuval Filmus Mar 4 at 11:23
  • $\begingroup$ @YuvalFilmus How is it related with classical computation? $\endgroup$ – porton Mar 4 at 11:54
  • 1
    $\begingroup$ BQP contains BPP. You can simulate classical probabilistic computation using quantum computation. $\endgroup$ – Yuval Filmus Mar 4 at 12:00
  • $\begingroup$ @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. $\endgroup$ – porton Mar 4 at 14:57
  • 1
    $\begingroup$ You can always simulate randomness in the usual quantum model. It’s like asking whether there is a randomized analog of randomized Turing machines. $\endgroup$ – Yuval Filmus Mar 4 at 16:17
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.