My understanding from reading Scott Aaronson's FAQ is that the "random" in "random gates" just means that they pick a random circuit to evaluate. But this circuit is known, just like a program can pick a random number and then print it out.

The fact that quantum computing behaves "randomly" by nature further complicates the discussion :)