Ex: Can you prepare $\ket{\omega}?$

Editorial

Solution (1): Combining Grover's Algorithm with the Phase Shift Method

Just like in the QPC001 - Problem C2, we can use a quantum algorithm known as fixed-point probability amplitude amplification to prepare arbitrary quantum states

One variant of fixed-point probability amplitude amplification is Grover's $\pi/3$ phase shift method, which has the desirable property of "monotonically increasing" the probability amplitude of the desired computational basis state as the number of iterations increases. However, compared to Grover's algorithm, which also amplifies complex amplitudes, the $\pi/3$ phase shift method is known to be inefficient in terms of query complexity¹ (comparable to classical computation). For more details on the $\pi/3$ phase shift method, refer to the editorial of QPC001 C2.

In this problem, we can efficiently prepare the state $\ket{\omega}$ by skillfully combining Grover's algorithm with the $\pi/3$ phase shift method.

Let's consider different cases based on the value of the real number $P$.

Case where $P > 0.06$ (Using Only the $\pi/3$ Phase Shift Method)

Consider recursively applying the $\pi/3$ phase shift method $m$ times.

In this case, the maximum error probability ($(1 - 0.06)^{3^m}$) and the required number of $R(\cdot)$ gates can be summarized as follows:

Therefore, by applying the method $4$ times, we can sufficiently reduce the error.

If $P \leq 0.06$, the required number of $R(\cdot)$ gates would be $121$, which violates the constraints.

Case where $0.02 \leq P \leq 0.06$ (Combining Grover's Algorithm with the $\pi/3$ Phase Shift Method)

Consider the use of Grover's algorithm. We define $\ket{S}$, $R_S(\theta)$ and $R_\omega(\theta)$ by

By defining $\left|\braket{\omega \mid S}\right|^2 = \sin^2(\theta/2)$ and $\ket{S'} = (\ket{S} - \sin^2(\theta/2)\ket{\omega})/\cos(\theta/2)$, we have

Now, by denoting the vector after applying Grover's probability amplitude amplification $m$ times as $\ket{S_m}$, we have

Solving this, $\ket{S_m}$ can be expressed as

Thus, we can find $\left|\braket{\omega \mid S_m}\right|^2 = \sin^2((m + 1/2)\theta) \fallingdotseq \sin^2(m\theta)$.

Since $P$ is small enough, the inequality $P \leq \sin^2(\theta/2) \leq 4P$ leads to the following approximate inequality:

Based on these results, we apply Grover's algorithm by setting $m = \pi/(4\sqrt{4P})$.

Moreover, since $\pi/(4\sqrt{4P}) \leq 9$, you can reduce the error probability to $0.5$ or less by performing probability amplitude amplification no more than $9$ times.

Finally, by recursively applying the $\pi/3$ phase shift method with $\ket{S_m} = G\ket{0}$ and $U_0 = G$, the maximum error probability ($(1 - 0.5)^{3^m}$) and the required number of $R(\cdot)$ gates can be summarized as follows:

Therefore, you can achieve the correct answer with no more than $85$ applications of the $R(\cdot)$ gates.

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit
 
MAX_R_COUNT = 100
 
 
def R_0(n: int, theta: float) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
 
    if n == 1:
        qc.p(theta, 0)
    else:
        qc.mcp(theta, list(range(n - 1)), n - 1)
 
    qc.x(range(n))
 
    return qc
 
 
def Grover(n: int, P: float, U, R) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    cnt = int(math.pi / (4 * (4 * P) ** 0.5))
 
    qc.compose(U(), inplace=True)
 
    for _ in range(cnt):
        qc.compose(R(math.pi), inplace=True)
        qc.compose(U().inverse(), inplace=True)
        qc.compose(R_0(n, math.pi), inplace=True)
        qc.compose(U(), inplace=True)
 
    return qc, cnt
 
 
def PhaseShift(n: int, U_s, R) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.compose(U_s, inplace=True)
    qc.compose(R(math.pi / 3), inplace=True)
    qc.compose(U_s.inverse(), inplace=True)
    qc.compose(R_0(n, math.pi / 3), inplace=True)
    qc.compose(U_s, inplace=True)
 
    return qc
 
 
def solve(n: int, P: float, U, R) -> QuantumCircuit:
    U_s, cnt_R = Grover(n, P, U, R)
    while 3 * cnt_R + 1 <= MAX_R_COUNT:
        U_s = PhaseShift(n, U_s, R)
        cnt_R = 3 * cnt_R + 1
 
    return U_s

Solution (2): Fixed-point Quantum Search with an Optimal Number of Queries [1]

As mentioned in Solution (1), Grover's $\pi/3$ phase shift method is inefficient in terms of query complexity compared to Grover's algorithm. Therefore, simply applying the $\pi/3$ phase shift method alone cannot solve this problem.

However, in 2014, an algorithm was proposed that achieves fixed-point probability amplitude amplification while maintaining the almost same efficiency as Grover's algorithm [1].

Thus, by applying this algorithm, you can solve the problem effectively.

The required number of applications of the $R(\cdot)$ gate can be reduced to $11$ or fewer. This is the square root of what $\pi/3$ phase shift method requires, which is $121$.

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit
from scipy.special import eval_chebyt
 
 
def R_0(n: int, theta: float) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
 
    if n == 1:
        qc.p(theta, 0)
    else:
        qc.mcp(theta, list(range(n - 1)), n - 1)
 
    qc.x(range(n))
 
    return qc
 
 
# Calculate the minimum number of query L
def calculate_L(delta: float, lambda_: float) -> int:
    L = int(math.ceil(math.log(2 / delta) / math.sqrt(lambda_)))
 
    # Check if L is odd
    if L % 2 == 0:
        L += 1
 
    return L
 
 
def calculate_gamma(L: int, delta: float) -> float:
    # Calculate the Chebyshev polynomial T_{1/L}(1/δ)
    chebyshev_value = eval_chebyt(1 / L, 1 / delta)
 
    # γ is the inverse of the Chebyshev value
    return 1 / chebyshev_value
 
 
# Define the fixed-point Grover's algorithm
def fixed_point_grover(n: int, delta: float, lambda_: float, U, R) -> QuantumCircuit:
    L = calculate_L(delta, lambda_)
 
    # Calculate the angles for Grover's iteration
    gamma = calculate_gamma(L, delta)
    angles = [
        -2 * math.atan(1 / (math.tan(2 * math.pi * j / L) * math.sqrt(1 - gamma**2)))
        for j in range(1, L // 2 + 1)
    ]
 
    qc = QuantumCircuit(n)
    qc.compose(U(), inplace=True)
    for alpha, beta in zip(angles, reversed(angles)):
        qc.compose(R(beta), inplace=True)
        qc.compose(U().inverse(), inplace=True)
        qc.compose(R_0(n, alpha), inplace=True)
        qc.compose(U(), inplace=True)
 
    return qc
 
 
def solve(n: int, P: float, U, R) -> QuantumCircuit:
    delta = 0.01
    lambda_ = P
    return fixed_point_grover(n, delta, lambda_, U, R)

References

• [1] T. J. Yoder, G. H. Low, and I. L. Chuang, “Fixed-point quantum search with an optimal number of queries,” Physical Review Letters, vol. 113, no. 21, p. 210501, 2014.