In this blog we are going to explain how we can take a quantum state |x\rangle (basically a column vector), apply a thing called the Hadamard gate, denoted by H (and its n-dimensional counterpart H^{\otimes n}), and produce a new quantum state that looks like this:

\displaystyle H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{z=0}^{2^n - 1} (-1)^{x\cdot z} |z\rangle

The first thing I want you to notice about the above equation is that we have an |x\rangle on the left-hand side, but we have a |z\rangle on the right-hand side.

Where did the x go? And why is it now a z?

It clearly went up in to the exponent of the coefficient of |z\rangle on the right-hand side!

Two things: why did it end up there? And what is the purpose of being able to do this?

To answer the first question: it ended up there because we used some mathematical tricks (which I will explain a little further on); and the purpose? Well, it’s the usual one: we want to change the coordinate system – i.e. we want to change the basis from one which is standard in to one where we want to work in – usually in order to solve a problem that has a clearer or easier representation in the non-standard basis, whatever that is (think: things which are periodic might be better represented in a basis that expresses periodicity as rotations, as a very common example).

Let us now focus on the left-hand side |x\rangle. What is this guy? This is a register of n qubits. For example, it could be the so-called all-zeroes register, written as such in its various forms:

\displaystyle |x\rangle = |00\dots 0\rangle = |\mathbf{0}\rangle = |0\rangle^{\otimes n}

Do you recall what group we are operating in? Since these are qubits and measurement resolves in to the two-element set \{0,1\}, then we are operating in the (cyclic) group of integers modulo 2, denoted (\mathbb{Z}_2,+). And since we are allowing for n such qubits, we are in the Boolean group (\mathbb{Z}_2^n, +), which is a finite abelian group.

Thinking about what group you are working in is important because the 0 element is going to be our group (additive) identity – hence the special consideration for this all-zeroes initial state, and for trick #3 below.

But now, going back to the |x\rangle state. Suppose it is this all-zeroes state |0\rangle^{\otimes n}. Then what happens when we apply the Hadamard operator H^{\otimes n} to it?

Recall that the Hadamard transform generalises to the quantum Fourier transform in n-dimensions – as long as you are operating in the cyclic group of integers modulo 2. Again, very important that you define your group! Therefore, as a direct consequence of this statement, we have the equation at the beginning of this section.

OK, but now let’s do it without the handwaving…

The Bitwise Scalar Product

The first trick we are going to look at to derive the above formula is the following: Suppose we are operating in our cyclic group of integers modulo 2 and we have n terms x_i and y_i. For example, x might look like this: x = 101010110101010110110010010 (imagine this has n terms), with the index i running from i=0 to n, and something similar (with the same length n) for y_i. In this example, x_7 = 1.

But now suppose we want to know their sum-product; i.e. we want to multiply all their sums, pairwise:

\displaystyle \prod_{i=0}^{n-1} (x_i + y_i)

This might seem like an arbitrary request: what is so special about the sum-product? Well, one important application of such a computation is when you calculate the inner product of two vectors.

Now, there is a trick to this, which will help us dramatically in understanding what the Hadamard is doing; and I have to say: in all my reading of Quantum Information and Algorithms I have never seen it derived this way. So hopefully this is a first! Perhaps these tricks are learned in other earlier computer algorithm courses that I never took…

First, we can simply expand the product:

\displaystyle \prod_{i=0}^{n-1} (x_i + y_i) = (x_0 + y_0)(x_1 + y_1) (x_2 + y_2) \cdots(x_{n-1} + y_{n-1})

and now let us actually compute the first product:

\displaystyle \prod_{i=0}^{n-1} (x_i + y_i) = (x_0x_1+x_0y_1+y_0x_1+y_0y_1)(x_2 + y_2) \cdots (x_{n-1} + y_{n-1} )

I want you to count up the number of terms inside the first parentheses: one x_0x_1, two x_0y_1, three x_1y_0 and four x_1y_1. So there are 4 terms inside the first parentheses.

Further, the highest index (subscript) of these terms is 1 (noting that the index runs from 0 up to n-1). Thus we could infer that there are 2^{i+1} terms, but let’s see if this pattern continues by looking at the next product:

\displaystyle \prod_{i=0}^{n-1} (x_i + y_i) = (x_0x_1x_2+\cdots+y_0y_1y_2)(x_3 + y_3)\cdots(x_{n-1} + y_{n-1})

Now the number of terms inside the first parentheses is 8. This pattern is easy to predict! It should come as no surprise that each time we do this, for each i\in(0,n-1) we are going to get 2^{n} terms to sum up. Here is what it looks like after n iterations of this process:

\displaystyle \displaystyle \prod_{i=0}^{n-1} (x_i + y_i) = (x_0x_1\dots x_{n-1}+\cdots+y_0y_1\dots y_{n-1}) = \sum_{i=0}^{2^n - 1} (\textup{bitstrings of length n})_i

where on the right-hand side there are 2^n terms to sum up, and they’re all bitstrings of length n.

Trick #1

Now here is the trick!

These 2^n terms on the right-hand side of the above equation each have length n. Look at them. Look at that first one: x_0x_1\dots x_{n-1}. This guy is n digits long. More importantly, each of the x_i‘s are only ever a 0 or a 1. Therefore, this is a bit-string of length n.

Let’s look at some random middle term: x_0y_1y_2x_3\dots y_{n-1}. Same length: n, and again, each term in the sequence is either a 0 or a 1. It is also a bit-string of length n.

Now that we know what each of the 2^n summands are, let us use a shorthand notation and write z_0 := x_0x_1\dots x_{n-1}, z_1 := y_0x_1\dots x_{n-1}, z_2 := x_0y_1\dots x_{n-1}, and so on, all the way up to z_{2^n - 1} := y_0y_1\dots y_{n-1}.

Thus we have re-labelled all of the 2^n - 1 bit-strings as z_j, with j running from 0 all the way up to [/latex]2^n -1[/latex].

Now notice! This indexing runs from 0 to 2^n - 1 – because there are 2^n summands; but the previous index, i, ran from 0 up to n-1 – so we can’t use the same index letter! So that is why we are using j to index this iteration.

Thus, we have

\displaystyle \prod_{i=0}^{n-1} (x_i + y_i) = \sum_{j=0}^{2^n - 1} z_j

where a particular z_j is a bit-string of length n.

This little exercise should make clear how we go from a product of n terms to a sum of 2n terms. Not only that, we saw how we made a change of basis: we went from n terms of x, indexed by i – to 2^n terms of z indexed by j.

Now let us see if we can apply this trick to the Hadamard transform.

Applying the Trick to the Hadamard Transform

Let the initial qubit register be |x\rangle (so we are starting with n terms of the qubits in the x basis). Applying a Hadamard (by definition), element-wise, does the following transformation:

\displaystyle H^{\otimes n}|x\rangle := \frac{1}{\sqrt{2}}\left(|0\rangle + (-1)^{x}|1\rangle\right) \underbrace{\cdots}_{n\text{ times}} \frac{1}{\sqrt{2}}\left(|0\rangle + (-1)^{x}|1\rangle\right)

where x is a arbitrary bitstring of length n.

And now we see why the computational basis is so important here: the Hadamard produces a product of n terms just as before in our example above – except that now the x‘s are |0\rangle, and the y‘s are |1\rangle. So we have the exact same problem as above, just a different symbol!

