Ex2: Find Hidden Number

Editorial

This problem, as in B6 and B8, involves amplifying the probability amplitude of a particular computational basis state. However, using the standard Grover's algorithm directly does not allow the circuit depth to be less than 75.

Thus, consider the condition given in this problem: "$L$ is one of the powers of 2."

This can be rephrased as "$\ket{L}$ is one of the $n$ types of computational basis states $\ket{100...0}_n, \ket{010...0}_n, ..., \ket{000...1}_n$".

Therefore, using a uniform superposition state via the $H$ gates as the initial state for Grover's algorithm is inefficient because it includes states that are clearly not targeted for amplification. Instead, by using the quantum state $\ket{\psi}$ from problem A6 as the initial state, the number of iterations can be reduced.

To invert the sign of the computational basis state we want to amplify in this problem, we can use the oracle $O$ itself.

The operation represented by the operator $2\ket{\psi}\bra{\psi}-I$ can be implemented using the circuit from A6 in the same way as B7.

When considering the optimal number of iterations, as discussed in B8, it is known to be the non-negative integer closest to the following real number $r$.

For $3\leq n\leq 6$, a single iteration satisfies $|a_L|^2\geq 0.9$, and for $8\leq n\leq 15$, two iterations suffice. Furthermore, you can ensure the circuit depth doesn't exceed the constraint.

For $n=2$ and $n=7$, the method above does not result in an integer satisfying $|a_L|^2\geq 0.9$. To address this problem, one way could be to apply the $H$ gate to only one qubit while preparing $\ket{\psi}$, reducing it to a case of $2n$. Alternatively, using one ancillary qubit or executing the conventional Grover's algorithm for $n=2$ could be considered.

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit
from qiskit.circuit.library import ZGate
 
 
def w(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    qc.x(0)
 
    count = 1
 
    # queue = [(a, b, control bit of CRy), ...]
    queue = [(n // 2, n, 0)]
 
    # breadth first search
    while len(queue):
        a, b, control = queue.pop(0)
 
        if a == 0:
            continue
 
        theta = 2 * math.atan(math.sqrt((b - a) / a))
 
        qc.cry(theta, control, count)
        qc.cx(count, control)
 
        queue.append(((b // 2) // 2, b // 2, control))
        queue.append((math.ceil(b / 2) // 2, math.ceil(b / 2), count))
 
        count += 1
 
    return qc
 
 
def initialize(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    if n == 2:
        qc.h(range(n))
    else:
        qc.compose(w(n), inplace=True)
        if n == 7:
            qc.h(0)
 
    return qc
 
 
def reflect(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
    qc.append(ZGate().control(n - 1), range(n))
    qc.x(range(n))
 
    return qc
 
 
def solve(n: int, o: QuantumCircuit) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    u_i = initialize(n)
    u_i_inv = u_i.inverse()
 
    qc.compose(u_i, inplace=True)
 
    cnt = 1 if n < 7 else 2
 
    for _ in range(cnt):
        qc.compose(o, inplace=True)
        qc.compose(u_i_inv, inplace=True)
        qc.compose(reflect(n), inplace=True)
        qc.compose(u_i, inplace=True)
 
    return qc