5.3 Searching with Grover

After returning safely back to Earth, Hila and Iman have become good friends with Alice and Bob. The four of them decide to spend New Year’s Eve together. This day also coincides with the drawing of the annual quantum lottery! They know that only one of the four can win the grand prize, but who will it be? If we label our four protagonists by bitstrings, say,

Name x1x_{1} x2x_{2}
Alice 0 0
Bob 0 1
Hila 1 0
Iman 1 1

then we can model the lottery by a function f:{0,1}2→{0,1}f\colon\{0,1\}^{2}\to\{0,1\} which evaluates to 1 for the bitstring corresponding to the winner. For example, if f⁢(1,0)=1f(1,0)=1 then Hila is the winner of this year’s lottery.

How can our friends determine the winner? Using a classical algorithm they have to evaluate the function up to three times to determine the winner. Indeed, suppose that they learn that f⁢(0,1)=0f(0,1)=0 and f⁢(1,0)=0f(1,0)=0 – then they still do not know whether Alice or Iman is the winner! For archaic reasons that have long been forgotten, the rules of the lottery only allow evaluating the function once. But naturally, the lottery is happy to apply the sign oracle OfO_{f} to any two-qubit states of our protagonists’ liking – after all, it is a quantum lottery…

Alice and her friends get together and start pondering. After a while, Bob grows impatient and suggests: “Let us just follow the first few steps of Deutsch-Jozsa and Bernstein-Vazirani – surely the same trick will work once again…” The others do not really know of a better alternative, so they go ahead and prepare the state

(H⊗H)⁢(|0⟩⊗|0⟩)=|+⟩⊗|+⟩=12⁢(|00⟩+|01⟩+|10⟩+|11⟩).\displaystyle(H\otimes H)(\left|0\right\rangle\otimes\left|0\right\rangle)=% \left|+\right\rangle\otimes\left|+\right\rangle=\frac{1}{2}\bigl{(}\left|00% \right\rangle+\left|01\right\rangle+\left|10\right\rangle+\left|11\right% \rangle\bigr{)}.

Next, they hand the state to the quantum lottery, which applies the sign oracle OfO_{f} and returns the state. Let aa and bb denote the two bits that label the winner, i.e., f⁢(a,b)=1f(a,b)=1 and all other function values are zero. Then the two-qubit state returned by the lottery is the following:

12⁢(|00⟩+|01⟩+|10⟩+|11⟩−2⁢|a,b⟩)\displaystyle\quad\frac{1}{2}\bigl{(}\left|00\right\rangle+\left|01\right% \rangle+\left|10\right\rangle+\left|11\right\rangle-2\left|a,b\right\rangle% \bigr{)}
=12⁢(|00⟩+|01⟩+|10⟩+|11⟩)−|a,b⟩\displaystyle=\frac{1}{2}\bigl{(}\left|00\right\rangle+\left|01\right\rangle+% \left|10\right\rangle+\left|11\right\rangle\bigr{)}-\left|a,b\right\rangle
=|+⟩⊗|+⟩−|a⟩⊗|b⟩,\displaystyle=\left|+\right\rangle\otimes\left|+\right\rangle-\left|a\right% \rangle\otimes\left|b\right\rangle,

where the −2⁢|a,b⟩-2\left|a,b\right\rangle in the first line replaces one of the plus signs by a minus sign. After applying a Hadamard transform, they arrive at the following state:

|0⟩⊗|0⟩−H⁢|a⟩⊗H⁢|b⟩\displaystyle\quad\left|0\right\rangle\otimes\left|0\right\rangle-H\left|a% \right\rangle\otimes H\left|b\right\rangle
=|00⟩−12⁢(|0⟩+(−1)a⁢|1⟩)⊗(|0⟩+(−1)b⁢|1⟩)\displaystyle=\left|00\right\rangle-\frac{1}{2}\Bigl{(}\left|0\right\rangle+(-% 1)^{a}\left|1\right\rangle\Bigr{)}\otimes\Bigl{(}\left|0\right\rangle+(-1)^{b}% \left|1\right\rangle\Bigr{)}
=−12⁢(−|00⟩+(−1)a⁢|10⟩+(−1)b⁢|01⟩+(−1)a+b⁢|11⟩)\displaystyle=-\frac{1}{2}\Bigl{(}-\left|00\right\rangle+(-1)^{a}\left|10% \right\rangle+(-1)^{b}\left|01\right\rangle+(-1)^{a+b}\left|11\right\rangle% \Bigr{)}

Now our friends are confused and not quite sure what to do. Hila has an idea: “I don’t really like the minus sign in front of |00⟩\left|00\right\rangle. Why don’t we apply a quantum operation that looks as follows?”