Well, almost, the same problem. We already know (from Trick #1) what the answer will look like: it will be a sum of 2n terms. But what do we do about this pesky (-1)^x attached to every |1\rangle term?

Well, if the number of |y\rangle‘s in the bitstring z is even then the negative term will become positive, otherwise it will be negative. Another way to do the same calculation is to just multiply all the (-1)^{x_i} terms together for each bit i in the bitstring z. This full product of coefficients will handle the cross-multiplication cases and always provide a negative or a positive value.

So, from the above trick, we know the answer to this is going to be a sum of 2n terms, so let’s write that down:

\displaystyle \frac{1}{\sqrt{2^n}} \sum_{z=0}^{2^n-1}|z\rangle

and then just quickly insert the negative/positive corrections (inside the interior parentheses):

\displaystyle \frac{1}{\sqrt{2^n}} \sum_{z=0}^{2^n-1} \left(\prod_{i=0 | z_i = 1}^{n-1} (-1)^{x_i}\right) |z\rangle

The big product inside the parentheses handles the pesky (-1)^x coefficients introduced by the Hadamard, and this always resolves to either a +1 (for even numbers of negatives) or a -1 (for an odd number of negatives).

OK, what does this mean now?

This means that for every z_i = 1, in the bitstring z, we have a contributory (-1)^{x_i} coefficient. For example, let us look at the bitstring of length 2 special case…

There are only four terms in this case: |00\rangle, |10\rangle, |01\rangle, and |11\rangle. With coefficients they are: |00\rangle (no change, as there is no z_i = 1 in the state, (-1)^{x_0}|10\rangle (because of the 1 in the 0 entry; (-1)^{x_1}|01\rangle; and (-1)^{x_0}(-1)^{x_1}|11\rangle = (-1)^{x_0 + x_1}|11\rangle.

By looking at this simple 2-dimensional case, it should give you some idea of what is going on in the n-dimensional case.

Trick #2

Now we are going to use the fact that in each of these product cases we could have that z_i = 1. If this is the case, for all i; and since 1 is the group multiplicative identity (yet another reason why the computational basis is so useful, and, of course, knowing what your group is!), we can identically insert z_i as a multiplicative factor (in the exponent) without loss of generality:

\displaystyle H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{z=0}^{2^n-1} \left(\prod_{i=0 | z_i = 1}^{n-1} (-1)^{x_i z_i}\right) |z\rangle

where multiplication here (no operator symbol multiplication) is the element-wise (or pairwise) group multiplication.

In my opinion, this is an interesting way to express this product: the number of instances of the (-1) factor is dependent on the number of instances of z_i = 1 in the vector of bitstring z. Note that we do not explicitly need a modulo 2 in the exponent product because zero multiplied by one (in any order) is always either zero or 1. This will be different below…

Now, using the law of exponents we may write this out in full:

\displaystyle H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{z=0}^{2^n-1} \left( (-1)^{\sum_{i=0 | z_i = 1}^{n-1} x_i z_i \bmod 2}\right) |z\rangle

OK, so now we have to be clear that we are in modulo 2, so we write it explicitly.

Trick #3

But now also note that condition on the sum: the z_i = 1. We can drop that now and just sum over all i because the cases where z_i \neq 1 will result in a 0 inside the sum, and we already know that 0 is the identity element in our group!

So we can simply write the sum in the exponent without the condition:

\displaystyle H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{z=0}^{2^n-1} \left( (-1)^{\sum_{i=0}^{n-1} x_i z_i \bmod 2}\right) |z\rangle

But now we have a breakthrough!

Observe that since the exponent of (-1) is now identical to the bitwise scalar (inner) product defined as:

\displaystyle x \cdot z := \sum_{i=0}^{n-1} x_i z_i \bmod 2

…it allows us to make the stunning substitution:

\displaystyle H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{z=0}^{2^n-1} (-1)^{x \cdot z}|z\rangle

…as required.

Conclusion

There we have it. All the way from the elementary definition of the Hadamard transform, all the way to the generalised Hadmard Transform with no steps skipped and each step clearly defined.

I would say that the only things that need to be done now are to rigorously prove that

\displaystyle x \cdot z := \sum_{i=0}^{n-1} x_i z_i \bmod 2

is indeed an actual inner product, and also a little familiarity with how the Hadamard transform generalises up to n-dimensions (i.e. how it applies to a register of n qubits). From there it is really just a couple of algebraic tricks and familiarity with how a product of sums converts in to a sum of products in the group of integers modulo 2.

It should now be clear exactly what is going on when you see the formula:

\displaystyle H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{z=0}^{2^n - 1} (-1)^{x\cdot z} |z\rangle

and it is the first example where we start to see the utility of being able to place quantum states (at least their basis – and now remember that the basis is what puts numbers on to abstract things) in to the exponent of the coefficient – a.k.a. in to the phase of a qubit.

This is a very good segway in to another trick called the phase kickback trick which will be the topic of the next blog post in this series. The phase kickback trick is very similar to what is going on in the generalised Hadamard transform with the exception that it sends not a 0 or a 1, but any eigenvalue of any arbitrary operator (i.e. a gate) into the phase.