Can one do quantum computing without negative amplitudes?
This would be better suited as a comment but since I lack the reputation to comment (!), I am going to write it as an answer. Sorry for the inconvenience. 

Yes, you can do quantum computing without complex numbers. As mentioned by @DmitriUrbanowicz it known that Toffoli and Hadamard are universal for quantum computing. (See this simple proof due Dorit Aharonov.)

First, I would like to point out something we all learnt in kindergarten: In quantum computing, the amplitudes can be negative (this happens if you are using Toffoli and Hadamard as your gate set) and even complex (if you are using, say, Toffoli, Hadamard, and Phase) but the probabilities are still non-negative.

Now, as pointed by @JoshuaGrochow above, if your amplitudes themselves are positive real numbers then your gates become classical---you collapse to BPP.

Finally, if you just restrict to your probabilities being positive real numbers and adding up to $1$, then you can potentially solve any problem. This is because you are not putting any restriction on the evolution.