One possible definition of "random" in this context: Is there any conceivable algorithm, perhaps one that models the entire universe in all of its particulars, that predicts the next string produced by the NIST quantum beacon?
Yes, but it has a variety of very unappealing physical properties. I mean for one thing, no one has all that information in the first place, but it would also be a theory were large scale correlations between outcomes would exist with space-like separations which would be weird, though clearly not impossible. T'Hooft's cellular automata approach has these properties and I guess its valid, although I don't know if it can be used to make non-trivial predictions.
Depends on the interpretation of QM. Many Worlds and Bohmian (Pilot Wave) are deterministic, but most interpretations are not. For MWI, you'd need your universal quantum computer to calculate all the branches/worlds. There's also Superdeterminism, which means you'd have to calculate everything from the big bang.
