Quantum Katas - Tutorials - Oracles - Task 3.3 (OR oracle of all bits except for a single bit)

Question

Let $x$ be an arbitrary state composed of $N$ qubits and $k$ be an integer such that $0\leq k \leq N.$

The task is to ignore the $k$-th bit and to flip the sign of $x$ if any of the remaining bits are equal to 1. In other words, flipping the sign of $x$ is independent of the $k$-th bit, but it is dependent on the existence of 1's lurking in $x$.

The solution I came up with is the following, which, unfortunately, I cannot implement.

Regardless of what $x$ is we flip its sign. There are two cases we should correct for, namely, the binary representations of 0 and $2^k$. Could not we take care of these two scenarios by using the ControlledOnInt function by setting $\textit{numberstate}$ to 0 (first we have the $X$ gate act on $x[k]$, so that $Z$ flips $x$) and $2^k$, the $\textit{oracle}$ to $Z$, the $\textit{control register}$ to $[x]$ and the $\textit{target register}$ to $x[k]$? Also, why can't the control and target registers be the same?

How could we implement the above with an auxiliary qubit?

In the second case where $x$ is the binary representation of $2^k$, we could use the task 3.2 from the same tutorial (flips the sign of $x$ if the $k$-th qubit is 1), but I am also having trouble with that task. I have been able to implement the OR oracle (task 3.1 of the same tutorial), but it was done with a marking oracle, not a phase oracle.

Answer 1

There is a much simpler way to approach this task. It requires only two observations:

1. You can always convert a marking oracle to a phase oracle using the phase kickback trick (discussed earlier in the tutorial). Some tasks in this tutorial prohibit using extra qubits for this purpose to push you towards a solution that doesn't rely on that, but this task doesn't have this restrictions, so you can allocate that extra qubit, implement a marking oracle and use them to get your phase oracle.

2. If you need to perform some computation on the whole register except one qubit, why not just define a qubit array that holds the rest of the qubits and use that array as the input for the marking oracle? (This is more of a programming trick than a quantum computing one, but it's a useful one!)

With those two observations, the code is pretty straightforward:

use minus = Qubit();
within {
    X(minus);
    H(minus);
} apply {
    Or_Oracle(x[...k-1] + x[k+1...], minus);
}

x[...k-1] + x[k+1...] is a concatenation of two qubit arrays: all qubits before the $k$-th one and all qubits after the $k$-th one.

You can always check the file ReferenceImplementation.qs in the tutorial folder to see the author's solutions to the tasks.