I'm doing the Q# quantum katas and I'm stuck on an oracle in the Deutsch-Jozsa algorithm katas.
Let $|x\rangle=|x_0x_1\dots x_{n-1}\rangle$ be a qubit array and $r$ be bit string of $k\leq n$. The $k$-prefix of a bit string $x$, $P_k(x)$, is the string obtained by cutting off everything except the first $k$ bits. An oracle for a function $f$ is a unitary operator that performs the following transformation
$$O_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle $$ where $\oplus$ represents sum modulo $2$ and $|y\rangle$ in this case is a single qubit.
The task is to write an oracle for the following function
$$f(x)=\left( \bigoplus_{i=0}^{n-1}x_i \right) \oplus g(x,r)$$
where $$ g(x,r)=\begin{cases} 1\quad \textrm{ if } P_k(x)=r\\ 0\quad \textrm{ otherwise } \end{cases}$$
The first term is easy to implement: just apply CNOT on $y$ with |$x_k\rangle$ as a control qubit for each $k$, this way $y$ is flipped as many times as there are $1$s in the string $x$, which is equivalent to flipping if the sum modulo $2$ is $1$.
The second term is giving me more trouble. I defined the qubit array $|r\rangle$ that contains the state equal to the bit string $r$ and another qubit array of the same length, $|z\rangle$ initially set to $|00\dots 0\rangle$ and I perform the following operation for every $j=0,\dots k-1$
$$\mathrm{CCNOT}|r_j\rangle|x_j\rangle|z_j\rangle $$ $$X\otimes X |r_j\rangle|x_j\rangle $$ $$\mathrm{CCNOT}|r_j\rangle|x_j\rangle|z_j\rangle $$ $$X\otimes X |r_j\rangle|x_j\rangle $$
this way the bit $|z_j\rangle$ is flipped if and only if the state of $|r_j\rangle|x_j\rangle $ is $|0\rangle|0\rangle$ or $|1\rangle|1\rangle$. After this I apply a multi controlled $X$ gate with control $|z\rangle$ and target $|y\rangle$, the idea being that if $|z\rangle$ contains only $1$ then $P_k(x)$ and $r$ are equal. The test fails, and I can't understand why. Could anybody help?
Here is my code:
for(k in 0..Length(x)-1) //first term
{
CNOT(x[k],y);
}
using(register = Qubit[Length(prefix)])
{
for(k in 0..Length(prefix)-1) //copy the bit string prefix in a qubit array
{ //01001... -> |01001..⟩
if(prefix[k]==1)
{
X(register[k]);
}
}
using(z = Qubit[Length(prefix)])
{
for(k in 0..Length(prefix)-1)
{
CCNOT(register[k],x[k],z[k]); //flips the state of the qubit z[k] if register[k] and x[k] are equal
X(register[k]); //000 -> 000 -> 110 -> 111 -> 001
X(x[k]); //010 -> 010 -> 100 -> 100 -> 010
CCNOT(register[k],x[k],z[k]); //100 -> 100 -> 010 -> 010 -> 100
X(x[k]); //110 -> 111 -> 001 -> 001 -> 111
X(register[k]);
}
Controlled X(z,y);
for(k in 0..Length(prefix)-1) //resets z
{
if(M(z[k])==One)
{
X(z[k]);
}
}
}
for(k in 0..Length(prefix)-1) //resets register
{
if(M(register[k])==One)
{
X(register[k]);
}
}
}