Fun fact: Grover's algorithm is a rare example of an algorithm that was proven optimal before it was invented.
Basically, the best they've proven is something like O(n * inverse_ackermann(n)), but it seems likely the algorithm actually runs in O(n). We also already have a randomised algorithm for this problem that runs in O(n) expected time on worst case input. The expectation is over the random choices.
https://en.wikipedia.org/wiki/Expected_linear_time_MST_algor...
By simulate I mean:
You get a sequence of instructions like 'insert x' and 'delete minimum', and you want to know what's elements are left in your priority queue at the end; but you don't care about any intermediate state.
It turns out that even in the comparison model, you can answer this question in linear time in the worst case. Precisely, with no approximation.