Part III. Quantum Algorithm

今回は全4部のうちのPart 3です。

Deutsch-JozsaのTutorialは4部に分かれています。
Part 1: 問題の定義と古典アルゴリズムについて
Part 2: 量子オラクルについて
Part 3: 量子アルゴリズムについて
Part 4: 実際にDeutsch-Jozsaを量子アルゴリズムで動かしてみる

Deutsch–Jozsa Algorithm問題定義

もう一度Deutsch–Jozsaの問題定義をおさらいしておきます。
Deutsch-Jozsaアルゴリズムとは中身のわからないブラックボックスな関数\(f(x)\)について、
1) すべての入力\(x\)に対して、常に0を返す、あるいは、常に1を返す場合、constant
2) 入力\(x\)に対して50%ずつの確率で0と１をそれぞれ返す場合balanced
と関数の性質を判定するアルゴリズムです。

古典コンピューターの場合、関数の性質を判定するのに最悪の場合、総当たり的に入力を与えないと解が求まらないのに対して、量子コンピュータを使うと多項式時間で解が求まることを検証していきます。

Deutsch–Jozsa Algorithm概要

アルゴリズムで実施すること自体はシンプルです。

1. Apply the H gate to each qubit.
   各ビットにアダマールゲートを適用します。
2. Apply the oracle.
   量子オラクルを適用します。
3. Apply the H gate to each qubit again.
   各ビットに再度アダマールゲートを適用します。
4. Measure each qubits.
   各ビットを測定します。
5. If all qubits were measured in  |0⟩  state, the function is constant, otherwise it is balanced.
   全ビットが\(|0\rangle\)に読めれば関数\(f(x)\)はconstant, 1つでも\(|1\rangle\)が読めればbalancedと判断

なぜこの手順で判断できるのかを考えてみましょう。

Deutsch–Jozsa Algorithm詳細

1) Apply the H gate to each qubit. 各ビットにアダマールゲートを適用

入力を\(\frac{1}{\sqrt2} \big(|0\rangle + |1\rangle \big)\)の状態に変換する。この形は\(|0\rangle\)と\(|1\rangle\)を同じ確率で取りうる重ね合わせ状態

2Qubitの\(|00\rangle\)にアダマール変換をかけた場合 \[(H \otimes H) |00\rangle = \big(H |0\rangle \big) \otimes \big(H |0\rangle\big) = \left(\frac{1}{\sqrt2} \big(|0\rangle + |1\rangle \big)\right) \otimes \left(\frac{1}{\sqrt2} \big(|0\rangle + |1\rangle \big)\right) = \frac{1}{2} \big(|00\rangle + |01\rangle + |10\rangle + |11\rangle \big)\] となる。これはすべてのbasis stateを同じ確率で重ね合わせた状態である。

これをもとにN-Qubitの場合を考えると
\[ H^{\otimes N} |0\rangle^{\otimes N} = \big( H|0\rangle \big)^{\otimes N} = \left( \frac{1}{\sqrt2} \big(|0\rangle + |1\rangle \big) \right)^{\otimes N} = \frac{1}{\sqrt{2^N}} \sum_{x=0}^{2^N-1} |x\rangle = \frac{1}{\sqrt{2^N}} \big(|0\rangle + |1\rangle + |2\rangle + \ldots +|2^N- 1\rangle \big) = \frac{1}{\sqrt{2^N}} \big(|x_0\rangle \otimes |x_1\rangle \otimes |x_2\rangle \otimes \ldots \otimes |x_N\rangle \big) \]
となる。 
\(\sum\)で書かれると一気によくわからなくなるが、ここは0から\(2^N-1\)までの重ね合わせ状態とばらして考えればよく、各ビットのテンソル積にばらせる場合は0からNビット目までのテンソル積にばらすのと同等と考えてよい。

2) Apply the oracle. 量子オラクルを適用

