HW 6 - Quantum Algorithms

1: Deutsh-Josza Algorithm on a 4-Qubit System

Question

Deutsch-Josza algorithm. The text (skip the codes) on Kasirajan, pp. 293-297 follows the
kets of a 4-qubit register and one helper (ancilla) qubit step by step for a balanced function.
a. Repeat all steps, but with a constant function with output 1.
b. What are the measurement options for the register qubits at the end? Did the algorithm
work correctly? Explain.
c. How would your final state (just before the measurement) change if your constant
function had output 1?

Let's begin with our setup:

Pasted image 20240523214222.png
For clarity, each $| ψ_{k} ⟩$ gives the state of the system at gate level $k$ using the given configuration above. As such:

| ψ_{0} ⟩ = | 0000 ⟩ | 0 ⟩

\begin{aligned} | ψ_{1} ⟩ & = H^{\otimes 4} | 0000 ⟩ X | 0 ⟩ \\ = \frac{1}{\sqrt{2^{4}}} ⨂_{i = 1}^{4} (| 0 ⟩ + | 1 ⟩) \otimes | 1 ⟩ \\ = \frac{1}{4} (| 0 ⟩ + 1) \otimes (| 0 ⟩ + | 1 ⟩) \otimes (| 0 ⟩ + | 1 ⟩) \otimes (| 0 ⟩ + | 1 ⟩) \otimes | 1 ⟩ \\ = \frac{1}{4} (| 0000 ⟩ + | 0001 ⟩ + \dots + | 1111 ⟩) \otimes | 1 ⟩ \\ = \frac{1}{4} \sum_{x = 0}^{2^{4} - 1} | x ⟩ \otimes | 1 ⟩ \end{aligned}

\begin{aligned} | ψ_{2} ⟩ & = \frac{1}{4} \sum_{x = 0}^{2^{4} - 1} | x ⟩ \otimes \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) \end{aligned}

Now we apply the constant oracle function given in the figure above. We know it's the right oracle since:

$| x ⟩$ just gets passed through
If $| y ⟩ = | 1 ⟩$ then we output $X | y ⟩ = X | 1 ⟩ = | 0 ⟩ = | y \oplus f (x) ⟩ = | \neg f (x) ⟩ = | 0 ⟩$ in this case since $f (x) = 1$ .
If $| y ⟩ = | 0 ⟩$ then we output $X | y ⟩ = X | 0 ⟩ = | 1 ⟩ = | y \oplus f (x) ⟩ = | f (x) ⟩ = | 1 ⟩$ since still $f (x) = 1$ for our oracle.
As such:

\begin{aligned} | ψ_{3} ⟩ & = \frac{1}{4} \sum_{x = 0}^{2^{4} - 1} | x ⟩ \otimes X \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) \\ = \frac{1}{4} \sum_{x = 0}^{2^{4} - 1} | x ⟩ \otimes \frac{1}{\sqrt{2}} (- | 0 ⟩ + | 1 ⟩) \end{aligned}

Then we 'un- $H$ ' to get the result of the algorithm:

\begin{aligned} | ψ_{4} ⟩ & = \frac{1}{4} H^{\otimes 4} \sum_{x = 0}^{2^{4} - 1} | x ⟩ \otimes \frac{1}{\sqrt{2}} (- | 0 ⟩ + | 1 ⟩) \\ = \frac{1}{4} ⨂_{i = 1}^{4} H (| 0 ⟩ + | 1 ⟩) \otimes \frac{1}{\sqrt{2}} (- | 0 ⟩ + | 1 ⟩) \\ = \frac{1}{\sqrt{2^{5}}} \sqrt{2^{4}} ⨂_{i = 1}^{4} | 0 ⟩ \otimes (- | 0 ⟩ + | 1 ⟩) \\ = \frac{1}{\sqrt{2}} (- | 00000 ⟩ + | 00001 ⟩) \end{aligned}

We just measure the left 4 qubits, which are always $| 0000 ⟩$ . Hence, we have to measure a 0 into our classical register. This is as expected, since iff we measure a pure 0, then we have a constant function (which we do as I showed in the explanation of our oracle).

