Heh? Unitarity is basically the defining characteristic of quantum mechanics. You can't just casually violate that.
There are definitely some interesting tricks you can do to exploit these behaviors. (I'm thinking for example of the "quantum Zeno effect", in which one can "find an answer without ever asking the question".[0]) But I don't know remotely enough about quantum computing to know what's actually possible in this context.
[0] A fun writeup on this idea is here (with an example involving an attempt not to wake any adorable sleeping puppies): http://www.preposterousuniverse.com/blog/2006/02/27/quantum-...
http://www.wikiwand.com/en/Wave_function_collapse
How to reconcile them in a satisfactory theory is an open issue, but non-unitary measurements play a crucial role in many quantum protocols, including, for example, quantum teleportation.
There is absolutely no consensus on this. This is merely saying that you believe in Everett style interpretations, which have so far failed to explain the appearance of non-linear processes in quantum mechanics satisfactorily.
Decoherence does _not_ solve the quantum measurement problem. You can not derive the Born rule.
Basically what decoherence does for you is translate a quantum amplitude on the space of operators into a classical distribution on the spectrum of your coupling. It does not tell you why you are allowed to interpret this distribution as a probability distribution. It does not tell you why you should be able to say that the state with higher amplitude is more likely to occur. In decoherence all states occur. So it is even unclear a priori what should be meant by the probability of a state occurring.
This is not my private opinion, this is the opinion of people like Zeh, who was instrumental in developing our current understanding of decoherence:
"[Decoherence] would explain why we never observe an apparatus pointing, say, to two different results, i.e. decoherence would provide a solution to the measurement problem of quantum mechanics. As pointed out by many authors, however (e.g. Adler 2003; Zeh 1995, pp. 14–15), this claim is not tenable."
http://plato.stanford.edu/entries/qm-decoherence/#SolMeaPro
Edit: Note that this is not in defense of the correctness of the above paper.
There's a famous theorem that any non-linearity in quantum mechanics (however small) would permit FTL information transfer. Could you link me one paper (either from a reputable journal or a highly cited article on the arXiv) that demonstrates non-linearity other than the exception of instantaneous collapse via measurement?
You can't have quantum computation without measurement, and thus without non-linearity. Quantum computation is not simply "doing the computation in each possible world", it also is some trick to extract (collapse) the information into one particular world, and I don't think we currently understand fully what that means, but it's certainly non-linear. After all the information is often in the amplitude.
Conversely there are measurement based models for quantum computation that rely purely on the non-linear process.
The "weird trick" is that they do non unitary things via partial measurement to beat that bound.
There might well be hidden costs here. Or judging from what others have said, it might just be a more straightforward mistake.