B3: Less Than Oracle I

Editorial

Consider multiplying each probability amplitude $a_i$ of the computational basis states $\ket{0},\ \ket{1},\ ...\ \ket{L-1}$ by $-1$.

The operation of multiplying by $-1$ can be achieved using the $Z$ gate, which leaves the computational basis state $\ket{0}$ unchanged, and transforms $\ket{1}$ into $-\ket{1}$.

So, how can you apply the $Z$ gate to only a specific computational basis state $\ket{l}$ within a superposition state?

This can be accomplished as follows:

1. For $\ket{l} = \ket{l_1 l_2 l_3 ... l_n}$, apply the $X$ gate at index $i$ where $l_i = 0$. This transforms $\ket{l}$ into $\ket{2^n - 1} = \ket{1...1}$.
2. Apply a multiple-control $Z$ gate¹, using $n - 1$ bits as control bits and the remaining $1$ bit as the target bit. In this case, the $Z$ gate acts only on the computational basis state $\ket{l}$ within the superposition.
3. Perform the inverse of step 1 to transform $\ket{2^n - 1}$ back to $\ket{l}$.

Therefore, by performing this operation for each computational basis state $\ket{0},\ \ket{1},\ ...\ \ket{L-1}$, you can solve this problem.

Sample Code

Below is a sample program:

from qiskit import QuantumCircuit
from qiskit.circuit.library import ZGate
 
 
def solve(n: int, L: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    for l in range(L):
        for i in range(n):
            # check if i-th bit of l is 0 or 1
            if not ((l >> i) & 1):
                qc.x(i)
        if n == 1:
            qc.z(0)
        else:
            # apply multiple controlled Z gate
            qc.append(ZGate().control(n - 1), range(n))
        for i in range(n):
            if not ((l >> i) & 1):
                qc.x(i)
    return qc