If instead we read a final state that had at least one state in the left 4 qubits where not all the qubits were 0, then the algorithm dictates that part of $f (x)$ is non-constant. Since $f$ is given as explicitly either balanced or constant, then logic entails that it be balanced.

2: Deutsh-Josza Algorithm w/ Hidden String

Question

Deutsch-Josza algorithm. Kasirajan mentions a hidden string that is applied to the register
qubits right before and right after the oracle.
a. In Kasirajan’s worked example of the balanced function on pp. 293-297, no hidden string
was included. This effectively means that the hidden string was 0, or |0000>. In his code
and circuit diagram for the balanced function, he uses the hidden string 15, or |1111>. We
can see this in his circuit diagram in Fig. 7.14: X gates are applied to all four register
qubits right before and right after the oracle (sequence of cNOTs). Repeat the steps from
Kasirajan, but with the hidden string applied. How does this change affect the final state
vector compared to Kasirajan’s calculations? And how does it affect the measurement
outcome and the conclusion as to whether the function is constant or balanced?
b. Now do it one more time, but with a hidden string of your choice, i.e. pick a number from
1-14 and imprint it by placing X-gates onto the correct qubits before and after the oracle.
How does this change affect the final state vector compared to Kasirajan’s calculations?
And how does it affect the measurement outcome and the conclusion as to whether the
function is constant or balanced?

Consider the following application of the Deutsch-Josza Algorithm, where the oracle given is the series of controlled-NOT gates:

Pasted image 20240523220950.png

Kasirajan makes mention of a "hidden string" that is applied to the register qubits right before and after being sent to the oracle. He is talking about the $X$ gates that normally aren't in the algorithm, which are applied to $| x ⟩$ right before and after the oracle.

We'll use the given circuit, which has the hidden string $| 1111 ⟩$ (implied by how all the $X$ 's are run before and after the algorithm) and see what happens. As with the last problem, we'll use $| ψ_{k} ⟩$ to indicate the $k$ -th step in the circuit above.

| ψ_{0} ⟩ = | 0000 ⟩ | 0 ⟩

\begin{aligned} | ψ_{1} ⟩ & = H^{\otimes 4} ⨂_{i = 1}^{4} | 0 ⟩ \otimes X | 0 ⟩ \\ = ⨂_{i = 1}^{4} \frac{1}{\sqrt{2}} (| 0 ⟩ + | 1 ⟩) \otimes | 1 ⟩ \\ = \frac{1}{4} ⨂_{i = 1}^{4} (| 0 ⟩ + | 1 ⟩) \otimes | 1 ⟩ \\ = \frac{1}{4} (| 0 ⟩ + | 1 ⟩) \otimes (| 0 ⟩ + | 1 ⟩) \otimes (| 0 ⟩ + | 1 ⟩) \otimes (| 0 ⟩ + | 1 ⟩) \otimes | 1 ⟩ \\ = \frac{1}{4} (| 00 ⟩ + | 01 ⟩ + | 10 ⟩ + | 11 ⟩) \otimes (| 00 ⟩ + | 01 ⟩ + | 10 ⟩ + | 11 ⟩) \otimes | 1 ⟩ \\ = \frac{1}{4} (| 0000 ⟩ + \dots + | 1111 ⟩) \otimes | 1 ⟩ \\ = \frac{1}{4} \sum_{x = 0}^{2^{4} - 1} | x ⟩ \otimes | 1 ⟩ \end{aligned}

\begin{aligned} | ψ_{2} ⟩ & = \frac{1}{4} X^{\otimes 4} ⨂_{i = 1}^{4} | 0 ⟩ + | 1 ⟩ \otimes H | 1 ⟩ \\ = \frac{1}{4} ⨂_{i = 1}^{4} X (| 0 ⟩ + | 1 ⟩) \otimes H | 1 ⟩ \\ = \frac{1}{4} ⨂_{i = 1}^{4} | 0 ⟩ + | 1 ⟩ \otimes \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) \\ = \frac{1}{\sqrt{2^{5}}} \sum_{x = 0}^{2^{4} - 1} | x ⟩ \otimes (| 0 ⟩ - | 1 ⟩) \end{aligned}

