6
$\begingroup$

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} $$

$\endgroup$
11
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 3, 2018 at 1:52
  • 4
    $\begingroup$ 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: cstheory.stackexchange.com/a/6657/49517 $\endgroup$ Aug 3, 2018 at 5:01
  • $\begingroup$ @NoahStephens-Davidowitz yes that's true, but I'd like to only use one positive real value per state, not two. $\endgroup$
    – Phylliida
    Aug 3, 2018 at 18:12
  • 1
    $\begingroup$ I'm pretty sure with only positive reals you get BPP instead of BQP. Negatives are crucial to achieve negative interference (i.e. cancelations). $\endgroup$ Aug 4, 2018 at 1:20
  • 1
    $\begingroup$ 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, which would not be possible to describe if using real numbers. $\endgroup$ Aug 7, 2018 at 20:51

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Ah, yes this is a fair point. The amplitudes (represented by complex numbers or real values that might be negative, both work) must be squared to get probabilities. Thus, a requirement that the probabilities themselves are positive is always satisfied, the issue occurs when you constrain the amplitudes to positive values (which is essentially what my suggestion was doing) $\endgroup$
    – Phylliida
    Aug 7, 2018 at 22:34
  • $\begingroup$ "if your amplitudes themselves are positive real numbers then your gates become classical" - this is only true if you restrict yourself to stochastic matrices. OP's example shows Hadamard gate application, which is capable of destructive interference. $\endgroup$ Aug 8, 2018 at 8:14
  • $\begingroup$ Notice that the OP is working with the absolute value squared, which gives you the probability---not the amplitude. If you, for example, applied the Hadamard gate to the basis vector $\lvert 1 \rangle$ you get $$ \frac{1}{\sqrt{2}} \, \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}\,\lvert 1 \rangle = \frac{1}{\sqrt{2}} (\lvert 0 \rangle - \lvert 1 \rangle) $$ Notice that the resulting state has non-positive entries. This is why the Hadamard allows you get destructive interference. $\endgroup$
    – user45987
    Aug 8, 2018 at 14:03
  • $\begingroup$ @SankethMenda positive-only amplitudes aren't obstacles to destructive interference: $$\frac{1}{\sqrt{2}} \, \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}\,\frac{1}{\sqrt{2}}(\lvert 0 \rangle + \lvert 1 \rangle) = \lvert 0 \rangle$$ $\endgroup$ Aug 8, 2018 at 14:43
  • $\begingroup$ And by the way, being restricted to non-negative amplitudes, there's no conceptual difference between an amplitude and corresponding probability. $\endgroup$ Aug 8, 2018 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.