## Intro to quantum computing with Q# – Part 2, Superposition

In the previous post in this series we mentioned the concept of superposition briefly. Let's use this second part to dive deeper into the mathematics of it, meet the cat of Schrödinger and try to find some simple quantum computing use cases for it.

### Superposition – introduction

Last time around, we briefly mentioned that when a qubit is in superposition, “it is both 0 and 1 at the same time”. This is a rather simplistic and not necessarily accurate description, but one that is commonly used in introductory texts and popular science articles, as it manages to convey the weirdness of conceptualizing quantum states.

Since we have a lot of room here, we now have, however, the luxury to emphasise that such a statement is really stripped of any mathematical or physical substance. Thankfully, we looked a little at the mathematics behind the qubit already, so we are now well positioned to describe superposition more accurately. Namely, we know that the quantum state of a qubit is a linear combination of $\ket{0}$ and $\ket{1}$.

In other words, given a a qubit state that we already discussed:

$$\ket{\varphi} = \alpha\ket{0} + \beta\ket{1}$$

we can say that a qubit is in a superposition when both amplitudes (and thus, probabilities) $|\alpha|$ and $|\beta|$ are non-zero.

The ontological aspect of the superposition, and in a broader sense, the entire quantum theory, is a lot more blurry and depends on the epistemology we would choose to subscribe to.

### Quantum mechanical view

In 1935, Austrian physicist Erwin Schrödinger published one of the most famous papers in the history of physics, “Die gegenwärtige Situation in der Quantenmechanik” (English translation is available here), in which he proposed a thought experiment around …a cat.

We'll let Schrödinger himself explain the experiment:

“A cat is penned up in a steel chamber, along with the following diabolical device (which must be secured against direct interference by the cat): in a Geiger counter there is a tiny bit of radioactive substance, so small that perhaps in the course of one hour one of the atoms decays, but also, with equal probability, perhaps none; if it happens, the counter tube discharges and through a relay releases a hammer which shatters a small flask of hydrocyanic acid. If one has left this entire system to itself for an hour, one would say that the cat still lives if meanwhile no atom has decayed. The first atomic decay would have poisoned it. The $\psi(x,t)$ function for the entire system would express this by having in it the living and the dead cat (pardon the expression) mixed or smeared out in equal parts.”

The cat has since gone to establish itself one of the symbols of quantum theory and has gained a firm position in popular culture. There have been countless references to the dead-and-alive-at-the-same-time cat in movies, books, video games and many other areas of our society. And just so that you see that physicists can have a good sense of humor too, have a quick look at one of the most popular quantum mechanics undergraduate textbooks – “Introduction to Qunatum Mechanics” by David Griffiths, which has a cat that is alive on the front cover, and a cat that is dead on the back cover.

There are plenty of competing interpretations of quantum mechanics, which can be used to explain or at least interpret the paradox, the most prevalent of which is the “Copenhagen interpretation”, championed by Niels Bohr and several other physicists that were close to him, such as Werner Heisenberg. In the view adopted in the “Copenhagen interpretation”, the superposition or, for that matter, the wave function describing a quantum object, does not describe the nature or reality in any way, nor are we allowed to reason about the reality behind a quantum object until it's actually measured. In other words, it is impossible disassociate the reality responsible for the quantum phenomena from the measurement itself, as we can only observe trace effects of quantum objects on the measurement apparatus and only infer their existence that way. This is fundamentally different from classical macro-scale physics, where systems, their state and behavior can be independently observed.

Within that view, superposition is a purely mathematical concept describing relations between various probability amplitudes of finding a particle at a given position or in a given quantum state. Thus, superposition is merely a tool that allows us to express our probabilistic expectations for the measurements. Within that thought framework, the cat paradox is no longer a paradox.

As Arkady Plotnitsky puts it in his excellent publication, with the elegance far superior to the parlance of this blog post:

“if (…) quantum states are seen (…), as defined by the $\psi$-function, strictly as mathematical entities encoding and enabling expectation catalogues concerning the outcome of possible experiments – rather than describing the behavior of quantum systems, in particular between experiments – Schrödinger's thought experiment presents no problem”.

