Nice succinct algorithm, but I must take issue with
There's an interesting O(1) algorithm
You do have to execute the algorithm on a classical computer, so Q::S or not, it's most definitely
not O(1). It'll be exponential (in the number of bits in $n) because behind the scenes, Q::S is dividing $n by all possible factors (what else could it be doing?). But even on a quantum computer, you still need either a division or gcd circuit (and probably a lot of other stuff), which will take some polynomial time in the number of bits.
Just because it's a one-liner doesn't make it O(1). Anyway, my favorite cutesy inefficient primality checker is
sub is_prime {
("1" x $_[0]) !~ /^(11+)\1+$/
}