Beginners question, so please stay on the beginner's level with possible answers.

I know very well what a qubit, superposition, and entanglement is. Also, I am familiar with several physical realizations so to speak of qubits and entanglement and their lifetime, coherence factors, etc.

Still, I don't understand how a "computation" inside e.g. 1 or 2 qubits actually runs. And when I understand it correctly multiple "computations" may run in parallel? How to imagine this?

I cannot find texts that essentially explain this.

  • 2
    $\begingroup$ Related: Differences between Quantum Computing and Parallelism $\endgroup$ – Sanchayan Dutta Oct 28 '19 at 9:57
  • 1
    $\begingroup$ As long as you view quantum computation as being about "computing in parallel", you are likely to be a bit confused. Some parts of quantum computation look a little like computing in parallel, and on occasion it is useful to talk about these situations as though some things are being computed in parallel. But it's not a good way of going about understanding quantum computation as a whole: quantum computing is it's own thing. – It's good to want to get an intuition of what happens with quantum computations on one or two qubits though, to start building your intuitions of how things go. $\endgroup$ – Niel de Beaudrap Oct 30 '19 at 10:50
  • 3
    $\begingroup$ quoting a wise man: If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once. $\endgroup$ – glS Oct 30 '19 at 15:43

As I suggest in the comments, I don't think that it is going to help you to understand quantum computation in terms of parallelism. To illustrate why, I will describe a simple two-qubit computation, in which — if you were absolutely adamant — you could claim there is computation happening in parallel; but which I would suggest does not in any meaningful sense. $\def\ket#1{\lvert#1\rangle}$

Consider the following circuit, acting on some standard basis state $\ket{x}\ket{y}$ provided as input:

Circuit illustrating control-target inversion of a CNOT gate using Hadamards

To smooth the analysis slightly for those who haven't seen a lot of quantum computation, let's consider how we could most easily represent the effects of these operations on some states.

  • The middle gate, which is a $\mathrm{CNOT}$ gate ("controlled-not"), performs the following transformation of standard basis states: $$ \mathrm{CNOT} \ket{x}\ket{y} = \ket{x}\ket{y \!\oplus\! x}$$ and performs the same transformation, independently, on each term of a superposition of standard basis states. This aspect of performing things independently on individual terms is what is sometimes described as the 'parallel' behaviour of quantum computation.

  • The gates surrounding the $\mathrm{CNOT}$ gate in the circuit are Hadamard gates, $ H = \tfrac{1}{\sqrt 2}\bigl[\begin{smallmatrix} 1 & \phantom- 1 \\ 1 & -1 \end{smallmatrix}\bigr], $ which we may describe as performing the following transformation on standard basis states: $$ \ket{x} \;\xrightarrow{\;H\;}\; \tfrac{1}{\sqrt 2}\Bigl( \ket{0} + (-1)^x \ket{1} \Bigr) .$$ On pairs of standard basis states, we may represent the effect of Hadamards on both qubits by $$ \ket{x}\ket{y} \;\xrightarrow{\;H \otimes H\;}\; \tfrac{1}{2}\Bigl( \ket{00} + (-1)^y \ket{01} + (-1)^x \ket{10} + (-1)^{x \oplus y} \ket{11}\Bigr); $$ and because the Hadamard gate is self-inverse, we also have the reverse transformation of states, $$ \tfrac{1}{2}\Bigl( \ket{00} + (-1)^y \ket{01} + (-1)^x \ket{10} + (-1)^{x \oplus y} \ket{11}\Bigr) \;\xrightarrow{\;H \otimes H\;}\; \ket{x}\ket{y}. $$

So: given these observations, let's take a look at what happens when we perform the circuit illustrated above on an input state $\ket{x}\ket{y}$: reading off transformations of the state, time-step by time-step, we have $$ \begin{align} & \ket{x}\ket{y} \\[1ex]&\xrightarrow{\;H \otimes H \;} \tfrac{1}{2}\Bigl( \ket{00} + (-1)^{y} \ket{01} + (-1)^x \ket{10} + (-1)^{x \oplus y} \ket{11}\Bigr) \\[1ex]&\xrightarrow{\;\mathrm{CNOT} \;} \tfrac{1}{2}\Bigl( \ket{00} + (-1)^{y} \ket{01} + (-1)^x \ket{11} + (-1)^{x \oplus y} \ket{10}\Bigr) \\&\qquad\qquad= \tfrac{1}{2}\Bigl( \ket{00} + (-1)^{y} \ket{01} + (-1)^{x\oplus y} \ket{10} + (-1)^{x} \ket{11}\Bigr) \\&\qquad\qquad= \tfrac{1}{2}\Bigl( \ket{00} + (-1)^{y} \ket{01} + (-1)^{(x\oplus y)} \ket{10} + (-1)^{(x\oplus y) \oplus y} \ket{11}\Bigr) \\[1ex]&\xrightarrow{\;H \otimes H \;} \ket{x \!\oplus\! y}\ket{y}. \end{align}$$ In the middle of the computation, we have a superposition of standard basis states, and $\mathrm{CNOT}$ can be said to be operating independently on each of them. But if we were to describe this as "parallel computation", you should ask yourself:

  1. What is the data that the computation is acting on?
  2. What is the output of these 'parallel' processes?

It seems to me that the standard basis terms that the $\mathrm{CNOT}$ is 'acting' on, aren't data at all: they do not individually correspond to any information about the input state. Furthermore, information about individual terms in the computation aren't represented in the output. It is customary — and in some contexts, essentially correct — to describe the terms in the superposition as representing random bits (or bit-strings), and you could say that it is on this random information that the process acts in parallel; but this 'randomness' does not in any way affect the output.

What this example demonstrates is that quantum computation allows information to be stored in different ways (using different orthogonal bases) of a single-qubit or multi-qubit system, and that the way in which operations act on these different bases is determined by — but may have qualitatively different features from — the way it acts on the standard basis. It's possible to describe parts of computation as acting 'in parallel over different possibilities', but such descriptions shouldn't be taken too seriously, because the 'parallelism' is one that one cannot directly exploit, any more than you can exploit the similar 'parallelism' that exists in randomised algorithms.

  • $\begingroup$ O well I learn a lot from your answer. First drawing the CNOT has a black circle and an open circle with a plus in it.|x> and |y> are input from the left. Then |x> and |y+x> are output on the right side I suppose. So probably the |y+x> is output on the bottom connection? $\endgroup$ – Gerard Nov 1 '19 at 8:59
  • $\begingroup$ I suppose you don't already know Dirac notation: my apologies. You might be interested to know that in the complete circuit, the top wire has state $\lvert x\oplus y \rangle$, and the bottom qubit has state $\lvert y \rangle$. As an algebraic expression, we write this computation as $(H \otimes H) \, \mathrm{CNOT} \, (H \otimes H)(\lvert x\rangle \otimes \lvert y\rangle) = \lvert x\oplus y \rangle \otimes \lvert y \rangle$. There are other notational conventions which makes this expression shorter, but this is the result in any case. (It is normal to find this surprising at first.) $\endgroup$ – Niel de Beaudrap Nov 1 '19 at 9:15

Your Answer

