2
$\begingroup$

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.