To help for this next part, use the truth table 7.2 provided to get what $q_{4}$ is:

\begin{aligned} | ψ_{3 - 6} ⟩ & = \frac{1}{\sqrt{2^{5}}} c X_{0, 1, 2, 3; 4} \sum_{x = 0}^{2^{4} - 1} (- 1)^{f (x)} | x ⟩ \otimes (| 0 ⟩ - | 1 ⟩) \end{aligned}

where $f (x)$ is the odd-parity function. Notice that the oracle in question here just flips the right state to $- | 0 ⟩ + | 1 ⟩$ if there's an odd number of 1's in the state. Otherwise it just leaves it alone. As a result:

\begin{aligned} | ψ_{3 - 6} ⟩ = \frac{1}{\sqrt{2^{5}}} ( & | 00000 ⟩ - | 00001 ⟩ \\ - | 00010 ⟩ + | 00011 ⟩ \\ - | 00100 ⟩ + | 00101 ⟩ \\ + | 00110 ⟩ - | 00111 ⟩ \\ \dots) \end{aligned}

Notice that all the kets with an odd number of 1's have -'s in front. Then we continue with our $X$ gates:

\begin{aligned} | ψ_{7} ⟩ & = X_{0 - 3} \frac{1}{\sqrt{2^{5}}} (| 00000 ⟩ - | 00001 ⟩ \\ - | 00010 ⟩ + | 00011 ⟩ \\ - | 00100 ⟩ + | 00101 ⟩ \\ + | 00110 ⟩ - | 00111 ⟩ \\ \dots \\ = \frac{1}{\sqrt{2^{5}}} X_{0 - 4} (| 0000 ⟩ \otimes (| 0 ⟩ - | 1 ⟩) - | 0001 ⟩ (| 0 ⟩ - | 1 ⟩) - | 0010 ⟩ \otimes (| 0 ⟩ - | 1 ⟩) + \dots) \\ = \frac{1}{\sqrt{2^{5}}} X_{0 - 4} (| 0000 ⟩ - | 0001 ⟩ - | 0010 ⟩ + \dots + | 1111 ⟩) \otimes (| 0 ⟩ - | 1 ⟩) \\ = \frac{1}{\sqrt{2^{5}}} (| 1111 ⟩ - | 1110 ⟩ - | 1101 ⟩ + \dots + | 0000 ⟩) \otimes (| 0 ⟩ - | 1 ⟩) \\ = \frac{1}{\sqrt{2^{5}}} (| 0000 ⟩ - | 0001 ⟩ - | 0010 ⟩ + \dots + | 1111 ⟩) \otimes (| 0 ⟩ - | 1 ⟩) \end{aligned}

So in this case the $X_{0 - 3}$ gate doesn't do anything to our state. For the last step:

\begin{aligned} | ψ_{8} ⟩ & = \frac{1}{\sqrt{2^{5}}} H^{\otimes 4} (| 0000 ⟩ - | 0001 ⟩ - | 0010 ⟩ + \dots + | 1111 ⟩) \otimes (| 0 ⟩ - | 1 ⟩) \\ = ⨂_{i = 1}^{4} \frac{1}{\sqrt{2}} H (| 0 ⟩ - | 1 ⟩) \otimes \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) \\ = ⨂_{i = 1}^{4} | 1 ⟩ \otimes \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) \\ = \frac{1}{\sqrt{2}} | 1111 ⟩ \otimes (| 0 ⟩ - | 1 ⟩) \end{aligned}

We measure just the $| x ⟩$ part, so we get 1111, just the same as Kasirjan's calculation with a number = 0 instead. Furthermore, we measured a non-zero number, implying the function is balanced (as it is). This implies using the hidden string doesn't change anything (at least in this specific case).

Let's see if it changes if we use the hidden string number = 0101. Doing our calculations again we get to:

