A3: Cyclic Shift Oracle I

解説

問題 A2 にて実装したスワップゲートを利用することで、この問題を解くことができます。

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

まず、$2$ 番目と $3$ 番目の量子ビットをスワップします。

次に、$1$ 番目と $2$ 番目の量子ビットをスワップします。

したがって、$2$ 回のスワップで量子状態 $\ket{x_2x_0x_1}$ を得ることができました。

以上の操作を一般化すると、$n-1$ 回のスワップによって目的の量子状態 $\ket{x_{n-1} x_0 x_1 \cdots x_{n-2}}$ を生成できます。 さらに、各スワップは深さ $3$ の量子回路で実装できるため、全体の量子回路の深さは $3(n-1)$ となり、結果としてこの問題を解くことができます。

解答例

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

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

探求

コンテスト後、hiryuN さんによって回路深さ $3 \lceil \log_2 n \rceil$ の解法が 発見 されました。 このアルゴリズムは、A4: Cyclic Shift Oracle の $\ket{x}\rightarrow \ket{(x+1) \bmod n}$ のアルゴリズムを、$i$ ビット目で $(i+1) \bmod n$ ビット目を置き換える操作に言い換えると導かれます。