AFAIK It's not non-determinism that makes quantum computing efficient, it's the ability to compute on superpositions, which effectively means computing all outcomes at the same time.
Ah, right. I meant non-determinism in the sense of a non-deterministic automaton that calculates all outcomes at the same time, not in the sense of introducing randomness.
