5.2.2 Hadamard transform and interference

While Deutsch’s algorithm is very surprising, it achieves only a very small improvement over the best classical algorithm, namely 1 evaluation of ff instead of 2. This could be useful if evaluating ff takes a very long time, say a year. But if it takes only a millisecond, then most people would not mind to wait for two milliseconds to get the answer (and pay much less for it because they would not need to use a quantum computer)! To demonstrate the usefulness of quantum computers, we would like to speed up computations by more than just a factor of 2.

There is no hope of getting a larger speedup if we only look at functions of a single bit, since those can be fully determined by two evaluations: f⁢(0)f(0) and f⁢(1)f(1). We will therefore look more generally at functions f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} with nn input bits, since there are many more such functions (indeed, there are 22n2^{2^{n}} of them). Recall that our goal is not to evaluate a function (indeed, we can do that with a single query to the oracle) but rather to learn some interesting property of the function that relates the values it takes on different inputs. Are there properties of nn-bit functions that we can learn very efficiently by using clever quantum algorithms?

To generalize Deutsch’s algorithm, observe that its key ingredient was to introduce a Hadamard gate HH before and after the sign oracle. We can do something very similar if we have an nn-bit function. In this case, the sign oracle OfO_{f} is a quantum operation of nn qubits, so we could simply apply Hadamard gates on all qubits before and after the oracle. The quantum operation that applies Hadamards on each of the nn qubits in parallel is called the Hadamard transform. Recall from Section 3.2.3 that we can write it as follows:

H⊗⋯⊗H.\displaystyle H\otimes\dotsb\otimes H.

Let us first see what happens if we apply the Hadamard transform to a basis state. For |0⁢…⁢0⟩\left|0\dots 0\right\rangle, the result is simply the uniform superposition over all basis states:

(H⊗⋯⊗H)⁢|0⁢…⁢0⟩\displaystyle(H\otimes\dotsb\otimes H)\left|0\dots 0\right\rangle =H⁢|0⟩⊗⋯⊗H⁢|0⟩\displaystyle=H\left|0\right\rangle\otimes\dotsb\otimes H\left|0\right\rangle
=12⁢(|0⟩+|1⟩)⊗⋯⊗12⁢(|0⟩+|1⟩)\displaystyle=\frac{1}{\sqrt{2}}\left(\left|0\right\rangle+\left|1\right% \rangle\right)\otimes\dotsb\otimes\frac{1}{\sqrt{2}}\left(\left|0\right\rangle% +\left|1\right\rangle\right)
=12n⁢(|0⁢…⁢00⟩+|0⁢…⁢01⟩+…+|1⁢…⁢11⟩).\displaystyle=\frac{1}{\sqrt{2^{n}}}\left(\left|0\dots 00\right\rangle+\left|0% \dots 01\right\rangle+\ldots+\left|1\dots 11\right\rangle\right).

This state is a superposition of 2n2^{n} basis states. There is a more compact way of writing this:

(H⊗⋯⊗H)⁢|0⁢…⁢0⟩=12n⁢∑y1,…,yn∈{0,1}|y1,…,yn⟩\displaystyle(H\otimes\dotsb\otimes H)\left|0\dots 0\right\rangle=\frac{1}{% \sqrt{2^{n}}}\sum_{y_{1},\dots,y_{n}\in\{0,1\}}\left|y_{1},\dots,y_{n}\right\rangle (5.10)

The notation ∑y1,…,yn∈{0,1}\sum_{y_{1},\dots,y_{n}\in\{0,1\}} means that you compute the sum of |y1,…,yn⟩\left|y_{1},\dots,y_{n}\right\rangle for all possible choices of the bits y1,…,yny_{1},\dots,y_{n}.

More generally, the output on an arbitrary basis state is always a superposition of all 2n2^{n} basis states with all amplitudes equal except for signs. Figuring out what exactly those signs are is a bit tricky. As a warm-up, try it first for the n=1n=1 and n=2n=2 cases.

Exercise 5.4 (Two Hadamards).