### Superposition mathematics for a single qubit

Now that we have established (or rather, in the spirit of Copenhagen, stepped around) the ontological basics, let's look at how we can put our qubit in a superposition and what are the quantum computational consequences of doing so. Of course superposition is one of the critical aspects of quantum computing – without it, the qubit could only represent the two binary states of 0 and 1, which would strip it of any possible advantages over classical computing.

In quantum mechanics, arbitrary transformations of the quantum state are not possible. Instead, time evolution of a quantum state is always represented by linear unitary transformations of the associated vector space. This is taken as an axiom, and is one of the postulates of quantum mechanics. The transformations are represented by matrices and in physics, in order for a given transformation matrix $U$ to be unitary, its Hermitian adjoint (a generalized version of conjugate transpose $U^*$ from linear algebra) $U^\dagger$ must be its own inverse. In other words, $U$ must satisfy the condition:

$$U^\dagger U = I$$

where I is the identity matrix. Therefore, algebraically speaking, in order to transform the state of a qubit into a uniformly distributed superposition we need to linearly transform it using the Hadamard transformation, represented by the Hadamard matrix, named like this after the French mathematician Jacques Hadamard.

As we already mentioned, quantum transformations are described by matrices – more specifically, $2^n * 2^n$ sized unitary matrices, where n stands for the number of qubits the gate acts on.

### Superposition in quantum computing

In quantum computing, quantum state transformations are represented – similarly to the analogous concept from classical computing – by computational gates. We will look in details at various gates and circuits in the next post in this series, for now we will just say tt Hadamard gate acts on a single qubit, hence it's corresponding matrix size is 2×2. The Hadamard H matrix is shown below:

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

Since $\frac{1}{\sqrt{2}}$ appears in each matrix element, we know from linear algebra that we can simplify the equation:

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

Our Hadamard matrix is not just unitary, it is also self adjoint (Hermitian) – so it's equal to its own conjugate transpose. In other words:

$$H = H^\dagger$$

This means that the following holds:

$$HH^\dagger = HH = I$$

We are starting to get side tracked by linear algebra again, so let's go back to our qubit. Suppose we start with a qubit prepared to be $\ket{0}$. At this point we know it's classical bit value would be 0, because $\alpha = 1$ and $\beta = 0$, so the probability of measuring a 0 is 100%. We now apply the Hadamard gate by multiplying our ket by the Hadamard matrix.

$$H(\ket{0}) = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} &-\frac{1}{\sqrt{2}} \end{bmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix} = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 0 \end{bmatrix} + \frac{1}{\sqrt{2}}\begin{bmatrix} 0 \\ 1 \end{bmatrix}$$

Similarly, for $\ket{1}$:

$$H(\ket{1}) = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} &-\frac{1}{\sqrt{2}} \end{bmatrix}\begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{bmatrix} = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 0 \end{bmatrix} – \frac{1}{\sqrt{2}}\begin{bmatrix} 0 \\ 1 \end{bmatrix}$$

The above representation is usually more readable and understandable when beginning to work with quantum computing, especially without deeper background in physics. That said, we can also write this in a more compact Dirac notation:

$$H(\ket{0}) = \frac{1}{\sqrt{2}}\ket{0} + \frac{1}{\sqrt{2}}\ket{1} = \frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$$

$$H(\ket{1}) = \frac{1}{\sqrt{2}}\ket{0} – \frac{1}{\sqrt{2}}\ket{1} = \frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$$

The difference between the two cases (starting the process with a $\ket{0}$ vs $\ket{1}$) is the amplitude sign (+ vs -), but notice that in order to obtain classic probabilities we need to square the amplitudes anyway, and therefore we are equally likely (50%) to get $\ket{0}$ and $\ket{1}$ in both cases. In other words, the Hadamard gate has created a uniformly distributed superposition for us in both situations.

