Does quantum computing rely on particular interpretations of quantum mechanics? It is my understanding that quantum computing relies on quantum superposition and entanglement to work--qbits must exist in all states simultaneously before giving a particular result when observed.
Would this mean that quantum computing is impossible in interpretations of quantum mechanics in which qbits are not in reality existing in all states simultaneously until observed?  Thus, wouldn't quantum computing be incompatible with non-local hidden variable interpretations (deBroglie-Bohm, for example), or with other interpretations in which the underlying reality is deterministic such as 't Hooft's?
 A: As Dan and Mark pointed out, the short answer to your question is NO.  Quantum computing relies only on the mathematical framework of QM---i.e., the part that's common to all interpretations, to whatever extent they are interpretations rather than alternative physical theories.  If a theory predicts that quantum computing can't work, the theory must either deviate somehow from the framework of QM, or else add some new physical principle to the framework with new observable consequences---neither of which a mere "interpretation" is supposed to do.
On the other hand, one can also ask the further question: do some interpretations provide more insight into how a QC works than others?  David Deutsch, one of the inventors of quantum computing, was motivated by the goal of making vivid the Many-Worlds Interpretation (of which he's a strong believer), and has argued for decades that quantum computing makes any interpretation other than a Many-Worlds one look hopelessly contrived.  However, others working in quantum computing vehemently disagree with that claim, and say that we can understand a QC just fine from (e.g.) a Copenhagen, quantum Bayesian, or "shut-up-and-calculate" perspective.  Probably the majority of QC researchers don't care about the interpretation debate, or regard it mostly as a source of amusement.  Their main goals are (a) to build devices that work, and (b) to understand what we could do with those devices.
However, here I'll add my personal opinion that some interpretations---such as deBroglie/Bohm and its cousins---look quite contrived if we try to use them to understand quantum computation.  Yes, certainly deBroglie/Bohm predicts that QC can work, since all of its predictions are the same as standard QM's.  However, in any interesting quantum algorithm (like Shor's algorithm), the computational "work" is clearly done by unitary transformations on an exponentially-large, highly-entangled n-particle wavefunction---a situation that leads to intuitions very different from those suggested by one or two particles moving around in a potential.  If you worked out the trajectories for the Bohmian particles in Shor's algorithm, they'd look like a comically-irrelevant sideshow to the main event, adding no explanatory value and just "tagging along for the ride."  (See this question for more.)
Finally, for some interpretations, like the "transactional interpretation," I don't think it's ever been satisfactorily explained how they can account for quantum computation.  But if so, then that's simply another way of saying that it hasn't been satisfactorily explained how they reproduce QM itself.  See here for more.
A: As Dan points out in his excellent answer, most alternative "interpretations" reproduce standard quantum mechanics by construction. However, collapse interpretations such as the GRW theory, or Penrose's gravitational collapse seem to prohibit coherence in quantum systems larger than some certain size or mass. Of course, these breakdown scales are larger than those yet achieved in quantum experiments, otherwise these interpretations would have already been falsified or confirmed. Since quantum computers could conceivably require large sizes to reach the fault-tolerant limit, maybe these collapse theories would come into play. However, even if we used a million trapped ions we still would be nowhere near the Planck mass required for Penrose's collapse, and probably quite far from the GRW limit. With larger qubits like superconducting systems, maybe the hypothetical collapse limit would be smaller than a working fault-tolerant computer. It's quite a big if, though.
Edit in response to comments
It's true that the theories I mentioned are not "interpretations" according to the pedantic definition. However, all of these examples are usually lumped together with true interpretations, and taught in the same philosophy classes, for example :) Actually, the end of Bohm's book is devoted to extensions of his theory that could falsify standard QM. Reading Chris Fuchs' writings on quantum Bayesianism makes it abundantly clear that he is ultimately interested in finding a fundamentally different theory that could be experimentally tested. This is because physicists know that in order for their pet theory to be interesting (to the rest of the scientific community, at least), it must also be falsifiable.  The common thread that all such variants share with true interpretations is that, by construction, they correctly predict the outcomes of all quantum experiments performed to date.  That's why I thought them worth mentioning as a different angle on the existing answers. 
A: Generally, when you make a quantum calculation, you have to make some sort of measurement of the qubits at the end of the algorithm where the result you're looking for is a very probable (but not necessarily certain) result. In any interpretation that actually agrees with the basic results of quantum mechanics, these probabilities will still hold and the algorithm will still work.
If an interpretation is ruled out by the possibility quantum computing, then it's (probably) wrong because it contradicts quantum mechanics. To the best of my knowledge all of the interpretations you mentioned, while deterministic, still give results in agreement with quantum mechanics and can't be ruled out by the existence of a quantum computer.