Recall from Eq. 2.34 that H⁢|x1⟩=(|0⟩+(−1)x1⁢|1⟩)/2H\left|x_{1}\right\rangle=\left\lparen\left|0\right\rangle+(-1)^{x_{1}}\left|1% \right\rangle\right\rparen/\sqrt{2}, for any x1∈{0,1}x_{1}\in\{0,1\}.

  1. 1.
    ​

    Write the state H⁢|x1⟩H\left|x_{1}\right\rangle, for arbitrary x1∈{0,1}x_{1}\in\{0,1\}, as follows:

    H⁢|x1⟩=12⁢∑y1∈{0,1}(−1)???⁢|y1⟩,H\left|x_{1}\right\rangle=\frac{1}{\sqrt{2}}\sum_{y_{1}\in\{0,1\}}(-1)^{% \framebox{???}}\left|y_{1}\right\rangle,

    where ??? is some expression involving x1,y1∈{0,1}x_{1},y_{1}\in\{0,1\}. Determine this expression.

  2. 2.
    ​

    Write the state (H⊗H)⁢|x1,x2⟩(H\otimes H)\left|x_{1},x_{2}\right\rangle, for arbitrary x1,x2∈{0,1}x_{1},x_{2}\in\{0,1\}, in the form

    (H⊗H)⁢|x1,x2⟩=12⁢∑y1,y2∈{0,1}(−1)???⁢|y1,y2⟩,(H\otimes H)\left|x_{1},x_{2}\right\rangle=\frac{1}{2}\sum_{y_{1},y_{2}\in\{0,% 1\}}(-1)^{\framebox{???}}\left|y_{1},y_{2}\right\rangle,

    where ??? stands for some expression involving x1,x2,y1,y2∈{0,1}x_{1},x_{2},y_{1},y_{2}\in\{0,1\}.
    Can you determine what this expression is?

Solution.
  1. 1.
    ​

    Here ??? stands for x1⁢y1x_{1}y_{1}.

  2. 2.
    ​

    For n=2n=2,

    (H⊗H)⁢|x1,x2⟩\displaystyle(H\otimes H)\left|x_{1},x_{2}\right\rangle =(H⁢|x1⟩)⊗(H⁢|x2⟩)\displaystyle=(H\left|x_{1}\right\rangle)\otimes(H\left|x_{2}\right\rangle)
    =(12⁢∑y1∈{0,1}(−1)x1⁢y1⁢|y1⟩)⊗(12⁢∑y2∈{0,1}(−1)x2⁢y2⁢|y2⟩)\displaystyle=\left\lparen\frac{1}{\sqrt{2}}\sum_{y_{1}\in\{0,1\}}(-1)^{x_{1}y% _{1}}\left|y_{1}\right\rangle\right\rparen\otimes\left\lparen\frac{1}{\sqrt{2}% }\sum_{y_{2}\in\{0,1\}}(-1)^{x_{2}y_{2}}\left|y_{2}\right\rangle\right\rparen
    =12⁢∑y1,y2∈{0,1}(−1)x1⁢y1⁢(−1)x2⁢y2⁢|y1⟩⊗|y2⟩\displaystyle=\frac{1}{2}\sum_{y_{1},y_{2}\in\{0,1\}}(-1)^{x_{1}y_{1}}(-1)^{x_% {2}y_{2}}\left|y_{1}\right\rangle\otimes\left|y_{2}\right\rangle
    =12⁢∑y1,y2∈{0,1}(−1)x1⁢y1+x2⁢y2⁢|y1,y2⟩,\displaystyle=\frac{1}{2}\sum_{y_{1},y_{2}\in\{0,1\}}(-1)^{x_{1}y_{1}+x_{2}y_{% 2}}\left|y_{1},y_{2}\right\rangle,

    so ??? stands for x1⁢y1+x2⁢y2x_{1}y_{1}+x_{2}y_{2}.

Did you figure out the solution? Good, then you are allowed to read on!