| ψ_{1} ⟩ = \frac{1}{4} \sum_{x = 0}^{2^{4} - 1} | x ⟩ \otimes | 1 ⟩

\begin{aligned} | ψ_{2} ⟩ & = \frac{1}{4} X_{0, 2}^{\otimes 2} ⨂_{i = 1}^{4} | 0 ⟩ + | 1 ⟩ \otimes H | 1 ⟩ \\ = \frac{1}{4} (| 0 ⟩ + | 1 ⟩) \otimes (| 0 ⟩ + | 1 ⟩) \otimes (| 0 ⟩ + | 1 ⟩) \otimes (| 0 ⟩ + | 1 ⟩) \otimes \frac{1}{\sqrt{2}} (| 0 ⟩ + | 1 ⟩) \end{aligned}

It didn't change anything! As a result, the rest of our calculations reign exactly the same! But when we return back to our layer of hidden string $X$ gates at $| ψ_{7} ⟩$ :

\begin{array}{r} | ψ_{7} ⟩ = X_{0, 2} \frac{1}{\sqrt{2^{5}}} (| 0000 ⟩ - | 0001 ⟩ - | 0010 ⟩ + \dots + | 1111 ⟩) \otimes (| 0 ⟩ - | 1 ⟩) \end{array}

We need to swap $| 0000 ⟩$ 's sign with $| 1010 ⟩$ 's sign, swap $| 0001 ⟩$ 's sign with $| 0100 ⟩$ 's sign, and so on. But in this case the kets with an odd number of 1's have a $-$ phase, while the other's have a $+$ phase. As such, since if we do the swap just on $q_{0}, q_{2}$ then:

X | q_{0} q_{1} q_{2} q_{3} ⟩ = | \neg q_{0} q_{1} \neg q_{2} q_{3} ⟩

Notice that if $q_{0} \oplus q_{1} \oplus q_{2} \oplus q_{3} = 0$ then negating the $q_{0}, q_{2}$ will just either:

add a 1 and remove a 0, then add a 1 then remove a 0 (net gain of 2 added 1's)
add a 1 and remove a 0, then remove a 1 and add a 0 (net gain of 0 added 1's)
do the same in reverse (net gain of 0 added 1's)
add a 0 and remove a 1, repeat (neg gain of -2 added 1's)
In each case, we maintain the parity of the 1's, so then the $X$ gate doesn't do anything in this case. As a result our calculations are the same (just as we expected and saw with Kasirajan's calculations):

| ψ_{8} ⟩ = \frac{1}{\sqrt{2}} | 1111 ⟩ \otimes (| 0 ⟩ - | 1 ⟩)

This is likely due to the fact that our number had an even parity amount of 1's. Namely, all the examples done had a number where the number of 1's was even. If we had done a number like number = 0001 then we would've gotten a different result. This is because applying $X_{1}$ before the oracle wouldn't change anything (all states have the same phase); however, applying it after the oracle would force some of the states, which some have different signs, to swap phases. This wouldn't change the measurements, but it would add a global negative phase to our answer, as some states just gain or lose phase in equal parts. Using Quantum Circuit Composer shows that for this number we get:

| ψ_{8} ⟩ = \frac{1}{\sqrt{2}} | 1111 ⟩ \otimes (- | 0 ⟩ + | 1 ⟩)

which is just a negative global phase of our other $| ψ_{8} ⟩$ 's.

3: Grover's Algorithm on a 3-Qubit System

Question

Grover’s algorithm. The text (again skip the codes) on Kasirajan, pp. 323 (last line) -326
follows the kets through Grover’s algorithm for 3 qubits.
a. Fill in some details: Show how to get equations 7.137-7.139. Note here: Kasirajan talks
about each state being changed by a factor of
μ - a i. This fell out of the sky a little bit...
Use the diffusion operator from class, “2|ψ><ψ| - I” applied to your kets each iteration
and compare your result to Kasirajan’s for each step.
b. Now do one more Grover iteration. Based on your results, what is the optimum number
of Grover iterations for 3 qubits with one correct solution/one entry to find?

Using the following circuit that does Grover's Algorithm:

Pasted image 20240524104911.png

a: Filling in the Details

We're going to fill in some details that Kasirajan doesn't for his computation. First, he applies the layer of $H^{\otimes 3}$ on $| x ⟩$ to get everything into superposition:

{| x ⟩}^{\otimes 3} | y ⟩ = | ψ_{1} ⟩ = {| s ⟩}^{\otimes 3} \otimes \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩)

We apply the first iteration of the oracle $\hat{O}$ , listed above, which only flips the $ω = | 010 ⟩$ state as that's the only state that has all control bits set to 1's:

| ψ_{2} ⟩ = \hat{O} {| s ⟩}^{\otimes 3} \otimes \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) = \frac{1}{\sqrt{2^{3}}} (| 000 ⟩ + \dots - | 010 ⟩ + \dots + | 111 ⟩) \otimes \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩)

Then we apply the Grover Diffusion Operator in more detail. First, we apply our Hadamards (Eq. 7.137):

\begin{aligned} | ψ_{3} ⟩ & = H^{\otimes 4} | ψ_{2} ⟩ \\ = H^{\otimes 3} \frac{1}{\sqrt{2^{3}}} (| 000 ⟩ + \dots - | 010 ⟩ + \dots + | 111 ⟩) \otimes H \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) \\ = (\frac{- 1}{\sqrt{2^{3}}} | 010 ⟩ + \frac{1}{\sqrt{2^{3}}} \sum_{x \in {0, 1}^{n}, x \neq 010} | x ⟩) \otimes | 1 ⟩ \end{aligned}

so instead of diving into the calculation for the 3-qubit case specifically. Let's look at the broad sense of what's going on. Use instead the operator $2 | s ⟩ ⟨ s | - I$ :

\begin{aligned} | ψ_{3} ⟩ & = (2 | s ⟩ ⟨ s | - I) | ψ ⟩ \\ = 2 | s ⟩ ⟨ s | ψ ⟩ - | ψ ⟩ \end{aligned}

Let's explore $⟨ s | ψ ⟩$ for a moment. For $n$ -qubits:

\begin{aligned} ⟨ s | ψ ⟩ & = \sum_{i = 1}^{2^{n} - 1} \underset{= χ (s_{i} = ψ)}{\underset{⏟}{⟨ s_{i} | ψ ⟩}} \\ = \underset{from s with ψ \neq ω}{\underset{⏟}{\sum_{x = 0, x \neq ω}^{2^{n} - 1} \frac{1}{\sqrt{2^{n}}} \cdot \frac{1}{\sqrt{2^{n}}}}} - \underset{from ω}{\underset{⏟}{\frac{1}{\sqrt{2^{n}}} \cdot \frac{1}{\sqrt{2^{n}}}}} \\ = \frac{1}{2^{n}} (2^{n} - 1 - 1) \\ = \frac{2^{n} - 2}{2^{n}} \end{aligned}

Notice that we have here $\sqrt{2^{n}} μ = \sqrt{N} μ = ⟨ s | ψ ⟩$ as we expect. Thus apply this into our transformation (ignore the ancilla qubit for now):

\begin{aligned} | ψ_{3} ⟩ & = 2 | s ⟩ \frac{2^{n} - 2}{2^{n}} - | ψ_{3} ⟩ \\ = \frac{2^{n} - 2}{2^{n - 1}} \frac{1}{\sqrt{2^{n}}} \underset{| ω ⟩ \in}{\underset{⏟}{(| 000. . . ⟩ + \dots + | 111. . . ⟩)}} - \frac{1}{\sqrt{2^{n}}} (| 00. . . ⟩ + \dots - | ω ⟩ + . . . + | 111. . . . ⟩) \\ = \frac{1}{\sqrt{2^{n}}} (\sum_{x = 0, x \neq ω}^{2^{n} - 1} \frac{2^{n} - 2}{2^{n - 1}} - 1 | x ⟩ + \frac{2^{n} - 2 + 2^{n - 1}}{2^{n - 1}} | ω ⟩) \\ = \frac{1}{\sqrt{2^{n}}} (\sum_{x = 0, x \neq ω}^{2^{n} - 1} \frac{2^{n} - 2 - 2^{n - 1}}{2^{n - 1}} | x ⟩ + \frac{2^{n} - 2 + 2^{n - 1}}{2^{n - 1}} | ω ⟩) \\ = \frac{1}{\sqrt{2^{n}}} (\sum_{x = 0, x \neq ω}^{2^{n} - 1} \frac{2^{n - 1} - 2}{2^{n - 1}} | x ⟩ + \frac{3 \cdot 2^{n - 1} - 2}{2^{n - 1}} | ω ⟩) \end{aligned}

Kasirajan here is actually considering some large quantity for $n \to \infty$ . In this case the $- 2$ parts of the fraction get ignored:

| ψ_{3} ⟩ \approx \frac{1}{\sqrt{2^{n}}} (\sum_{x = 0, x \neq ω}^{2^{n} - 1} | x ⟩ + 3 | ω ⟩)

BIG NOTE

This is an approximation, so it's not exactly what we are expecting. But the approximation gives the general gist of what's going on here.

So for instance in the $n = 3$ case that we are considering:

| ψ_{3} ⟩ = \frac{1}{\sqrt{8}} (\underset{\neq | ω ⟩}{\underset{⏟}{| 000 ⟩ + \dots + | 111 ⟩}} + 3 | ω ⟩) \otimes | 1 ⟩

Which is equation 7.137. But we can repeat this process, just considering the constant of 3 in front of $| ω ⟩$ . To speed up the process, let's rederive the $2 | s ⟩ ⟨ s | - I$ operator when given any $k$ in front of $| ω ⟩$ :

\begin{aligned} ⟨ s | ψ ⟩ & = \sum_{i = 1}^{2^{n} - 1} \underset{= χ (s_{i} = ψ)}{\underset{⏟}{⟨ s_{i} | ψ ⟩}} \\ = \underset{from s with ψ \neq ω}{\underset{⏟}{\sum_{x = 0, x \neq ω}^{2^{n} - 1} \frac{1}{\sqrt{2^{n}}} \cdot \frac{1}{\sqrt{2^{n}}}}} - k \underset{from ω}{\underset{⏟}{\frac{1}{\sqrt{2^{n}}} \cdot \frac{1}{\sqrt{2^{n}}}}} \\ = \frac{1}{2^{n}} (2^{n} - 1 - k) \\ = \frac{2^{n} - 2 - k}{2^{n}} \end{aligned}

\begin{aligned} | ψ_{3} ⟩ & = 2 | s ⟩ \frac{2^{n} - 2 - k}{2^{n}} - | ψ_{3} ⟩ \\ = \frac{2^{n} - 2 - k}{2^{n - 1}} \frac{1}{\sqrt{2^{n}}} (| 000. . . ⟩ + \dots + | 111. . . ⟩) - \frac{1}{\sqrt{2^{n}}} (| 00. . . ⟩ + \dots - k | ω ⟩ + . . . + | 111. . . . ⟩) \\ = \frac{1}{\sqrt{2^{n}}} (\sum_{x = 0, x \neq ω}^{2^{n} - 1} \frac{2^{n} - 2 - k}{2^{n - 1}} - 1 | x ⟩ + \frac{2^{n} - 2 + k 2^{n - 1}}{2^{n - 1}} | ω ⟩) \\ = \frac{1}{\sqrt{2^{n}}} (\sum_{x = 0, x \neq ω}^{2^{n} - 1} \frac{2^{n} - 2 - k - 2^{n - 1}}{2^{n - 1}} | x ⟩ + \frac{2^{n} - 2 + k 2^{n - 1}}{2^{n - 1}} | ω ⟩) \\ = \frac{1}{\sqrt{2^{n}}} (\sum_{x = 0, x \neq ω}^{2^{n} - 1} \frac{2^{n - 1} - 2 - k}{2^{n - 1}} | x ⟩ + \frac{(2 + k) \cdot 2^{n - 1} - 2}{2^{n - 1}} | ω ⟩) \end{aligned}

As $n \to \infty$ then we ignore the $- 2$ 's in the fraction, giving for the $n = 3$ case and using our first pass $k = 3$ value:

| ψ_{3} ⟩ \approx \frac{1}{\sqrt{8}} (\underset{\neq | ω ⟩}{\underset{⏟}{(| 000 ⟩ + \dots + | 111 ⟩)}} + 5 | ω ⟩) \otimes | 1 ⟩

Which is exactly equation 7.138. Notice that essentially, every time because of the $2 + k$ factor we go up by the previous amount plus 2 for the $| ω ⟩$ factor, implying that the approximation breaks once we get past $\frac{N}{2}$ iterations. As such, it's best to just do three iterations in this case since if we go past that then we are in undefined territory.

4: Grover's Algorithm in General

Question

Grover's algorithm. Kasirajan provides sample code for Grover's algorithm with 3 qubits.
a. Write a code that works for 4 qubits. Attach it to your HW.
b. Write a code that works for $n$ qubits. Attach it to your HW.
c. Pick a number of qubits > 4 and an entry (binary number string) you would like to find in the database. Note that the entry you are looking for is encoded into the grover_oracle function: Apply X-gates to any qubit you want to be 0, and do nothing to any qubit you want to be 1. Then apply the controlsX gate, and then repeat the same X gates to the same qubits again. Run your algorithm and include the histogram here. Did your algorithm find your entry? How many Grover iterations were optimal?

For the purposes of this assignment, I actually just did the $n$ qubit case, as doing the 4 qubit case is as simple as calling:

from algorithms.groverSearch import groversAlgorithm
from qiskit import QuantumCircuit

num_qubits = 4
data = 1 # Data string you want to search for
qc = QuantumCircuit(num_qubits, num_qubits)

groversAlgorithm(qc, data)

# ... do other stuff

But now we can for the $n$ case consider when num_qubits is some arbitrary number. What follows is the code to accomplish this:

algorithms/groverSearch.py

from algorithms.utilities import *
from typing import Callable

def generic_single_transform(qc : QuantumCircuit, method : Callable[[QuantumCircuit, QubitSpecifier], InstructionSet], func : Callable[[int], bool] = lambda x : True) -> None:
    """Apply a arbitrary gate to all qubits of the QC, given some filtering function `func` that applies it to only specific qubits

    Args:
        qc (QuantumCircuit): QC to apply the series of gates to.
        func (Callable[[int], bool]): Function to test whether an index gets the transformation applied to itself. The default is to apply it to all qubits of `qc`.
        method (Callable[[QuantumCircuit, QubitSpecifier], InstructionSet]): the method from `qc` that is the gate you want to apply.
    """
    for i in range(0, qc.num_qubits):
        if (func(i)):
            method(qc, i)

def oracle(qc : QuantumCircuit, data : int) -> None:
    """Encodes a value to be searched within grover's algorithm.
    
    Args:
        qc (QuantumCircuit): QC to apply the encoding to.
        data (int): The data to be encoded. Only the lowest `qc.num_qubits` bits are considered in `data`.
    """

    # Do first pass of X gates
    i = 1
    pos = 0
    xed_qubits = []
    while i < 2**(qc.num_qubits):
        if not i & data:
            qc.x(pos)
            xed_qubits.append(pos)
        i = i << 1
        pos += 1

    # Essentially a CCC...CCCX gate for however many qubits we have.
    qc.mcp(pi, [x for x in range(0, qc.num_qubits - 1)], qc.num_qubits - 1)

    # Repeat the same pass.
    for i in xed_qubits:
        qc.x(i)

def diffusion(qc : QuantumCircuit) -> None:
    """Apply diffusion step to QC.
    Args:
        qc (QuantumCircuit): The QC to do the diffusion on.
    """
    generic_single_transform(qc, QuantumCircuit.h)
    generic_single_transform(qc, QuantumCircuit.x)
    qc.mcp(pi, [x for x in range(0, qc.num_qubits - 1)], qc.num_qubits - 1)
    generic_single_transform(qc, QuantumCircuit.x)
    generic_single_transform(qc, QuantumCircuit.h)

def groversAlgorithm(qc : QuantumCircuit, data : int, iter : int = None) -> None:
    """Apply grover's algorithm to the current state of the passed QuantumCircuit.
    Args:
        qc (QuantumCircuit): The QuantumCircuit to apply the algorithm to.
        data (int): The data to try to search for in the database.
        iter (int): Number of iterations to do. By default the optimum is to do
    """

    generic_single_transform(qc, QuantumCircuit.h)
    qc.barrier()
    if iter is None:
        iter = 2**(qc.num_qubits-1) - 1
    for i in range(0, iter):
        oracle(qc, data)
        qc.barrier()
        diffusion(qc)
        qc.barrier()

def main(num_qubits : int):
    # Add 1 qubit for the ancilla
    qc = QuantumCircuit(num_qubits)
    groversAlgorithm(qc, 2)
    print(qc)
    
if __name__ == "__main__":
    main(4)

On algorithms/groverSearch.py

There are some things required for running this code:

Make sure you keep all files in the algorithms folder and run from the parent folder of algorithms
If you run the file directly, you actually get the num_qubits = 4 version, where data = 2 in that case, just like Kasirajan's version of the code.
Notice groversAlgorithm uses the default iter value as $\frac{N}{2} - 1$ where $N = 2^{n}$ where $n$ is the number of qubits. This was the optimal value to use because the largest amplitude for $| ω ⟩$ increased by $2 k + 1$ for integers $k$ where $k$ was the iteration number. If it ever got above $\frac{1}{\sqrt{N}}$ then there are problems including the amplitudes of the other

Make sure to include the utilities file that has all the needed imports:

algorithms/utilities.py

from qiskit import *
import qiskit.quantum_info as qi
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit import InstructionSet
from qiskit.circuit.quantumcircuit import QubitSpecifier
from math import pi

def printCircuit(qc : QuantumCircuit, is_cmdline : bool = False):
    print(qc)
    qc_transpiled = transpile(qc)
    stv = qi.Statevector.from_instruction(qc_transpiled)
    if is_cmdline:
        print(stv.draw('text'))
    else:
        return stv.draw('latex')

Running the following jupyter notebook:

groverSearch.ipynb

from algorithms.groverSearch import *
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram

# Change these...
num_qubits = 7
data = 1

qc = QuantumCircuit(num_qubits, num_qubits)
groversAlgorithm(qc, data)

# Print info about the algorithm and statevector
print(qc)
qc_transpiled = transpile(qc)

# Measure data
for i in range(0, num_qubits):
    qc.measure(i, i)
    
# Histogram data getting from measurement
backend = AerSimulator()
job = backend.run(qc.copy(), shots=1024)
result = job.result()
counts = result.get_counts()

stv = qi.Statevector.from_instruction(qc_transpiled)
stv.draw('latex')

plot_histogram(counts)

This will allow you to plot the circuit on the command-line as well as see the statevector at the end, and a histogram of all measurements from a 1024 shot run of measurements.

Let's have fun with this. For example, running the default code where num_qubits = 7 and the data we search for is data = 1 gives:

- 0.0214729255 | 0000000 ⟩ + 0.9702793468 | 0000001 ⟩ - 0.0214729255 | 0000010 ⟩ - 0.0214729255 | 0000011 ⟩ - 0.0214729255 | 0000100 ⟩ - 0.0214729255 | 0000101 ⟩ + \dots - 0.0214729255 | 1111011 ⟩ - 0.0214729255 | 1111100 ⟩ - 0.0214729255 | 1111101 ⟩ - 0.0214729255 | 1111110 ⟩ - 0.0214729255 | 1111111 ⟩

See the 97% measurement on our searched term. The histogram turned out to measure:

Pasted image 20240602234234.png

We can try some other measurements for the (c) part of the question. Let's do num_qubits = 9 and data = 420

Pasted image 20240602234447.png

You can guess what the spike of 330 measurements is measuring right?