Another interesting property of the Hadamard gate, is that like all quantum gates, it is reversible. That is not surprising, since gates are unitary operators, which means that property is guaranteed by the underlying mathematics. Thus, applying Hadamard gate again, returns us back to the state which we started from. This is a property that does not apply to all classical computing gates – for example AND or XOR are not reversible.

In the mathematical terms, we can verify it in the following way (going back to $\ket{0}$):

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

and (going back to $\ket{1}$):

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

### Superposition – Q# code

After long and winding road, we have finally arrived at the happy place that allows us to write some Q# code. We can use the example from previous blog post as the starting point – remember that we prepared a qubit there, and then measured its value. All of that, for a reminder, is shown again below (including its related C# driver code).

The code prepares a single qubit, and measures it in the Pauli Z basis, repeating this a given amount of times (1000), keeping track of the total tally of 0s and 1s measured. As we already determined last time, such set up will yield 100% 0s as the qubit is in the base state of $\ket{0}$ and when we measure it in the Pauli Z basis we are guaranteed to get a 0.

In order to apply the uniformly distributed superposition, we can sneak in the Hadamard gate, represented by the aptly named H() method in Q#, right into the exact same code snippet – before we measure the qubit. This is shown next.

If we now run this code using the same C# driver code as we had last time, we should see result that is close to this:

We can pause here for a moment, and marvel at our astonishing achievement. Sure, this is running on a quantum simulator only, but should this Q# code be deployed to a real Q# compatible quantum computer (which, hopefully, will be possible soon using Azure Quantum), it would, in principle, work the same way. So let's squint our eyes for a moment and imagine that it is indeed a real quantum computer that we are interacting with. What we have tapped into here, is true, nature-guaranteed randomness. The bits are fully random, with 50% chance of being 0 or 1, and those probabilities are guaranteed by the laws of quantum mechanics and the underlying mathematics we already looked at.

The true randomness right at the heart of our reality might be very difficult to make peace with. In a 1926 letter to Max Born, Albert Einstein, who couldn't agree with the probabilistic core of quantum mechanics or Heisenberg's uncertainty principle, and was convinced the ultimate nature of reality is fundamentally deterministic, wrote:

“The theory produces a good deal but hardly brings us closer to the secret of the Old One. I am at all events convinced that He does not play dice.” (org. “Die Theorie liefert viel, aber dem Geheimnis des Alten bringt sie uns kaum näher. Jedenfalls bin ich überzeugt, daß der nicht würfelt.”).

We can close off this post by doing something useful, for a change. Let's leverage the quantum superposition to build a true random number generator in Q#. Of course at this point, it should not be very surprising to anyone, given we just managed to generate random bits. As all computing students know, once we have enough bits we can form numbers out of them – such as for example 16-, 32- or 64-bit integers.

The final piece of our Q# code does just that, it generates an array of 32 random bits, which we can use to construct a truly random number.

The code is very similar to the code we used earlier, and the Hadamard gate is of course at the center of all interesting action, guaranteeing a uniformly distributed superposition. It is worth briefly mention the somewhat esoteric syntax used for inserting elements into an array: set array w/= idx <- value. To be more precise, this is in fact a copy-and-update expression, since arrays in Q# are immutable. Therefore, this is really not the most efficient way of keeping track of our random 32 bits, but it was a good occasion to introduce this useful language construct.

Finally, the C# driver to run the code and then convert the random bits into a 32-bit unsigned integer looks like this:

The output of this code would be something like:

And there we have it – we have achieved something useful with a quantum computer. In fact, if we think about it, it is something no classical computer can ever claim – a mathematically guaranteed, underpinned by the basic laws of nature, true random number.

### Summary

In this part 2 of the blog post series we had a look at the epistemology, mathematics and Q# code behind the superposition. We discussed the algebraic meaning of quantum transformations and also briefly touched upon the concept of quantum gates. Finally, we managed to unsettle Albert Einstein a bit and created a first somewhat useful program in Q#.

In the next post in this series we will be looking in more details at quantum gates and attempt to discuss the important ones.