|00⟩\displaystyle\left|00\right\rangle ↦−|00⟩\displaystyle\mapsto-\left|00\right\rangle (5.16)
|01⟩\displaystyle\left|01\right\rangle ↦|01⟩\displaystyle\mapsto\left|01\right\rangle
|10⟩\displaystyle\left|10\right\rangle ↦|10⟩\displaystyle\mapsto\left|10\right\rangle
|11⟩\displaystyle\left|11\right\rangle ↦|11⟩\displaystyle\mapsto\left|11\right\rangle

Iman joins in: “I think I know how to build this using a controlled-Z operation and a handful of NOTs…” In no time, our friends arrive at the following state:

−12⁢(|00⟩+(−1)a⁢|10⟩+(−1)b⁢|01⟩+(−1)a+b⁢|11⟩)\displaystyle-\frac{1}{2}\Bigl{(}\left|00\right\rangle+(-1)^{a}\left|10\right% \rangle+(-1)^{b}\left|01\right\rangle+(-1)^{a+b}\left|11\right\rangle\Bigr{)}

After only a brief moment, Alice realizes: “This two-qubit state can be written as a tensor product!”

−12⁢(|0⟩+(−1)a⁢|1⟩)⊗(|0⟩+(−1)b⁢|1⟩)=−(H⊗H)⁢|a,b⟩.\displaystyle-\frac{1}{2}\Bigl{(}\left|0\right\rangle+(-1)^{a}\left|1\right% \rangle\Bigr{)}\otimes\Bigl{(}\left|0\right\rangle+(-1)^{b}\left|1\right% \rangle\Bigr{)}=-(H\otimes H)\left|a,b\right\rangle.

Bob is elated: “Aha! We only need to apply another Hadamard transform and measure both qubits…” Can you also figure out who the winner of this year’s quantum lottery will be?

Homework 5.5 (Quantum lottery).
  1. 1.
    ​

    Write the quantum operation in Eq. 5.16 using a controlled-Z operation and a few NOT operations.

    Hint: Recall that the controlled-Z operation C⁢Z1→2CZ_{1\to 2} acts on basis states |x,y⟩\left|x,y\right\rangle as follows: If x=0x=0 then it does nothing. If x=1x=1 then it acts as a ZZ on the second qubit. You learned last week how to build it in Quirky.

  2. 2.
    ​

    Build the quantum algorithm that Alice, Bob, Hila, and Iman came up with in Quirky, and determine the winner of this year’s quantum Lottery.

Hack.
  1. 1.
    ​

    We can write the quantum operation in Eq. 5.16 as

    (NOT⊗NOT)⁢C⁢Z1→2⁢(NOT⊗NOT).\displaystyle(\mathrm{NOT}\otimes\mathrm{NOT})CZ_{1\to 2}(\mathrm{NOT}\otimes% \mathrm{NOT}).

    This works, because C⁢Z1→2CZ_{1\to 2} works as follows (from the hint and what ZZ does)

    |00⟩\displaystyle\left|00\right\rangle ↦|00⟩\displaystyle\mapsto\left|00\right\rangle
    |01⟩\displaystyle\left|01\right\rangle ↦|01⟩\displaystyle\mapsto\left|01\right\rangle
    |10⟩\displaystyle\left|10\right\rangle ↦|10⟩\displaystyle\mapsto\left|10\right\rangle
    |11⟩\displaystyle\left|11\right\rangle ↦−|11⟩\displaystyle\mapsto-\left|11\right\rangle

    This is almost what we want, if only we could switch the roles of 0 and 11 in all the input and the output bits. But this is precisely what NOT\mathrm{NOT} does! So we apply NOT\mathrm{NOT} on all bits before and after the C⁢Z1→2CZ_{1\to 2}.

  2. 2.
    ​

    The Quirky circuit looks as follows:

    [Uncaptioned image]

    This means that Iman is the winner of this year’s quantum lottery!

The quantum algorithm that our friends just discovered is a special case of Grover’s algorithm. Grovers algorithm solves the following problem: Given an oracle for a function f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\}, it finds x1,…,xn∈{0,1}x_{1},\dots,x_{n}\in\{0,1\} such that f⁢(x1,…,xn)=1f(x_{1},\dots,x_{n})=1. We can think of this problem as finding a lottery winner among 2n2^{n} participants or, less prosaically, finding an item that satisfies some property of interest in an unstructured database (by which we mean that the database entries are not sorted or similarly). By the same argument that we gave before, any classical algorithm will in the worst case need to look at all but one of the 2n2^{n} many entries before it is done (also in the average case one still needs to look at about half the entries). In contrast, Grover’s algorithm only needs to use the oracle only a number of times that is proportional to 2n\sqrt{2^{n}}, which grows much more slowly with nn! Grover’s algorithm is a very versatile tool which gives a square-root speedup for many computational problems.