In general, you can derive the following formula that describes the sign pattern of the amplitudes you get when applying the Hadamard transform to any nn-qubit basis state: For any x1,…,xn∈{0,1}x_{1},\dotsc,x_{n}\in\{0,1\},

(H⊗⋯⊗H)⁢|x1,…,xn⟩=12n⁢∑y1,…,yn∈{0,1}(−1)x1⁢y1+…+xn⁢yn⁢|y1,…,yn⟩.(H\otimes\dotsb\otimes H)\left|x_{1},\dots,x_{n}\right\rangle=\frac{1}{\sqrt{2% ^{n}}}\sum_{y_{1},\dots,y_{n}\in\{0,1\}}(-1)^{x_{1}y_{1}+\ldots+x_{n}y_{n}}% \left|y_{1},\dots,y_{n}\right\rangle. (5.11)

We can now generalize the Deutsch algorithm in a straightforward way. Starting with the nn-qubit basis state |0⁢…⁢0⟩\left|0\dots 0\right\rangle, we first apply the Hadamard transform, next the sign oracle OfO_{f} for the function f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} of interest, and finally another Hadamard transform. For example, for n=3n=3, this corresponds to the following Quirky circuit:

[Uncaptioned image]

For general nn, the mathematical formula for the final nn-qubit state is:

(H⊗⋯⊗H)⁢Of⁢(H⊗⋯⊗H)⁢|0⁢…⁢0⟩.\displaystyle(H\otimes\dotsb\otimes H)O_{f}(H\otimes\dotsb\otimes H)\left|0% \dots 0\right\rangle. (5.12)

Can we write down this state more explicitly? As before, we can compute this step by step. First, we apply the Hadamard transform to the all-zeros basis state. By Eq. 5.10, we obtain the uniform superposition over all basis states:

(H⊗⋯⊗H)⁢|0⁢…⁢0⟩=12n⁢∑x1,…,xn∈{0,1}|x1,…,xn⟩.\displaystyle(H\otimes\dotsb\otimes H)\left|0\dots 0\right\rangle=\frac{1}{% \sqrt{2^{n}}}\sum_{x_{1},\dots,x_{n}\in\{0,1\}}\left|x_{1},\dots,x_{n}\right\rangle.

Next we apply the sign oracle OfO_{f}:

Of⁢(H⊗⋯⊗H)⁢|0⁢…⁢0⟩\displaystyle O_{f}(H\otimes\dotsb\otimes H)\left|0\dots 0\right\rangle =12n⁢∑x1,…,xn∈{0,1}(−1)f⁢(x1,…,xn)⁢|x1,…,xn⟩.\displaystyle=\frac{1}{\sqrt{2^{n}}}\sum_{x_{1},\dots,x_{n}\in\{0,1\}}(-1)^{f(% x_{1},\dots,x_{n})}\left|x_{1},\dots,x_{n}\right\rangle.

What does the final Hadamard transform achieve? By linearity, we can apply Eq. 5.11 to each basis vector, so we obtain the following expression for the state in Eq. 5.12:

(H⊗⋯⊗H)⁢Of⁢(H⊗⋯⊗H)⁢|0⁢…⁢0⟩\displaystyle\quad(H\otimes\dotsb\otimes H)O_{f}(H\otimes\dotsb\otimes H)\left% |0\dots 0\right\rangle
=12n⁢∑x1,…,xn∈{0,1}(−1)f⁢(x1,…,xn)⁢12n⁢∑y1,…,yn∈{0,1}(−1)x1⁢y1+…+xn⁢yn⁢|y1,…,yn⟩\displaystyle=\frac{1}{\sqrt{2^{n}}}\sum_{x_{1},\dots,x_{n}\in\{0,1\}}(-1)^{f(% x_{1},\dots,x_{n})}\frac{1}{\sqrt{2^{n}}}\sum_{y_{1},\dots,y_{n}\in\{0,1\}}(-1% )^{x_{1}y_{1}+\ldots+x_{n}y_{n}}\left|y_{1},\dots,y_{n}\right\rangle
=∑y1,…,yn∈{0,1}12n⁢(∑x1,…,xn∈{0,1}(−1)x1⁢y1+…+xn⁢yn⁢(−1)f⁢(x1,…,xn))⁢|y1,…,yn⟩,\displaystyle=\sum_{y_{1},\dots,y_{n}\in\{0,1\}}\frac{1}{2^{n}}\left(\sum_{x_{% 1},\dots,x_{n}\in\{0,1\}}(-1)^{x_{1}y_{1}+\ldots+x_{n}y_{n}}(-1)^{f(x_{1},% \dots,x_{n})}\right)\left|y_{1},\dots,y_{n}\right\rangle, (5.13)