ここで\(|x\rangle\)にOracleをかける
\[U_f \left(\frac{1}{\sqrt{2^N}} \sum_{x=0}^{2^N-1} |x\rangle \right) = \frac{1}{\sqrt{2^N}} \sum_{x=0}^{2^N-1} U_f|x\rangle = \frac{1}{\sqrt{2^N}} \sum_{x=0}^{2^N-1} (-1)^{f(x)} |x\rangle \]

3) Apply the H gate to each qubit again. 各ビットに再度アダマールゲートを適用

\[ \begin{align}\dfrac{1}{2^N} \sum_{x=0}^{2^N-1} (-1)^{f(x)} \sum_{y=0}^{2^N-1} (-1)^{x \cdot y} \lvert y \rangle = \sum_{y=0}^{2^N-1} \left( \dfrac{1}{2^N} \sum_{x=0}^{2^N-1} (-1)^{f(x)} (-1)^{x \cdot y} \right) \lvert y \rangle\end{align} \]

4) Measure each qubits. 各ビットを測定します。

全N-Qubitを観測して、\({\lvert 0 \rangle ^{\otimes N}}\)が読める確率を考えてみます。
\[\left( \dfrac{1}{2^N} \sum_{x=0}^{2^N-1} (-1)^{f(x)} (-1)^{x \cdot y} \right) \lvert y \rangle^{\otimes N}\]
と考えて、係数の部分に着目し\(|y\rangle={\lvert 0 \rangle ^{\otimes N}}\)=のケースを考えます。
\(x \cdot y\)は\(x\)と\(y\)のBitwise Inner Productで、単純に\(y_N = |0\rangle\)の場合、\(x \times 0\)で0と考えてよいです。つまり、
\[\left( \dfrac{1}{2^N} \sum_{x=0}^{2^N-1} (-1)^{f(x)} \right) \lvert 0 \rangle^{\otimes N}
=\left( \dfrac{1}{2^N} \sum_{x=0}^{2^N-1} (-1)^{f(x)} \right) \left( \lvert 0 \rangle \otimes \lvert 0 \rangle \otimes\ldots \lvert 0 \rangle\right) \]
となり、\(f(x)\)がconstantの場合係数が1または-1、つまり\({\lvert 0 \rangle ^{\otimes n}}\)が読める確率が100%(\(1^2=1, -1^2=1\))、\(f(x)\)がbalancedの場合係数が0、\({\lvert 0 \rangle ^{\otimes N}}\)が読める確率は0%(\(0^2=1\))となります。

Exercise 4: Implement the quantum algorithm!

ここまで来たらあとの実装は簡単だと思います。

operation DeutschJozsaAlgorithm (N : Int, oracle : (Qubit[] => Unit)) : Bool {
    // Create a boolean variable for storing the return value.
    // You'll need to update it later, so it has to be declared as mutable.
    mutable isConstant = true;

    // Allocate an array of N qubits for the input register x.
    using (x = Qubit[N]) {
        // Newly allocated qubits start in the |0⟩ state.
        // The first step is to prepare the qubits in the required state before calling the oracle.
        // A qubit can be transformed from the |0⟩ state to the |+⟩ state by applying a Hadamard gate H.
        ApplyToEach(H, x);

        // Apply the oracle to the input register.
        // The syntax is the same as for applying any function or operation.
        oracle(x);

        // Apply a Hadamard gate to each qubit of the input register again.
        ApplyToEach(H, x);

        // Measure each qubit of the input register in the computational basis using the M operation.
        // You can use a for loop to iterate over the range of indexes 0..N-1.
        // Note that you can't return the answer in the middle of a loop,
        // you have to update the variable isConstant using the "set" keyword.
        for (i in 0 .. N-1) {
            let a = M(x[i]);
            if (a == One) {
                set isConstant = false;
                ResetAll(x);
            }
        }

        // Before releasing the qubits make sure they are all in the |0⟩ state
        // (otherwise you'll get a ReleasedQubitsAreNotInZeroState exception).
        // You can use the library operation Reset which measures a qubit and applies a correction if necessary.
        // The library operation ResetAll does the same for a register of qubits.
        ResetAll(x);
    }
    
    // Return the value of the boolean variable.
    return isConstant;
}