In this blog we are going to explain how we can take a quantum state (basically a column vector), apply a thing called the *Hadamard gate*, denoted by (and its -dimensional counterpart ), and produce a new quantum state that looks like this:

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

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

It clearly went up in to the *exponent* of the coefficient of 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 . What is this guy? This is a register of qubits. For example, it could be the so-called **all-zeroes** register, written as such in its various forms:

Do you recall what group we are operating in? Since these are qubits and measurement resolves in to the two-element set , then we are operating in the **(cyclic) group of integers modulo 2**, denoted . And since we are allowing for such qubits, we are in the

**Boolean group**, 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 state. Suppose it is this all-zeroes state . Then what happens when we apply the Hadamard operator to it?

Recall that the Hadamard transform *generalises* to the quantum Fourier transform in -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 terms and . For example, might look like this: (imagine this has terms), with the index running from to , and something similar (with the same length ) for . In this example, .

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

*pairwise*:

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:

and now let us actually compute the first product:

I want you to count up the number of terms inside the first parentheses: one , two , three and four . 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 up to ). Thus we could infer that there are terms, but let’s see if this pattern continues by looking at the next product:

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 we are going to get terms to sum up. Here is what it looks like after iterations of this process:

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

### Trick #1

Now here is the trick!

These terms on the right-hand side of the above equation each have length . Look at them. Look at that first one: . This guy is digits long. More importantly, each of the ‘s are only ever a 0 or a 1. Therefore, this is a **bit-string of** **length **.

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

Now that we know *what* each of the summands are, let us use a shorthand notation and write , , , and so on, all the way up to .

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

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

Thus, we have

where a particular is a bit-string of length .

This little exercise should make clear how we go from a ** product of n terms** to a

**. Not only that, we saw how we made a change of basis: we went from terms of , indexed by – to terms of indexed by .**

*sum of 2*^{n}termsNow 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 (so we are starting with terms of the qubits in the basis). Applying a Hadamard (by definition), *element-wise*, does the following transformation:

where is a *arbitrary* bitstring of length .

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 ‘s are , and the ‘s are . 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 2^{n} terms**. But what do we do about this pesky attached to every term?

Well, if the number of ‘s in the bitstring 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 terms together for each bit in the bitstring . 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 2 ^{n} terms**, so let’s write that down:

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

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

OK, what does this mean now?

This means that for every , in the bitstring , we have a contributory coefficient. For example, let us look at the bitstring of length ** 2** special case…

There are only four terms in this case: , , , and . With coefficients they are: (no change, as there is no in the state, (because of the in the entry; ; and .

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

### Trick #2

Now we are going to use the fact that in each of these product cases we could have that . If this is the case, for all ; and since 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 as a multiplicative factor (in the exponent) without loss of generality:

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 factor is dependent on the number of instances of in the vector of bitstring . 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:

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 . We can drop that now and just sum over all because the cases where 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:

But now we have a breakthrough!

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

…it allows us to make the stunning substitution:

…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

is indeed an actual inner product, and also a little familiarity with how the Hadamard transform generalises up to -dimensions (i.e. how it applies to a register of 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:

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.

Very interesting and very cool! I hadn’t yet realized the Hadamard gate could apply to more than two qubits, so this was quite educational.

One question: At the end of Trick #1, the sentence

“where a particular x_j is a bit-string of length n.”— should the“x_j”be“z_j”? (If not I may not have understood this as well as I thought I did.)Thanks Wyrd, yes you’re right. That should be a “z_j”.