Quantum-Computation-course-Basel/archives/practice/PracticeExercise2-solutions.ipynb

Fun with Oracles: The Bernstein-Vazirani Algorithm

In [1]:

from qiskit import *
%matplotlib inline
from qiskit.visualization import plot_histogram
from qiskit_aer import AerSimulator

# import image module
from IPython.display import Image

In this exercise, we will construct an oracle that lets us guess a secret number (the bitstring a) in a single query to a quantum computer. We begin by posing the problem classically. Suppose we have access to a function f_a(x) that takes a bitstring a as input and returns a\cdot x, modulo 2:

f_a(x)=a\cdot x\quad (\mathrm{mod}\; 2).

As an example, if a=001 and x=101, then f_a(x)=0\times 1 + 0\times 0 + 1\times 1=1. As a classical circuit, we can represent the Bernstein-Vazirani oracle like this (image stolen from Pennylane):

In [2]:

Image(url="classical.png", width=400, height=400)

Out [2]:

More generally, we can write the action of this oracle as

\begin{equation}
U_f\vert x\rangle\vert s\rangle=\vert x\rangle \vert s\oplus f_a(x)\rangle,\quad s=0,1,
\end{equation}

where \oplus denotes addition modulo 2.

To find a classically, we would have to query this oracle N=\mathrm{len}(a) times with inputs x_0=0\dots 01, x_1=0\dots 10,..., x_{N-1}=10\dots0. (Each query allows us to determine one bit of a.) Given the oracle U_f, the Bernstein-Vazirani algorithm allows us to find a in a single shot using the following circuit:

In [ ]:

Image(url="quantum.png", width=400, height=400)

The steps of the algorithm are as follows:

1. Initialize the register qubits to the |0\rangle^{\otimes n} state, and the ancilla qubit to |{-}\rangle
2. Apply Hadamard gates to the input register
3. Query the oracle
4. Apply Hadamard gates to the input register
5. Measure

Let's walk through the steps one-by-one. If we start with all register qubits initialized in \vert a\rangle and apply a Hadamard to each one, then we have prepared the state

\vert a \rangle\stackrel{H^{\otimes N}}{\longrightarrow} \frac{1}{\sqrt{2^N}}\sum_{x=0}^{2^N-1}(-1)^{a\cdot x}\vert x\rangle.

Since the register qubits are all initialized in \vert 0\rangle, the input state on which the oracle acts is therefore given by

\vert \psi_0\rangle =\frac{1}{\sqrt{2^{N+1}}}\sum_{x=0}^{2^N-1}\vert x\rangle(\vert 0\rangle-\vert 1\rangle).

Let's start by preparing this state. First, we choose a secret number:

In [16]:

secretnumber = input('Enter a binary number:')
l = len(secretnumber)

Enter a binary number: 0101

The next code cell is for you to complete. It should realize Steps #1 and #2 in the list above:

In [17]:

qc = QuantumCircuit(l+1, l)

qc.h(range(l))
qc.x(l)
qc.h(l)

qc.barrier()
qc.draw()

Out [17]:

     ┌───┐      ░ 
q_0: ┤ H ├──────░─
     ├───┤      ░ 
q_1: ┤ H ├──────░─
     ├───┤      ░ 
q_2: ┤ H ├──────░─
     ├───┤      ░ 
q_3: ┤ H ├──────░─
     ├───┤┌───┐ ░ 
q_4: ┤ X ├┤ H ├─░─
     └───┘└───┘ ░ 
c: 4/═════════════
                  

Next, let's see what happens when we apply the oracle U_f to \vert \psi_0\rangle. Using the equation given above, we have

   \begin{aligned}
   U_f\lvert \psi_0 \rangle  
   & = \frac{1}{\sqrt{2^{N+1}}}\sum_{x=0}^{2^N-1} \vert x\rangle (\vert f_a(x)\rangle - \vert 1 \oplus f_a(x)\rangle)  \\&= \frac{1}{\sqrt{2^{N+1}}}\sum_{x=0}^{2^N-1}(-1)^{f_a(x)}|x\rangle ( |0\rangle - |1\rangle ) .
   \end{aligned}

Neglecting the ancilla qubit, the action of Steps #1-3 above can therefore be summarized as

|00\dots 0\rangle \xrightarrow{H^{\otimes N}} \frac{1}{\sqrt{2^N}} \sum_{x} |x\rangle \xrightarrow{U_f} \frac{1}{\sqrt{2^N}} \sum_{x} (-1)^{a\cdot x}|x\rangle.

Since the Hadamard is its own inverse, the secret number a can be recovered by once again applying Hadamards to all register qubits:

\frac{1}{\sqrt{2^N}}\sum_{x=0}^{2^N-1}(-1)^{a\cdot x}\vert x\rangle\stackrel{H^{\otimes N}}{\longrightarrow}\vert a \rangle.

We will now construct the oracle by applying CNOTs between the ancilla (in position l) and every bit of the secret number equal to 1. (The target qubit should be l.)

In [18]:

#Building the oracle
for i, digit in enumerate(reversed(secretnumber)):
    if digit == '1':
        qc.cx(i,l)
        
qc.draw()

Out [18]:

     ┌───┐      ░           
q_0: ┤ H ├──────░───■───────
     ├───┤      ░   │       
q_1: ┤ H ├──────░───┼───────
     ├───┤      ░   │       
q_2: ┤ H ├──────░───┼────■──
     ├───┤      ░   │    │  
q_3: ┤ H ├──────░───┼────┼──
     ├───┤┌───┐ ░ ┌─┴─┐┌─┴─┐
q_4: ┤ X ├┤ H ├─░─┤ X ├┤ X ├
     └───┘└───┘ ░ └───┘└───┘
c: 4/═══════════════════════
                            

Finally, we apply Hadamards and measure all register qubits in the Z basis. You can visualized your circuit using qc.draw().

In [19]:

qc.h(range(l))
qc.measure(range(l), range(l))

qc.draw()

Out [19]:

     ┌───┐      ░      ┌───┐             ┌─┐   
q_0: ┤ H ├──────░───■──┤ H ├─────────────┤M├───
     ├───┤      ░   │  ├───┤     ┌─┐     └╥┘   
q_1: ┤ H ├──────░───┼──┤ H ├─────┤M├──────╫────
     ├───┤      ░   │  └───┘     └╥┘┌───┐ ║ ┌─┐
q_2: ┤ H ├──────░───┼─────────■───╫─┤ H ├─╫─┤M├
     ├───┤      ░   │  ┌───┐  │   ║ └┬─┬┘ ║ └╥┘
q_3: ┤ H ├──────░───┼──┤ H ├──┼───╫──┤M├──╫──╫─
     ├───┤┌───┐ ░ ┌─┴─┐└───┘┌─┴─┐ ║  └╥┘  ║  ║ 
q_4: ┤ X ├┤ H ├─░─┤ X ├─────┤ X ├─╫───╫───╫──╫─
     └───┘└───┘ ░ └───┘     └───┘ ║   ║   ║  ║ 
c: 4/═════════════════════════════╩═══╩═══╩══╩═
                                  1   3   0  2 

We can finally run our circuit. Only a single shot is required since the outcome is deterministic in the absence of other errors. If you've done everything correctly, the following code block should return the secret number you specified at the beginning of this notebook.

In [20]:

backend = AerSimulator()
result = backend.run(qc, shots=1).result()
counts = result.get_counts()
print(counts)

{'0101': 1}

In [ ]: