# Hamming with prefix oracle

I'm doing the Q# quantum katas and I'm stuck on an oracle in the Deutsch-Josza 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]);
}
}
}


One problem is that you are resetting the $$\left|z\right\rangle$$ register after applying the Controlled X(z, y) operation. Right before you reset, your $$\left|z\right\rangle$$ register is entangled with the other two registers, such that resetting in that way collapses any superposition on the $$\left|x\right\rangle \left|y\right\rangle$$ registers. While that's not a problem if you only ever provide as input qubits in a computational basis state, the Deutsch–Jozsa algorithm uses inputs in states such as $$\left|++\cdots+\right\rangle\left|-\right\rangle$$.

If you want to use this approach, you'll need to first uncompute the information stored in $$\left|z\right\rangle$$. Here, that means running the following loop over again after applying Controlled X(z, y):

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]);
}


Doing so will deterministically return $$\left|z\right\rangle$$ to the all-zeros state, without using measurement. This is very common in quantum programming, and is why the Q# standard libraries include operations like ApplyWithCA.