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と1をそれぞれ返す場合balanced
と関数の性質を判定するアルゴリズムです。
古典コンピューターの場合、関数の性質を判定するのに最悪の場合、総当たり的に入力を与えないと解が求まらないのに対して、量子コンピュータを使うと多項式時間で解が求まることを検証していきます。
Deutsch–Jozsa Algorithm概要
アルゴリズムで実施すること自体はシンプルです。- Apply the H gate to each qubit.
各ビットにアダマールゲートを適用します。 - Apply the oracle.
量子オラクルを適用します。 - Apply the H gate to each qubit again.
各ビットに再度アダマールゲートを適用します。 - Measure each qubits.
各ビットを測定します。 - 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; }