My favorite presentation (http://c2.com/cgi/wiki?QuantumBogoSort) goes approximately like this:

1. Randomize the list. 2. If the list is not sorted, destroy the universe.

Is randomizing a list of n entities once is an O(n) operation. not sure how it would be done in O(1) on quantum computers.

The link that Dove gave suggests there's an idea of quantum randomization that will split our universe into n! universes in constant time.