Can one do quantum computing without negative amplitudes?

Question

The typical representation I see of $k$ qubits is a $2^k$ complex numbers $c_i$ for every possible combination of values of those bits, such that the sum of all the squared magnitudes of those numbers is 1. i.e.

$$\sum_i \vert c_i \vert^2 = \sum_i (a_i + i b_i)(a - ib_i) = \sum_i a_i^2 + b_i^2 = 1$$

(so with two bits, we have $\vert c_0 \vert^2 = P(00)$, $\vert c_1 \vert^2 = P(01)$, $\vert c_2 \vert^2 = P(10)$, and $\vert c_3 \vert^2 = P(11)$)

Then gates are simply defined by complex matrices of size $2^k \times 2^k$ that preserve this requirement (formally the set of such matrices is the unitary matrices). To apply a gate we simply multiply these matrices by our current "vector of complex probabilites" and a new set of $c_i$'s. I.e., if $c \in \mathbb{C}^{2^k}$ and our unitary gate H is in $\mathbb{C}^{2^k \times 2^k}$ then we get our result $c^\prime \in \mathbb{C}^{2^k}$ via

$$c^\prime = H c $$

However, is using complex numbers necessary? What I mean is, we could instead define real $p_i = \vert c_i \vert$, and then to apply a gate we do

$$p^\prime = \vert H \sqrt{p} \vert^2 $$

(here by $\sqrt{p}$ and $|..|^2$ I mean I apply those operations to each element of the vector, and keep the vector the same size)

This answer seems to suggest we might be able to do this, and clearly this does preserve everything for one application of an operator if we pick $c_i = \sqrt{p_i} + 0i$, for example, but I don't know about a sequence of multiple gates that each output and work with rotated complex numbers with the same magnitude.

Personally I feel having a set of $0 \leq p_i \leq 1$ s.t. $\sum_i p_i = 1$ seems much more intuitive to me, so my question is simply: is a computer using these rules less powerful than a quantum computer? Or is it a separate complexity class?

As far as I can tell the main difference is gates with imaginary numbers: in this $p$ setting they result in an operation on the inputs in terms of real numbers but it may not be linear, and the order of applying the gates may now matter (try out the $\sqrt{NOT}$ gate for example), but I don't know if that actually matters in terms of what it can compute efficiently.

Edit: for example, the Hadamard gate

$$ H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$

applied to $\begin{bmatrix} p_0 \\ p_1 \end{bmatrix}$ ($p_0$ is probability of $<0|$, $p_1$ is probability of $<1|$) would be

$$ p^\prime = \vert \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} \sqrt{p_0} \\ \sqrt{p_1} \end{bmatrix} \vert^2 = \vert \begin{bmatrix} \frac{\sqrt{p_0} + \sqrt{p_1}}{\sqrt{2}} \\ \frac{\sqrt{p_0} -\sqrt{p_1}}{\sqrt{2}} \end{bmatrix} \vert^2 = \begin{bmatrix} \vert \frac{\sqrt{p_0} + \sqrt{p_1}}{\sqrt{2}}\vert^2 \\ \vert \frac{\sqrt{p_0} -\sqrt{p_1}}{\sqrt{2}}\vert ^2 \end{bmatrix} = \begin{bmatrix} \frac{p_0 + p_1}{2} + \sqrt{p_0}*\sqrt{p_1} \\ \frac{p_0 + p_1}{2} - \sqrt{p_0}*\sqrt{p_1}\end{bmatrix} $$

Answer 1

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.