QCoder

Editorial

This problem involves amplifying the probability amplitudes of specific computational basis states, assuming the use of Grover's algorithm, as in Problem B6.

The probability $P(r)$ of observing the target computational basis state after performing Grover iterations $r$ times is expressed by

\begin{equation} P(r) = \sin^2\left(\left(r + \frac{1}{2}\right)\theta\right), \end{equation}

where $\theta = 2\arcsin(1/\sqrt{2^n})$ .

The positive minimum real number $r_{\mathrm{min}}$ that satisfies $P(r)=1$ can be given by

\begin{equation} r_{\mathrm{min}}=\frac{\pi}{2\theta}-\frac{1}{2}. \end{equation}

In practice, the number of iterations must be an integer, but within the constraints of this problem, it can be confirmed that rounding $r_{\mathrm{min}}$ to an integer satisfies $|a_L|^2\geq 0.9$ .

For $n=10$ , $r_{\mathrm{min}} \sim 25$ , and since the circuit for Grover iterations can be implemented with a depth of 8 or less, the total depth of the quantum circuit can be kept below 250.

Proof of Equation (1)

Let us define the quantum state $\ket{\psi'}$ by

\begin{equation} \ket{\psi'} = \frac{1}{\sqrt{2^n-1}} \left(\sum_{i=0}^{2^n-1}\ket{i} - \ket{L}\right). \end{equation}

The state $\ket{\psi}$ can be expressed using $\ket{L}$ and $\ket{\psi'}$ as follows:

\begin{equation} \ket{\psi} = \frac{1}{\sqrt{2^n}} \ket{L} + \frac{\sqrt{2^n-1}}{\sqrt{2^n}} \ket{\psi'} \end{equation}

Next, considering $\theta$ that satisfies

\begin{equation} \sin \frac{\theta}{2} = \frac{1}{\sqrt{2^n}}, \end{equation}

we can rewrite $\ket{\psi}$ as follows:

\begin{equation} \ket{\psi}=\sin\frac{\theta}{2}\ket{L}+\cos\frac{\theta}{2}\ket{\psi'} \end{equation}

Letting $r$ be a non-negative integer, we compute the quantum state after performing Grover iterations on the following state:

\begin{equation} \sin\left(\left(r+\frac{1}{2}\right)\theta\right)\ket{L}+\cos\left(\left(r+\frac{1}{2}\right)\theta\right)\ket{\psi'} \end{equation}

First, the inner products of $\ket{\psi}$ , $\ket{\psi'}$ , and $\ket{L}$ yield:

\braket{\psi|L}=\braket{L|\psi}=1/\sqrt{2^n},\ \braket{\psi'|\psi}=\braket{\psi|\psi'}=\sqrt{2^n-1}/\sqrt{2^n},\ \braket{\psi'|L}=\braket{L|\psi'}=0

Considering the oracle $O$ that flips the sign of the computational basis state $\ket{L}$ , it can be expressed as $O = I - 2\ket{L}\bra{L}$ . When we apply the oracle $O$ to the quantum state in equation (7), we obtain:

\begin{align} &O \left(\sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'}\right) \nonumber \\ &= (I - 2\ket{L}\bra{L}) \left(\sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'}\right) \\ &= \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} - 2\sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} \braket{L|L} - 2\cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} \braket{L|\psi'} \\ &= \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} - 2\sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} \\ &= - \sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos\left(r_{+ \frac{1}{2}} \theta\right)\ket{\psi'} \end{align}

where $r_{+ \frac{1}{2}}$ denotes $r + 1 / 2$ .

Next, applying the operation represented by the operator $2\ket{\psi}\bra{\psi} - I$ gives us:

\begin{align} & (2 \ket{\psi}\bra{\psi} - I) \left(- \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} \right) \nonumber \\ &= -2 \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} \braket{\psi|L} + 2\cos \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} \braket{\psi|\psi'} + \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} - \cos (r_{+ \frac{1}{2}} \theta )\ket{\psi'} \\ &= - \frac{2}{\sqrt{2^n}} \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} + \frac{2\sqrt{2^n-1}} {\sqrt{2^n}} \cos \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} + \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} - \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} \\ &= - 2 \sin \frac{\theta}{2} \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} + 2 \cos\frac{\theta}{2} \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} + \sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} - \cos\left(r_{+ \frac{1}{2}} \theta\right)\ket{\psi'} \\ &= - 2 \sin^2 \frac{\theta}{2} \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} - 2\sin \frac{\theta}{2} \cos \frac{\theta}{2} \sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} \\ & \qquad \qquad + 2\sin\frac{\theta}{2} \cos \frac{\theta}{2} \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + 2\cos^2 \frac{\theta}{2} \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} + \sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} - \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} \nonumber \\ &= \left(\left(1 - 2 \sin^2 \frac{\theta}{2}\right) \sin\left(r_{+ \frac{1}{2}} \theta\right) + 2 \sin \frac{\theta}{2} \cos \frac{\theta}{2} \cos\left(r_{+ \frac{1}{2}} \theta\right)\right) \ket{L} \\ & \qquad \qquad + \left(\left(2 \cos^2\ \frac{\theta}{2} - 1\right) \cos\left(r_{+ \frac{1}{2}} \theta\right) - 2 \sin \frac{\theta}{2} \cos \frac{\theta}{2} \sin\left(r_{+ \frac{1}{2}} \theta\right)\right) \ket{\psi'} \nonumber \\ &= \left(\sin\left(r_{+ \frac{1}{2}} \theta\right) \cos \theta + \cos\left(r_{+ \frac{1}{2}} \theta\right) \sin \theta\right) \ket{L} + \left(\cos\left(r_{+ \frac{1}{2}} \theta\right) \cos \theta - \sin\left(r_{+ \frac{1}{2}} \theta\right) \sin \theta\right) \ket{\psi'} \\ &= \sin\left(\left(r_{+ \frac{1}{2}} + 1\right) \theta\right) \ket{L} + \cos \left(\left(r_{+ \frac{1}{2}} + 1\right) \theta\right) \ket{\psi'} \end{align}

