A4: Cyclic Shift Oracle II

解説

問題 A2 にて実装したスワップゲートの意味を考えましょう。

解法1

はじめに、$2$ 量子ビットのスワップについて考えます。 $1$ 番目の量子ビットと $2$ 番目の量子ビットをスワップする操作は、制御 $X$ ゲートを用いることで実現でき、状態遷移は以下のようになります。

ここで、$2$ 番目の量子ビットが $0$ である時、すなわち $\ket{00}, \ket{10}$ となる時の状態遷移に注目します。

上記の $(2)$ 式のように、はじめの「$1$ 番目の量子ビットを制御ビット、$2$ 番目の量子ビットを標的ビットとする制御 $X$ ゲート」と、次の「$2$番目の量子ビットを制御ビット、$1$ 番目の量子ビットを標的ビットとする制御 $X$ ゲート」によって $2$ 量子ビットのスワップが実現されていることがわかります。 これを上手く利用することで、この問題を解くことができます。

まず、$x_{n-1} = 0$ であることから $x_{n-2}, x_{n-1}$ は $2$ ステップで交換でき、以下の状態遷移が成り立ちます。

同様に、$x_{n-1} = 0$ であることから $x_{n-3}, x_{n-1}$ は $2$ ステップで交換でき、以下の状態遷移が成り立ちます。

同様の操作を全部で $n-1$ 回行うことで、目的の量子状態 $\ket{x_{n-1} x_0 x_1 \cdots x_{n-2}}$ を深さ $2(n-1)$ で生成することができます。

$n = 3$ の場合の回路図は、以下の通りです。

解法2

A2 の解説で述べたように、3ステップで $2$ 変数 $x, y$ をスワップする古典アルゴリズムとして、XOR swap が知られています。 特に $y=0$ のとき $3$ ステップ目の「$y$ を $x + y \pmod 2$ で置き換える操作」を省略できるため、「$y$ を $x + y \pmod 2$ で置き換える操作」と「 $x$ を $x + y \pmod 2$ で置き換える操作」の $2$ ステップでXOR swapを実現することができます。 これを利用することで、以下解法で解くこともできます。

まず、制御 $X$ ゲートを用いて $y$ を $x + y \pmod 2$ で置き換える操作を $1, 2, \ldots, n-1$ ビット目に対して行います。

for i in reversed(range(n - 1)):
    qc.cx(i, i + 1)  

次に、制御 $X$ ゲートを用いて $x$ を $x + y \pmod 2$ で置き換える操作を $1, 2, \ldots, n-1$ ビット目に対して行います。

for i in reversed(range(n - 1)):
    qc.cx(i + 1, i)  

これによって解法1と同様に、目的の量子状態 $\ket{x_{n-1} x_0 x_1 \cdots x_{n-2}}$ を深さ $2(n-1)$ で生成することができます。

$n = 3$ の場合の回路図は、以下の通りです。

解答例

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

解法1

from qiskit import QuantumCircuit
 
 
def solve(n: int) -> QuantumCircuit:  
    qc = QuantumCircuit(n)  
 
    for i in reversed(range(n - 1)):
        qc.cx(i, i + 1)
        qc.cx(i + 1, i)
 
    return qc

解法2

from qiskit import QuantumCircuit
 
 
def solve(n: int) -> QuantumCircuit:  
    qc = QuantumCircuit(n)
 
    for i in reversed(range(n - 1)):
        qc.cx(i, i + 1)
 
    for i in reversed(range(n - 1)):
        qc.cx(i + 1, i)
 
    return qc