where we exchanged the two sums to obtain the last equality. For n=1n=1 this is exactly the same as Eq. 5.7. In general, however, this expression looks quite unwieldy and hard to interpret – it seems like the circuit computes some superposition of basis states, where the amplitude is some strange sum of plus and minus signs!

Let us try to get some intuition by looking at the amplitude of |0⁢…⁢0⟩\left|0\dots 0\right\rangle in Eq. 5.13. The square of this number is the probability that, when we measure the nn qubits, all outcomes are zero. Since this amplitude corresponds to y1=…=yn=0y_{1}=\ldots=y_{n}=0, it is given simply by

12n⁢∑x1,…,xn∈{0,1}(−1)f⁢(x1,…,xn).\displaystyle\frac{1}{2^{n}}\sum_{x_{1},\dots,x_{n}\in\{0,1\}}(-1)^{f(x_{1},% \dots,x_{n})}.

What does this mean? Suppose that there are NfN_{f} input bitstrings for which ff evaluates to zero and 2n−Nf2^{n}-N_{f} bitstrings for which ff evaluates to one. Then,

12n⁢∑x1,…,xn∈{0,1}(−1)f⁢(x1,…,xn)=Nf−(2n−Nf)2n=2⁢Nf−2n2n.\displaystyle\frac{1}{2^{n}}\sum_{x_{1},\dots,x_{n}\in\{0,1\}}(-1)^{f(x_{1},% \dots,x_{n})}=\frac{N_{f}-(2^{n}-N_{f})}{2^{n}}=\frac{2N_{f}-2^{n}}{2^{n}}.

There are two interesting extreme cases:1414 14 For n=1n=1, every function is either constant or balanced. For n>1n>1 this is not true (e.g., the AND function is neither constant nor balanced).

  • •
    ​

    If ff is a constant function then either Nf=0N_{f}=0 (for the all-zeros function) or Nf=2nN_{f}=2^{n} (for the all-ones function). Either way, the amplitude is ±2n/2n=±1\pm 2^{n}/2^{n}=\pm 1. Since the squares of all amplitudes should sum to 1, we conclude that all other amplitudes in Eq. 5.13 must be 0. In other words, whenever ff is constant, the state in Eq. 5.13 is simply ±|0⁢…⁢0⟩\pm\left|0\dots 0\right\rangle. If we measure all nn qubits of this state then all outcomes will be zero.

  • •
    ​

    If ff is a balanced function, which means that there are as many zeros as ones, then Nf=2n/2N_{f}=2^{n}/2 and so the amplitude is 0. This means that if we measure the state in Eq. 5.13 then we can never get all outcomes equal to zero. Hence, for a balanced function at least one of the measurement outcomes will always be one.

Note how these two cases correspond to very different patterns of interference (see Section 2.6.1). In the first case, the amplitude of |0⁢…⁢0⟩\left|0\dots 0\right\rangle gets amplified to ±1\pm 1 due to a highly focused constructive interference, while at the same time all other amplitudes simultaneously vanish due to a massively widespread destructive interference. In the second case, |0⁢…⁢0⟩\left|0\dots 0\right\rangle experiences destructive interference, causing non-zero amplitudes to pop up elsewhere. Hadamard transform illustrates the central importance of interference in quantum computing. In the next two sections, we will make crucial use of it to design quantum algorithms on a large number of qubits.