Therefore, the quantum state after performing the Grover iteration $r$ times on $\ket{\psi}$ from equation $(6)$ can be represented by

\begin{equation} \ket{\psi} = \sin\left(\left(r + \frac{1}{2}\right) \theta\right) \ket{L} + \cos \left(\left(r + \frac{1}{2}\right) \theta\right) \ket{\psi'}. \end{equation}

For the case where $n = 2$ , the circuit diagram is shown below. The Reflect_B4 in the circuit diagram indicates the circuit of problem B4.

The above considerations can be interpreted geometrically as follows. In the diagram, $U_{\psi} = 2 \ket{\psi}\bra{\psi} - I$ . In the 2-dimensional space spanned by $\ket{\psi'}$ and $\ket{L}$ , $O$ is a transformation that moves a vector to a vector symmetric to $\ket{\psi'}$ , while $U_{\psi}$ is a transformation that moves a vector to a vector symmetric to $\ket{\psi}$

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit, QuantumRegister
from qiskit.circuit.library import ZGate
 
 
def compose_oracle(qc: QuantumCircuit, y: QuantumRegister, o: QuantumCircuit) -> QuantumCircuit:
    qc.x(y)
    qc.h(y)
    qc.compose(o, inplace=True)
    qc.h(y)
    qc.x(y)
 
    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:
    x, y = QuantumRegister(n), QuantumRegister(1)
    qc = QuantumCircuit(x, y)
 
    theta = math.asin(1 / math.sqrt(2**n)) * 2
    rotation_count = int(round(math.pi / 2 / theta - 1 / 2))
 
    qc.h(range(n))
 
    for _ in range(rotation_count):
        compose_oracle(qc, y, o)
        qc.h(range(n))
        qc.compose(reflect(n), inplace=True)
        qc.h(range(n))
 
    return qc

B8: Grover's Algorithm II

Editorial

Proof of Equation (1)

Sample Code