C2: Generate Uniform Amplitude Superposition State II

Editorial

Quantum algorithms such as Grover's algorithm and amplitude amplification work by amplifying the probability amplitudes of specific computational basis states. The probability of observing the desired computational basis state in these algorithms is expressed as a periodic function of the number of iterations. Although this probability can be amplified to values close to $1.0$, it typically cannot reach exactly $1.0$.

In contrast, an algorithm called fixed-point amplitude amplification can monotonically increase the probability amplitude of the desired computational basis state relative to the number of iterations. That is, the observation probability converges to $1.0$ with a sufficient number of iterations.

Therefore, this problem can be solved using fixed-point amplitude amplification.

Next, we describe an overview of fixed-point amplitude amplification. While various methods have been proposed, here we consider Grover's $\pi/3$ phase-shift method.

First, we define the pre-amplification initial state as $\ket{s}$ ¹ and the desired post-amplification state as $\ket{t}$. In the $\pi/3$ phase-shift method, amplitude amplification is performed by applying to the initial state $\ket{s}$ an operator $U_m$ recursively defined by the following equation, with respect to some unitary operation $U$ ².

where $(\cdot)^{\dagger}$ denotes the Hermitian transpose, and the selective phase shift operators $R_s$ and $R_t$ are defined by

Note that the oracle $R_t$ can use the implementation from problem B4 ³.

For details and background of the algorithm, please refer to the sample code and the literatures [1], [2], and [3].

Next, we perform an error analysis.

Define the initial error $\epsilon_0$ as the probability of observing any computational basis state other than those desired when measuring state $U\ket{s}$. That is, the probability of observing a desired state is $1 - \epsilon_0$. In this problem, if $U$ prescribed "apply the Hadamard gate to all qubits ($H^{\otimes n}$)" as seen in C1, applying $U_m$ to the first $\lceil\log_2(L)\rceil$-th qubits ensures $1 - \epsilon_0 > 0.5 \Rightarrow \epsilon_0 < 0.5$ ⁴.

Here, the error between $U_m\ket{s}$ and $\ket{t}$ is represented by $\epsilon_0^{3^m}$ ⁵.

Therefore, the recursive depth $m$ required to reduce the error to less than $5.0 \times 10^{-3}$ can be determined by solving the following equation:

The solution to Equation $(4)$ includes $m > 1.86$. Thus, setting $m = 2$ ensures the error is sufficiently reduced within the problem constraints.

Sample Code

Below is a sample program:

from qiskit import QuantumCircuit
from qiskit.circuit.library import PhaseGate
import math
 
 
def Rt(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.p(math.pi / 3, i)
        else:
            qc.append(PhaseGate(math.pi / 3).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
 
 
def Rs(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
 
    if n == 1:
        qc.p(math.pi / 3, 0)
    else:
        qc.append(PhaseGate(math.pi / 3).control(n - 1), range(n))
 
    qc.x(range(n))
 
    return qc
 
 
def U(m: int, n: int, L: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    if m == 0:
        qc.h(range(n))
        return qc
 
    u = U(m - 1, n, L)
 
    qc.compose(u, inplace=True)
    qc.compose(Rt(n, L), inplace=True)
    qc.compose(u.inverse(), inplace=True)
    qc.compose(Rs(n), inplace=True)
    qc.compose(u, inplace=True)
 
    return qc
 
 
def solve(n: int, L: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    k = math.ceil(math.log2(L))
    if k == 0:
        return qc
 
    m = 2
    qc.compose(U(m, k, L), inplace=True)
 
    return qc

References

• [1] L. K. Grover et al., “Quantum algorithms with fixed points: The case of database search,” arXiv:quant-ph/0603132, Mar. 2006.
• [2] G. Brassard et al., “Quantum amplitude amplification and estimation,” arXiv:quant-ph/0005055, vol. 305, pp. 53–74, 2002.
• [3] L. K. Grover, “Fixed-point quantum search,” Physical Review Letters, vol. 95, no. 15, p. 150501, Oct. 2005.