Quantumania 17 - More Function, More Mystery

We ended up being slightly less impressed than we might have been about the Hadamard gate’s ability to narrow down the identity of a mystery function from four possibilities to two with a single measurement, given that we could make the same amount of progress by invoking the function once directly. If you give the function $0$ as the input, it can only output $0$ or $1$ , and that divides the four possible functions into two pairs.

Even so, there’s still something neat about the idea that we’ve “rotated a function” so that we can, with a single invocation, narrow it down to being either a constant that ignores its input or being dependent on its input, something that seems to absolutely require two invocations. I used the term balanced for the latter kind, in anticipation of the upgrade we’re going to embark on today.

That upgrade is going to show off our ability to casually string together many qubits into a register of qubits. I think it’s quite cool that we’re using terminology from classical computing. Registers in this context, as in mechanisms for temporarily storing numbers, have existed for as long as mechanical calculators (hundreds of years.) A long time ago there was something called a cash register (ask your grandma.)

We can build states for compound systems of three qubits by using the tensor product to stitch their spaces together:

\ket{0} \otimes \ket{0} \otimes \ket{0} = \ket{000}

Rather than writing out absurdly long kets as we increase the number of qubits to a large number $n$ , you’ll sometimes see this notation:

\ket{0} ^{\otimes n}

We’re just raising $\ket{0}$ to the power of $n$ (but using the tensor product.) So that’s a really quick way to say I have a system of $n$ qubits. Now, with such a system I can apply a unitary operation like Hadamard (symbolised here by $H$ ) to individual qubits:

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

If I have two qubits in $\ket{0}$ and put each through Hadamard, and multiply out:

H \ket{0} \otimes H \ket{0} = \frac{1}{2} \Big( \ket{0} + \ket{1} \Big) \Big( \ket{0} + \ket{1} \Big) = \frac{1}{2} \Big( \ket{00} + \ket{01} + \ket{10} + \ket{11} \Big)

Now for the first time (it’s a big day) we’re actually going to interpret the bit patterns in qubit tensor products as actual binary numbers. What happens if we have a system of $8$ qubits, in which $\ket{00101010}$ would signify $42$ , but ours are initially all zero, and put each them through Hadamard and multiply out?

\frac{1}{16} \Big( \ket{00000000} + \ket{00000001} + \ket{00000010} + \cdots \ket{11111101} + \ket{11111110} + \ket{11111111} \Big)

It’s an equal superposition of every number in the range $0$ to $255$ . Why is the normalisation factor $1/16$ ? Because this is Pythagoras in $256$ dimensions: all those ingredients are unit vectors, the square of the length of each is $1$ , there are $256$ of them, so the square of the “hypotenuse” of this ultra-hyper-bonkers-triangle is $256$ , thus its length is $\sqrt{256} = 16$ , so that’s what we need to divide by to shrink it down to $1$ .

In general, for $n$ qubits treated in this way the result is the state vector:

\ket{\psi} = \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \ket{x}

Here $x$ can be thought of the value between $0$ and $2^n - 1$ but represented in binary and used as the label for one of the ingredients.

Now we have what we need to upgrade our mystery function scenario so that function takes an $n$ -bit number as its input and produces a single bit as output. But to make this work we’re going to have to introduce a restriction on the mystery function that will seem a little contrived: it either ignores the input number entirely (it’s a constant), or it is balanced, meaning that for exactly half the range of possible values it produces output $1$ and for the other half $0$ . Supposing it is balanced, we have no idea which input values produce $1$ . To be sure it’s not constant, you’d have to test the function on just over half the possible input values, $2^n/2 + 1$ , potentially a huge number.

When we had one-bit input, the mystery function was wrapped in a unitary operator, by passing the first qubit straight through unchanged (at least, according to the definition) and using the result of the function to affect the second qubit’s output.

U_f \ket{A, B} = \ket{A, B \oplus f(A)}

Now we’re going to do the same thing except $A$ is our qubit register, carrying some $n$ -bit number. $B$ is just an extra qubit that will carry the encoded output, and at input it is $H \ket{1} = \ket{-}$ , so the complete input state is:

\frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} \ket{x} \otimes \ket{-}

When $U_f$ acts on this, being linear, it distributes over all the summed terms. Each term is in effect acted on like this:

