Exercise Sheet 2

Instruction

We want to implement a gate $\mathbf{mod}[\mathbf{q}]$ taking input $s$ of width $n$ and whose action is defined as follows:

$$\mathbf{mod}[\mathbf{q}]=\{\begin{array}{ll}0& \text{if }\mathrm{hw}(w)\equiv 0\mathrm{mod}q\\ 1& \text{otherwise}\end{array}$$

The function $\mathrm{hw}(\cdot )$ is the Hamming weight and counts the number of $1$s in the input. Such a gate is helpful in an implementation of the recursive Fourier sampling problem (RFS), also called recursive Bernstein-Vazirani Problem.

We are given an operator $M_q$ on $k=\lceil {\log }_{2}q\rceil$ qubits which acts as follows:

$$M_q|x⟩=\{\begin{array}{ll}|x+1\mathrm{mod}q⟩& \text{if }x<q\\ |x⟩& \text{if }x\ge q\end{array}$$

We are interested in the case $q=3$. We claim that $M_3$ with its matrix given below can be used to implement $\mathbf{mod}[\mathbf{q}]$ for $q=3$.

$$\left(\begin{array}{cccc}0& 0& 1& 0\\ 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right)$$

This matrix looks quite similar to the matrix of the $\mathrm{SWAP}$ gate. Simply exchange $M_3$ row $0$ with row $1$ in order to obtain $\mathrm{SWAP}$.

Remark: The following matric is generated by Qiskit (with Qiskit’s bit order).

$$\left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\end{array}\right)$$

1. An important condition $M_q$ has to satisfy is $(M_q{)}^q=I$. Show that $(M_3{)}^3$ results in the identity.

2. Implement a gate $M_3$ using one ${\mathrm{CNOT}}^0$ gate and one $\mathrm{SWAP}$ gate. Recall that ${\mathrm{CNOT}}^0$ acts when the control qubit is in state $|0⟩.Employ[[Knowledge/Pauli-XQuantumGate|Pauli-Xgates]]and$\mathrm{CNOT}$tosimulate$\mathrm{CNOT}^0$.UseQiskitandemploytheunitarysimulatortoobtainthematrixformofyourimplementation.Isthismatrixequalto$M_{3}$ above?

3. Implement a single-controlled version $c{M}_3$ of gate $M_3$ in Qiskit using $\mathrm{CNOT}$, $\mathrm{CCNOT}$ and controlled $\mathrm{SWAP}$ gates. Test your implementation and document the test cases.

4. Implement the $\mathbf{mod}[\mathbf{q}]$ gate for $q=3$ and $n=4$ input qubits as a gate array in Qiskit.

   Start with $k=\lceil {\log }_{2}q\rceil$ ancillary qubits and apply four $c{M}_3$ gates each controlled by another single input qubit. The target qubits are the ancillary qubits. Apply an OR gate with target $r$ exploiting that $a\vee b$ is equivalent to $\neg (\neg a\wedge \neg b)$. Measure $r$ and compute.

   Test your implementation with all possible $16$ values for the input.