Quantumania 15 - Mystery Function

In electronics and regular computing, a gate is a function that takes one or more bit inputs and produces a bit output. Physically bits are represented by voltage levels in wires. A transistor is a switch that can either connect or disconnect two of its terminals so that a current can either flow through them or be blocked: what controls the switch is the voltage level at a third terminal, called the base or gate. A simplistic conceptual use case (not actually how these things are implemented):

• If you connect two transistors in series, a current can’t flow through them unless they are both switched on (conducting), so in this configuration they implement a gate called AND: Their bases receive the input bits, and if both are $1$, the output is $1$, otherwise the output is $0$.
• If you connect them in parallel, a current will be able to flow if either of them is on, so they implement an OR gate: if either input is $1$, the output is $1$.

In this way we can make building blocks of complex logic functions. Eventually if you keep playing with this idea, things will get out of hand, which is why your phone has 20 billion transistors in it, and 20 trillion transistors are manufactured every second, and we probably make more of them in a year than the number of individual grains of rice that have ever been eaten by people, and now we can have intelligent conversations with clusters of transistors.

Now, as it happens, transistors absolutely depend on semiconductor behaviour that can’t be explained classically. So in a sense, all computing is quantum computing. But that’s not what we mean by it. We’re actually talking about replacing:

• the bit as the unit of information, operated on by logic gates and assembled into registers of bits, wherein the states of individual bits remain independent, with
• the qubit, operated on by unitary transformations (which we’ll still call gates), and assembled into registers of qubits, wherein the individual qubits might not have independent states at all, so the assembly can only be understood as a whole.

That thing where you have only 30 qubits and yet this requires a billion-dimensional state space to give weight to every possible combination of their states, we want to take advantage of that somehow.

Starting off small, the most simple logical functions have a single bit input and a single bit output. In fact there are only four such functions! Two depend on their input, and two ignore it. The first two are the identity function (output is equal to input) and NOT (output is opposite of input). The other two are effectively constants, evaluating always $1$ or always $0$.

Operations on a single qubit are unitary, so they are described by a matrix U that has an inverse (they are always reversible) given by $U^\dagger$, meaning that if you apply the matrix and its conjugate transpose, the state vector is left as it was in the first place, i.e. the combination is equal to the identity matrix:

\[U U^\dagger = I\]

Bonus points if $U = U^\dagger$ (it’s hermitian) too because then it is self-inverse:

\[U U = I\]

So we already have an infinite range of operators we can apply to a single qubit. As with any linear operator, we can fully describe what it does by stating the results of applying it to the basis vectors, and indeed that is what the two columns of the matrix tell us. Take for example the spin matrix for the X axis, expressed in the Z basis (which is shorter than the fancy name: “the computational basis”):

\[X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\]

This swaps the coordinates. So it maps:

\[\vert 0 \rangle \to \vert 1 \rangle \quad \quad \vert 1 \rangle \to \vert 0 \rangle\]

or in column vector form:

\[(1, 0)^\intercal \to (0, 1)^\intercal \quad \quad (0, 1)^\intercal \to (1, 0)^\intercal\]

This is sometimes called the quantum NOT gate, but it is as likely to be called X in deference to its physical significance. Another one we saw, geometrically just the same thing but acting along a different alignment, is the Hadamard gate:

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

This turns the unit vectors of the computational basis into unit vectors of the X basis (which we’ve often been calling front $\vert f \rangle$ and back $\vert b \rangle$):

\[\vert 0 \rangle \to \vert \mathbb{+} \rangle \quad \quad \vert 1 \rangle \to \vert \mathbb{-} \rangle\]

which are themselves balanced superpositions:

\[\lvert \mathbb{+} \rangle = \frac{\lvert 0 \rangle + \lvert 1 \rangle}{\sqrt{2}} \quad \quad \lvert \mathbb{-} \rangle = \frac{\lvert 0 \rangle - \lvert 1 \rangle}{\sqrt{2}}\]

And because it’s self-inverse:

\[\vert \mathbb{+} \rangle \to \vert 0 \rangle \quad \quad \vert \mathbb{-} \rangle \to \vert 1 \rangle\]

Getting more cocky, we can think of gates (unitary transformations) that act on pairs of qubits. One of these is controlled-NOT or CNOT for short. This has a transistor-like quality to it. The state space is 4D, there are 4 basis states, so we have to say what effect the gate has on all four:

\[\vert 00 \rangle \to \vert 00 \rangle \quad \quad \vert 01 \rangle \to \vert 01 \rangle \quad \quad \vert 10 \rangle \to \vert 11 \rangle \quad \quad \vert 11 \rangle \to \vert 10 \rangle\]

See how it works? The first qubit is the control, so if it’s $0$ then the second qubit is unaffected, but if it’s $1$ the second qubit is flipped. Another way to look at it is that the second qubit is like the output of the classical XOR gate, which can be thought of as a “difference detector”: if the two inputs are the same, the output is $0$, otherwise it’s $1$. But that alone would lose information, something that happens freely in classical computing (one of the reasons why computers need fans - to blow away all the waste entropy¹.) By carrying the first qubit through unchanged, it retains the ability to be unitary.

One standard way to write XOR in this context is $\oplus$, meaning “addition, modulo 2”, i.e. divide by $2$ and keep the remainder (or to put it another way, if the result exceeds $1$, subtract $2$ from it until it doesn’t.) With this notation, CNOT is just (with commas for clarity):

\[\vert A, B \rangle \to \vert A, A \oplus B\rangle\]

where $A, B \in \lbrace 0, 1 \rbrace$, so this expands to the four possibilities given previously.

Remember, although in this specification $A$ and $B$ can only be the definite symbols $0$ and $1$, giving only the four base state combinations, the operator can apply to any state vector, which can be described by a linear combination of those four ingredients. We’ve already said enough to know what it does, because thanks to linearity, we can just apply the operator to the base ingredients (which we already have prescribed answers for) and make the same linear combination of the results.

Some of the earliest insights into the possibilities of computing this way involved considering a unitary operation formed from an unknown function on classical bits. We realised above that there are only four such functions (identity, NOT and the constants $0$ and $1$). But suppose we have one of them, and we don’t know which one, but someone has conveniently wrapped it in a unitary transform for us, $U_f$:

\[U_f \vert A, B \rangle = \vert A, B \oplus f(A)\rangle\]

i.e. the second qubit is XOR between the second qubit’s label and $f$ applied to the first qubit’s label. Again, $A$ and $B$ are only allowed to be $0$ or $1$, and the function $f$ only operates on ordinary bits given by those labels, and yet we’ve fully specified a linear operator that can act on any state, by distributing itself down to each contribution to that state made by a basis state such as $\vert 00 \rangle, \vert 01 \rangle$… That is, there’s nothing fuzzy happening here. It can all be worked out.

If we have a pair of qubits in the base states $\vert 0 \rangle$ and $\vert 1 \rangle$, which means as a combined system they are in the base state $\vert 01 \rangle$, we can put each of them through Hadamard:

\[\vert 01 \rangle \to \vert \mathbb{+}\mathbb{-}\rangle\] \[\begin{eqnarray*} \vert \mathbb{+}\mathbb{-}\rangle &=& \left[\frac{\vert 0 \rangle}{\sqrt{2}} + \frac{\vert 1 \rangle}{\sqrt{2}}\right] \left[\frac{\vert 0 \rangle}{\sqrt{2}} - \frac{\vert 1 \rangle}{\sqrt{2}}\right] \\ &=& \frac{\vert 00 \rangle}{2} - \frac{\vert 01 \rangle}{2} + \frac{\vert 10 \rangle}{2} - \frac{\vert 11 \rangle}{2} \end{eqnarray*}\]

Then we put them through $U_f$. This is a simple enough scenario that we can describe the effect of all flavours of $f$ (and thus $U_f$) on all the base states in full, and so completely grasp what’s going on. What does applying $U_f$ do?

\[U_f \vert \mathbb{+}\mathbb{-} \rangle = \frac{1}{2} \Big[ \vert 0, f(0) \rangle - \vert 0, 1 \oplus f(0) \rangle + \vert 1, f(1) \rangle - \vert 1, 1 \oplus f(1) \rangle \Big]\]

But as there are only four possible things $f$ could be, we can write down all four variants of the above gibberish. If $f$ is the identity function, outputting its input unchanged:

\[U_f \vert \mathbb{+}\mathbb{-} \rangle = \frac{1}{2} \Big[ \vert 00 \rangle - \vert 01 \rangle + \vert 11 \rangle - \vert 10 \rangle \Big]\]

Or if it’s NOT, flipping its input:

\[U_f \vert \mathbb{+}\mathbb{-} \rangle = \frac{1}{2} \Big[ \vert 01 \rangle - \vert 00 \rangle + \vert 10 \rangle - \vert 11 \rangle \Big]\]

Or if it ignores its input and is always $0$:

\[U_f \vert \mathbb{+}\mathbb{-} \rangle = \frac{1}{2} \Big[ \vert 00 \rangle - \vert 01 \rangle + \vert 10 \rangle - \vert 11 \rangle \Big]\]

Or is always $1$:

\[U_f \vert \mathbb{+}\mathbb{-} \rangle = \frac{1}{2} \Big[ \vert 01 \rangle - \vert 00 \rangle + \vert 11 \rangle - \vert 10 \rangle \Big]\]

The difference is in the pattern of positive and negative factors. Tabulating them systematically:

$f$	$\vert 00 \rangle$	$\vert 01 \rangle$	$\vert 10 \rangle$	$\vert 11 \rangle$
Identity	$+$	$-$	$-$	$+$
NOT	$-$	$+$	$+$	$-$
$0$	$+$	$-$	$+$	$-$
$1$	$-$	$+$	$-$	$+$

There are really two patterns here, each containing two variants that only differ by an overall factor of $-1$. If the function pays attention to its input, that is, $f(0) \ne f(1)$:

\[\begin{eqnarray*} U_f \vert \mathbb{+}\mathbb{-} \rangle &=& \pm \frac{1}{2} \Big[ \vert 00 \rangle - \vert 01 \rangle - \vert 10 \rangle + \vert 11 \rangle \Big] \\ &=& \pm \left[\frac{\vert 0 \rangle}{\sqrt{2}} - \frac{\vert 1 \rangle}{\sqrt{2}}\right] \left[\frac{\vert 0 \rangle}{\sqrt{2}} - \frac{\vert 1 \rangle}{\sqrt{2}}\right] \\ &=& \pm \vert \mathbb{-}\mathbb{-} \rangle \end{eqnarray*}\]

Whereas if $f$ ignores its input, $f(0) = f(1)$:

\[\begin{eqnarray*} U_f \vert \mathbb{+}\mathbb{-} \rangle &=& \pm \frac{1}{2} \Big[ \vert 00 \rangle - \vert 01 \rangle + \vert 10 \rangle - \vert 11 \rangle \Big] \\ &=& \pm \left[\frac{\vert 0 \rangle}{\sqrt{2}} + \frac{\vert 1 \rangle}{\sqrt{2}}\right] \left[\frac{\vert 0 \rangle}{\sqrt{2}} - \frac{\vert 1 \rangle}{\sqrt{2}}\right] \\ &=& \pm \vert \mathbb{+}\mathbb{-} \rangle \end{eqnarray*}\]

So after this, the first qubit is either $\vert \mathbb{-} \rangle$ or $\vert \mathbb{+} \rangle$, and this tells us if $f$ depends on or ignores its input. Now, we have plenty of measurement devices aligned for the $\lbrace0, 1\rbrace$ basis (a.k.a. the computational basis), and so to save us the trouble of having to buy a detector for the $\lbrace+, -\rbrace$ (X) basis (have you priced those things lately? I’m not made of money!), we can throw the first qubit through a Hadamard gate so it can switch back like this:

\[\vert \mathbb{+} \rangle \to \vert 0 \rangle \quad \quad \vert \mathbb{-} \rangle \to \vert 1 \rangle\]

And so if we get $0$, we know $f$ is a constant. The first strange thing about this procedure is that we read the useful output from the first qubit, while the second is in an already known, predetermined state and carries no information for us. This is despite the fact that $U_f$ is defined as changing the second qubit, not the first:

\[U_f \vert A, B \rangle = \vert A, B \oplus f(A)\rangle\]

But that’s just the definition of it in terms of the computational basis. When we put the qubits through Hadamard we reflected them into the X basis, and the definition doesn’t directly say what it does in that basis in such a simple way, although as we’ve seen, as a linear operator, it does indirectly specify its effect completely regardless of the basis being used.

The other surprising thing is that with a single evaluation of $U_f$, we appear to have narrowed down the identity of $f$ from four possibilities to two. However, this alone seems less impressive when you consider what would happen if you directly evaluated $f$ once. We can classify $f$ variants into subgroups two ways:

• Is it constant or balanced (dependent on its input)?
• What’s the output from $f(0)$?

We can arrange the four variants into a matrix according to these criteria:

	constant	balanced
$f(0) = 0$	$0$	Identity
$f(0) = 1$	$1$	NOT

So our quantum evaluation technique tells us which column it’s in, whereas classical direct evaluation tells us which row. Both methods halve the possibilities, but… along different axes? How strange.