<p>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.</p>

<p>$$\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$$</p>

<p>(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)$)</p>

<p>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</p>

<p>$$c^\prime = H c $$</p>

<p>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>

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

<p>(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)</p>

<p><a href="https://physics.stackexchange.com/questions/32422/qm-without-complex-numbers">This answer</a> 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.</p>

<p>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?</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Quantum_logic_gate#Square_root_of_NOT_gate_(%E2%88%9ANOT)" rel="nofollow noreferrer">$\sqrt{NOT}$</a> gate for example), but I don't know if that actually matters in terms of what it can compute efficiently.</p>

<p>Edit: for example, the Hadamard gate</p>

<p>$$ H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 &amp; 1 \\ 1 &amp; -1 \end{bmatrix}$$</p>

<p>applied to $\begin{bmatrix} p_0 \\ p_1 \end{bmatrix}$ ($p_0$ is probability of $&lt;0|$, $p_1$ is probability of $&lt;1|$) would be</p>

<p>$$ p^\prime = \vert \frac{1}{\sqrt{2}} \begin{bmatrix} 1 &amp; 1 \\ 1 &amp; -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} $$</p>

CC BY-SA 4.0
2018-08-03T01:52:54.297Z
I'm not sure I understand how you want your operations to work. However, since you can embed $\mathbb{C}^{n \times n}$ into $\mathbb{R}^{2n \times 2n}$ via the embedding $x + i y \mapsto \begin{pmatrix} x &y\\ -y &x \end{pmatrix}$, and since quantum circuits are just unitary matrices in $\mathbb{C}^{n \times n}$, you can always express a circuit as a matrix in $\mathbb{R}^{2n \times 2n}$. In this new representation, quantum operations are just a certain type of linear operator on $\mathbb{R}^{2n \times 2}$. It's just a bit less elegant than the complex representation.
Noah Stephens-Davidowitz
CC BY-SA 4.0
2018-08-03T05:01:32.687Z
Not sure what you suggest, but complex numbers aren't necessary for quantum computation. There's already an answer for such a question on cstheory: https://cstheory.stackexchange.com/a/6657/49517
Dmitri Urbanowicz
CC BY-SA 4.0
2018-08-03T18:12:42.900Z
@NoahStephens-Davidowitz yes that's true, but I'd like to only use one positive real value per state, not two.
Phylliida
CC BY-SA 4.0
2018-08-03T18:13:27.657Z
@DmitriUrbanowicz yes but that answer requires negative values, I'd like my p values to be only positive. I added an example, does that help?
Phylliida
CC BY-SA 4.0
2018-08-04T01:20:09.170Z
I'm pretty sure with only positive reals you get BPP instead of BQP. Negatives are crucial to achieve negative interference (i.e. cancelations).
Joshua Grochow
CC BY-SA 4.0
2018-08-04T13:34:06.510Z
@Phylliida your example yields negative probabilities.
Dmitri Urbanowicz
CC BY-SA 4.0
2018-08-05T00:10:21.250Z
@JoshuaGrochow that's what I suspected, do you have a formal proof or a rough jist of how one would do that?
Phylliida
CC BY-SA 4.0
2018-08-05T00:18:12.520Z
@DmitriUrbanowicz no? Any values of $0 \leq p_0, p_1 \leq 1$ will output positives, there is just a minus sign in the intermediate computation. Feel free to give a counterexample if you have one, but as far as I know there isn't. We can verify this by noting that for any possible output $c_i = (H \sqrt{p})_i \in \mathbb{C}$ in the vector produced by doing $H\sqrt{p}$, we convert to the new $p^\prime_i$ via doing $p^\prime_i = \vert c \vert^2 = \vert a+bi \vert ^2 = (a+bi)(a-bi) = a^2 + b^2 \geq 0$. The point is that each $p_i$ is a norm of a complex number which is always positive.
Phylliida
CC BY-SA 4.0
2018-08-05T05:45:06.043Z
@Phylliida sorry, I was wrong.
Dmitri Urbanowicz
CC BY-SA 4.0
2018-08-07T20:51:38.843Z
As an aside, note that there are non-asymptotical system properties that are not possible to replicate if using real numbers. As an easy example, using complex numbers in 2 dimensions gives you a system where the number of maximum orthogonal states is 2, and where there are three such basis that are [mutually unbiased](https://en.wikipedia.org/wiki/Mutually_unbiased_bases#Example_for_d_=_2), which would not be possible to describe if using real numbers.
Abel Molina
CC BY-SA 4.0
2018-08-07T22:25:54.947Z
@AbelMolina Interesting, even though they don't affect things asymptotically, could they affect constants (by this I mean not using big O type notation) for some given problem and some fixed n, in terms of number of gates required? (or some equivalent)
Phylliida
<complexity-classes><quantum-computing>
Can one do quantum computing without negative amplitudes?
Phylliida
# Can one do quantum computing without negative amplitudes?

(Asked by: username_0 on 2018-08-02)

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](https://physics.stackexchange.com/questions/32422/qm-without-complex-numbers) 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}$](https://en.wikipedia.org/wiki/Quantum_logic_gate#Square_root_of_NOT_gate_(%E2%88%9ANOT)) 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} $$

**Tags:** complexity-classes, quantum-computing

> **Comments:**
> **username_1**: I'm not sure I understand how you want your operations to work. However, since you can embed $\mathbb{C}^{n \times n}$ into $\mathbb{R}^{2n \times 2n}$ via the embedding $x + i y \mapsto \begin{pmatrix} x &y\\ -y &x \end{pmatrix}$, and since quantum circuits are just unitary matrices in $\mathbb{C}^{n \times n}$, you can always express a circuit as a matrix in $\mathbb{R}^{2n \times 2n}$. In this new representation, quantum operations are just a certain type of linear operator on $\mathbb{R}^{2n \times 2}$. It's just a bit less elegant than the complex representation.  
> **username_2**: Not sure what you suggest, but complex numbers aren't necessary for quantum computation. There's already an answer for such a question on cstheory: https://cstheory.stackexchange.com/a/6657/49517  
> **username_0**: @NoahStephens-Davidowitz yes that's true, but I'd like to only use one positive real value per state, not two.  
> **username_0**: @DmitriUrbanowicz yes but that answer requires negative values, I'd like my p values to be only positive. I added an example, does that help?  
> **username_3**: I'm pretty sure with only positive reals you get BPP instead of BQP. Negatives are crucial to achieve negative interference (i.e. cancelations).  
> **username_2**: @username_0 your example yields negative probabilities.  
> **username_0**: @JoshuaGrochow that's what I suspected, do you have a formal proof or a rough jist of how one would do that?  
> **username_0**: @DmitriUrbanowicz no? Any values of $0 \leq p_0, p_1 \leq 1$ will output positives, there is just a minus sign in the intermediate computation. Feel free to give a counterexample if you have one, but as far as I know there isn't. We can verify this by noting that for any possible output $c_i = (H \sqrt{p})_i \in \mathbb{C}$ in the vector produced by doing $H\sqrt{p}$, we convert to the new $p^\prime_i$ via doing $p^\prime_i = \vert c \vert^2 = \vert a+bi \vert ^2 = (a+bi)(a-bi) = a^2 + b^2 \geq 0$. The point is that each $p_i$ is a norm of a complex number which is always positive.  
> **username_2**: @username_0 sorry, I was wrong.  
> **username_4**: As an aside, note that there are non-asymptotical system properties that are not possible to replicate if using real numbers. As an easy example, using complex numbers in 2 dimensions gives you a system where the number of maximum orthogonal states is 2, and where there are three such basis that are [mutually unbiased](https://en.wikipedia.org/wiki/Mutually_unbiased_bases#Example_for_d_=_2), which would not be possible to describe if using real numbers.  
> **username_0**: @AbelMolina Interesting, even though they don't affect things asymptotically, could they affect constants (by this I mean not using big O type notation) for some given problem and some fixed n, in terms of number of gates required? (or some equivalent)  

---

## 0 answers

