QCoder

解説

問題 A5 の想定解法では量子ビット数 $n$ に対して量子回路の深さが $n + 2$ であり、この問題を解くことができません。より効率的な方法を考える必要があります。

以下の $6$ 量子ビットの例をみてみましょう。

この量子回路は、量子状態 $\frac{1}{\sqrt{6}} (\ket{100000} + \ket{010000} + \ket{001000} + \ket{000100} + \ket{000010} + \ket{000001})$ を生成します。以下、量子回路上のバリア ¹ を境に分けたブロックごとに解説していきます。

1つ目のブロックでは、1番目の量子ビットに $X$ ゲートを作用させます。

\begin{equation} \ket{000000} \xrightarrow{X(0)} \ket{100000} \end{equation}

2つ目のブロックでは、 $\ket{100000}$ と $\ket{010000}$ の一様重ね合わせを生成します。

\begin{equation} \ket{100000} \xrightarrow{CRy(\theta_1,0,1)} \xrightarrow{CX(1,0)} \sqrt{\frac{3}{6}} \ket{100000} + \sqrt{\frac{3}{6}} \ket{010000} \end{equation}

3つ目のブロックでは、 $\ket{100000}$ と $\ket{010000}$ をさらに分裂させます。

\begin{align} &\sqrt{\frac{3}{6}} \ket{100000} + \sqrt{\frac{3}{6}} \ket{010000} \nonumber\\ &\xrightarrow{CRy(\theta_2,0,2)} \xrightarrow{CX(2,0)} \xrightarrow{CRy(\theta_3,1,3)} \xrightarrow{CX(3,1)} \sqrt{\frac{1}{6}} \ket{100000} + \sqrt{\frac{1}{6}} \ket{010000} + \sqrt{\frac{2}{6}} \ket{001000} + \sqrt{\frac{2}{6}} \ket{000100} \end{align}

最後に4つ目のブロックの遷移は次のように表されます。

\begin{align} &\sqrt{\frac{1}{6}} \ket{100000} + \sqrt{\frac{1}{6}} \ket{010000} + \sqrt{\frac{2}{6}} \ket{001000} + \sqrt{\frac{2}{6}} \ket{000100} \xrightarrow{CRy(\theta_4,2,4)} \xrightarrow{CX(4,2)} \nonumber\\ &\xrightarrow{CRy(\theta_5,3,5)} \xrightarrow{CX(5,3)} \frac{1}{\sqrt{6}} (\ket{100000} + \ket{010000} + \ket{001000} + \ket{000100} + \ket{000010} + \ket{000001}) \end{align}

なお、各回転角 $\theta_i$ は以下の通りです。

\begin{align} \theta_1 &= 2 \arctan{(\sqrt{1})}\\ \theta_2 &= \theta_3 = 2 \arctan{(\sqrt{1})}\\ \theta_4 &= \theta_5 = 2 \arctan{(\sqrt{1})}\\ \end{align}

この量子回路の深さは4となるので、はるかに小さい回路の深さを実現できています。

次に、この操作を一般化します。問題となるのは、回転角の定め方です。

$6$ 量子ビットの場合を例として、以下のような木構造を考えます。

各ノード $(a, b)^{(i, j)}$ は、 $i$ 番目の量子ビットの振幅 $\sqrt{b/n}$ のうち $\sqrt{a/n}$ を $j$ 番目の量子ビットに分け与える操作を表します。すなわち、この $i$ 番目を制御ビット、 $j$ 番目を標的ビットとする制御 $R_y$ ゲートの回転角 $\theta$ は以下の連立方程式を解くことで求めることができます。

\begin{equation} \left\{ \, \begin{aligned} & \cos\left(\frac{\theta}{2}\right) = \sqrt{\frac{a}{n}} \\ & \sin\left(\frac{\theta}{2}\right) = \sqrt{\frac{b-a}{n}} \end{aligned} \right. \end{equation}

この方程式を解くと、 $0 \leq \theta \leq 2\pi$ の範囲で次の解が得られます。

\begin{equation} \theta = 2 \arctan{\left(\sqrt{\frac{b-a}{a}}\right)} \end{equation}

なお、この木構造では親ノード $(a, b)^{(i, j)}$ に対して、上下の子ノードはそれぞれ $(\lfloor\lfloor b/2 \rfloor/2\rfloor,\lfloor b/2 \rfloor)^{(i, ?)}$ と $(\lfloor \lceil b/2 \rceil/2 \rfloor,\lceil b/2 \rceil)^{(j, ?)}$ と表されます。 $a = 0$ のとき、そのような操作は意味をなさないため定義されません。また、標的ビットのインデックス $j$ は $2$ から $n$ までの数を木の根から近い順に各ノードに割り当てていくことで得られます。

以上を元に量子回路を設計することで、量子回路の深さは $2 \lceil \log_{2}{n} \rceil + 1$ となり、この問題を解くことができます。

実装にあたって、木構造の探索には幅優先探索などの手法を用いることができます。

解答例

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

import math
 
from qiskit import QuantumCircuit
 
 
def solve(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

Qiskit ではバリア (qc.barrier()) が深さにカウントされてしまうため、提出するコードには含めないように注意して下さい。 ↩

A6: Generate One-hot Superposition State III

解説

解答例

Footnotes