U_f \Big( \ket{x} \otimes \ket{-} \Big) = U_f \left( \ket{x} \otimes \frac{\ket{0} - \ket{1}}{\sqrt{2}} \right) = \frac{1}{\sqrt{2}} \Big( \ket{x} \ket{0 \oplus f(x)} - \ket{x} \ket{1 \oplus f(x)} \Bi

This means that if $f(x) = 0$ , it adds nothing and this particular term is unchanged:

\frac{1}{\sqrt{2}} \Big( \ket{x} \ket{0 \oplus f(x)} - \ket{x} \ket{1 \oplus f(x)} \Big) = \frac{1}{\sqrt{2}} \Big( \ket{x} \ket{0} - \ket{x} \ket{1} \Big) = \ket{x} \otimes \ket{-}

Whereas if $f(x) = 1$ it in effect swaps the labels of the output bit ingredients:

\frac{1}{\sqrt{2}} \Big( \ket{x} \ket{0 \oplus f(x)} - \ket{x} \ket{1 \oplus f(x)} \Big) = \frac{1}{\sqrt{2}} \Big( \ket{x} \ket{1} - \ket{x} \ket{0} \Big) = -\ket{x} \otimes \ket{-}

A nifty way to capture this optional negative factor effect, given that $(-1)^0 = 1$ and $(-1)^{1} = -1$ , is:

(-1)^{f(x)}

And (like we saw with the single qubit version of this problem), our interest in the extra $\ket{-}$ qubit ends at this point because it is unaffected. We can focus on the input $n$ -qubit register, which now looks like this:

\frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} (-1)^{f(x)} \ket{x}

It’s starting to look a bit garbled, but it’s just saying that the state is the sum of $2^n$ different vector terms that have been flipped to negative if $f(x) = 1$ for term $x$ . For example, if $n = 3$ then there are $8$ terms represented by $\ket{x}$ in the sum, such as $\ket{000}$ , $\ket{001}$ , $\ket{010}$ , and so on up to $\ket{111}$ . If $f(101) = 1$ , then the $\ket{101}$ term will be negative in the sum. And then all will be scaled down by $1/\sqrt{8}$ to make it unitary.

As if it weren’t garbled enough, the last step is (as before) to apply Hadamard one more time. As we saw above, when we apply it to an all-zeros state $\ket{000\dots}$ , the result is an expansion containing a term for every bit pattern. Well, now we’re applying it to the sum of terms for every bit pattern. If you’re into coding, this is what you might call a nested loop. Again, supposing $n = 3$ , we have a sum of $8$ terms, some positive, some negative, and each of those will now expand out into $8$ terms, some positive, some negative, so we’ll have $64$ terms. But these can then be grouped together because there will be $8$ repetitions of $\ket{000}$ , also $8$ of $\ket{001}$ , and so on.

Actually multiplying them all out even for $n = 3$ would be rather tedious. It’s more instructive to think through how each term ends up with its effective final sign. The way Hadamard works on the basis vectors is that it only introduces a negative factor when the input is $\ket{1}$ , and it only places that negative factor on the output $\ket{1}$ term. So an all-zeros $\ket{000\dots}$ state put through Hadamard produces only positive terms.

The n=3 Deutsch-Jozsa structure: the all-zeros state passes through a Hadamard into a row of all eight 3-bit states, then a second Hadamard fans each into a column of signed copies. The all-zeros row (green) is all positive, while every other row has four plus and four minus signs that cancel to zero.

With the other terms, those with at least one $1$ , something remarkable happens: when we group the remaining $56$ multiplied-out terms into their $7$ types, among the $8$ copies of (say) $\ket{010}$ , $4$ are positive and $4$ are negative, so they cancel out. This happens for every basis vector apart from all-zeros. This shouldn’t be that surprising though, as we know that Hadamard is self-inverting: $H = H^{-1}$ . So that can only mean:

H^2 \ket{000\dots} = \ket{000\dots}

So if the mystery function is constant, and thus applies the same sign-flip to every term, there are only two possibilities. If $f(x) = 0$ , there’s no overall sign-flip:

H U_f H \ket{000\dots} = \ket{000\dots}

Whereas if $f(x) = 1$ , the sign is flipped:

H U_f H \ket{000\dots} = -\ket{000\dots}

Either way, this state will with certainty produce a $\ket{0}$ on every qubit. No other pattern has a non-zero amplitude.

The only other form the mystery function is allowed to take is to be balanced, and I said that was going to seem contrived. What it means for the $\ket{000\dots}$ state is that exactly half the terms contributing to it will be positive and half will be negative, and this will be entirely the function’s doing (Hadamard leaves all-zeros states alone.) The first (inner) Hadamard makes a term for every possible value, all of them positive, the mystery function flips the sign of half of them, and the final (outer) Hadamard creates from each a $\ket{000\dots}$ contribution that preserves the sign of the term it came from. This means that all the $\ket{000\dots}$ contributions cancel out, leaving a zero probability of measuring the all-zeros pattern.

The end result is that a measurement of $\ket{000\dots}$ will only happen if it was absolutely certain to happen, because the mystery function is constant. If it is balanced, $\ket{000\dots}$ is impossible, so something else will be found (at least one qubit will be in the $\ket{1\dots}$ state.)

Because of the peculiar contrivance of the setup, this is not at all useful. But it demonstrates how a quantum algorithm can produce a deterministic result, and seemingly explore a potentially huge problem space in a simple and practically instantaneous process. With $n = 275$ qubits, the number of basis vectors is $2^{275} \approx 10^{82}$ , about the number of atoms in the visible universe, and yet we seem to be able to probe the behaviour of a function on all of them, all at once.

Not yet regretting the time you've spent here?