Another possibility is simply that they've got wildly more resources than we can imagine. It's ferociously expensive to run the universe on a classical simulation of QM, but finite. We have no particular reason to believe this "higher reality" doesn't have this level of resources. I've often pondered our universe as the moral equivalent of an elementary school demonstration; what if we're some metaphorical elementary kid's homework, because our physics is relatively simple (assuming some ToE that may actually be simpler than meets the current eye) and produces interesting results?
We can reasonably discuss the feasibility of simulating our universe using our universe. We can do some reasonable discussion of "universes that run something like ours but with some differences". We are profoundly ignorant about everything else.
I can't help but find it unsettling listening to a subject of the universe describe it as "relatively simple". Simple relative to what?! Some arbitrary more complex system? Well
Sure!
Frankly, I don't think it's a question of complexity, or even expressivity, but more one of encapsulation and information hiding.
The fundamental laws of the universe, at present, seem to be a whole lot simpler than many of the things that arise from them. That's as much of a statement in that direction as I think can be supported.
"I can't help but find it unsettling listening to a subject of the universe describe it as "relatively simple". Simple relative to what?!"
For one, simple relative to every universe we've ever created, such as Minecraft, World of Warcraft, Second Life, etc., all of which are megabytes upon megabytes (if not gigabytes) of ad-hoc rules, specifications, hard-coded geometry, etc. Even if we ignore the visualization aspects, they are all very complicated.
It is very likely that whatever the ultimate Theory of Everything is would fit comfortably into kilobytes. Very dense kilobytes, kilobytes you could spend your entire life understanding, but kilobytes. Certainly the entire Standard Model could be packed into kilobytes even starting from a fairly simple axiomatic mathematics, with a half-decent encoding. Its complexity comes from the number of particles interacting under its rules, and the fact our human brains aren't particularly suited to running QM calculations and confuses that difficulty with "complexity", since very few people have a grasp on what complexity truly is [1]. Most of the complexity of the Standard Model would actually be building up from the simple axioms and defining imaginary numbers and the other basic mathematic operations; once that was done, the fundamental equations to evolve state and the table of constants would not be very large. (Assuming that the parameters are not infinitely complicated real numbers, and that we can cut them off safely aften 40 or 50 decimal places without noticing a difference.)
The real universe's complexity does not appear to stem from its core building blocks necessarily, but from the staggering amount of space it occupies and the amount of computation it does, with both the Planck space and Planck time constants being staggeringly low on the one end, and the age of the universe and the expected age it should be able to survive staggeringly large on the other.
[1]: Defining it correctly is way beyond the scope of this post. But to get an idea, go here, look at the initial state, and then hit "start": http://pmav.eu/stuff/javascript-game-of-life-v3.1.1/ It looks like all sorts of complicated stuff is happening, right? However, the rule set is a small rule about what cells live or die based on neighbors, that small initial state, and if we're getting really technical, the iteration counter. What is on your screen may be visually complicated, but mathematically, it's very, very simple.
What's really shocking is that the Life rule set is probably sufficient to describe our universe. It's Turing Complete, and there's a sense in which any TC set of rules is equivalent to any other. However, it is also very likely that running our universe on Life rules would also require a massively complicated initial state, making it an unappealing theory to explain the real universe for that and several other reasons. We'd like to see something where the sum total of the complexity of the rule set and the initial state isn't that great, or is at least proportional to the amount of "stuff" the universe seems to have started out with.
We can reasonably discuss the feasibility of simulating our universe using our universe. We can do some reasonable discussion of "universes that run something like ours but with some differences". We are profoundly ignorant about everything else.