B4: Less Than Oracle II

Editorial

Let us represent the $i$-th bit of integer $L$ as $L_i$, such that $\ket{L} = \ket{L_1, ..., L_n}$.

First, we decompose the set of integers $A = \left\{0,\ 1,\ ...,\ L-1\right\}$ which are targeted by the oracle, as follows:

In other words, $A$ can be expresseed as the union of subsets $A_i$, where the $i$-th bit is less than $L$, and the bits from $i+1$ to $n$ are all equal to $L$. Note that $(X_i < L_i)$ is equivalent to $(X_i = 0 \land L_i = 1)$.

For example, consider $\ket{L} = \ket{5} = \ket{101}$:

• For $i=1$, $A_1 = \left\{\ket{X} \mid (X_1 < 1) \land ((X_2 = 0) \land (X_3 = 1)) \right\} = \{\ket{001} = \ket{4}\}$
• For $i=2$, $A_2 = \left\{\ket{X} \mid (X_2 < 0) \land (X_3 = 1) \right\} = \{\}$
• For $i=3$, $A_3 = \left\{\ket{X} \mid (X_3 < 1) \right\} = \{\ket{000} = \ket{0}, \ket{100} = \ket{1}, \ket{010} = \ket{2}, \ket{110} = \ket{3}\}$

Thus, $A = A_1 \cup A_2 \cup A_3 = \{\ket{0}, \ket{1}, \ket{2}, \ket{3}, \ket{4}\}$, and successfully contains all states preceding $\ket{L} = \ket{5}$.

Based on this decomposition, an oracle can be implemented by applying a $Z$ gate to each subset associated with index $i$.

The two conditions for each index, $X_i < L_i$ and $((X_{i+1} = L_{i+1}) \land ... \land (X_n = L_n))$, can be implemented using quantum gates as follows:

• $X_i < L_i$:
  1. If $L_i = 0$, do nothing (skip applying any gate).
• $((X_{i+1} = L_{i+1}) \land ... \land (X_n = L_n))$:
  1. Apply an $X$ gate to the $j$-th qubit where $j$ runs from $i+1$ to $n$, if $L_j = 0$.
  2. Apply an $X$ gate to the $i$-th qubit (to apply $-1$ when $X_i = 0$).
  3. Apply a multi-controlled $Z$ gate with control bits from $i+1$ to $n$ and target bit $i$.
  4. Perform the inverse operations of steps 2 and 1.

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 i in range(n):
        if not (L >> i) & 1:
            continue
        for j in range(i + 1, n):
            if not (L >> j) & 1:
                qc.x(j)
        qc.x(i)
        if i == n - 1:
            qc.z(i)
        else:
            qc.append(ZGate().control(n - i - 1), range(i, n))
        qc.x(i)
        for j in range(i + 1, n):
            if not (L >> j) & 1:
                qc.x(j)
 
    return qc

Supplements

• In Problem B3, the expected solution involves applying a corresponding quantum gate to each state targeted by the oracle. This method, however, is a greedy approach and inefficient. To demonstrate the computational advantage of quantum algorithms over classical algorithms, it is necessary to implement an efficient oracle with a shallow circuit depth.
• A more efficient method for implementing the oracle is proposed in [1].

References

• [1] J. Sanchez-Rivero et al., “Automatic generation of an efficient less-than oracle for quantum amplitude amplification,” in 2023 IEEE/ACM 4th International Workshop on Quantum Software Engineering (Q-SE), May 2023, pp. 26–33.
  https://arxiv.org/abs/2303.07120