Hamming with prefix oracle

Question

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

Answer 1

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.