QCoder

解説

本問題もB6やB8と同様に特定の計算基底状態の確率振幅を増幅する問題です。しかし、通常のグローバーのアルゴリズムをそのまま用いた場合、回路の深さを $75$ 以内にすることはできません。

そこで、本問題の「 $L$ は $2$ のべきのいずれかである」という条件に注目します。

これは「 $\ket{L}$ は $n$ 種類の計算基底状態 $\ket{100...0}_n, \ket{010...0}_n, ... \ket{000...1}_n$ のいずれかである」と言い換えられます。

よって、グローバーのアルゴリズムの初期状態として $H$ ゲートによる一様重ね合わせ状態を利用するのは、明確に増幅の対象となりえない状態を含むため非効率です。代わりに A6 問題の量子状態 $\ket{\psi}$ を初期状態として用いることでイテレーションの回数を少なくすることができます。

\ket{\psi} = \frac{1}{\sqrt{n}} \lparen \ket{100...0}_n + \ket{010...0}_n + \cdots + \ket{000...1}_n \rparen

また、この問題において、増幅したい計算基底状態の符号を反転させる操作はオラクル $O$ そのものを利用できます。

演算子 $2\ket{\psi}\bra{\psi}-I$ で表される操作は、A6で実装した回路を用いてB7と同じように実装することができます。

イテレーションを行う最適な回数について、B8と同様に考察すると、以下の実数 $r$ に近い非負整数であることがわかります。

r=\frac{\pi}{2\theta}-\frac{1}{2}\ \left(\theta=2\sin^{-1}\frac{1}{\sqrt{n}}\right)

$3\leq n\leq 6$ の場合は $1$ 回のイテレーションで、 $8\leq n\leq 15$ の場合は $2$ 回のイテレーションで、操作後に $|a_L|^2\geq 0.9$ を満たすことが計算できます。また、回路の深さが制約を超えないように実装できることもわかります。

$n=2$ と $n=7$ の場合は上記の方法では $|a_L|^2\geq 0.9$ を満たすイテレーション回数が整数に存在しません。この問題に対処する方法には、 $\ket{\psi}$ を用意する際に $1$ つの量子ビットのみに $H$ ゲートを作用させて $2n$ の場合に落としこむ方法が考えられます。また、アンシラビットを $1$ つ用意する方法や、 $n=2$ の場合は通常のグローバーのアルゴリズムを実行する方法なども考えられます。

解答例

解答例は以下の通りです。

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

Ex2: Find Hidden Number

解説

解答例