I doubt I've ever seen someone so completely miss the
point of a module. Q::S isn't about speed, it's about
showing the power of quantum operations, the any
and all functions. It's a simulation
of a machine. And yes, the primality tester is
O(1). It's just using different units than you are used to.
Note that all big-Oh run time complexities are in numbers
of elementary operations. For instance, in computational
geometry deciding whether a point lies right or left
of a line is an O(1) operation, regardless how many bits we
need to express the coordinates of the points when we would
actually simulate such operations on a current day device.
In the world of Q::S we have different elementary operations.
in reply to about Coolness, Impatience and Complexity
Finally it should be pointed out that Q::S was mainly intended
as a joke. Most people got it - but some didn't.