Part II. Quantum Oraclesの解説
今回は全4部のうちのPart 2です。
Deutsch-JozsaのTutorialは4部に分かれています。
Part 1: 問題の定義と古典アルゴリズムについて
Part 2: 量子オラクルについて
Part 3: 量子アルゴリズムについて
Part 4: 実際にDeutsch-Jozsaを量子アルゴリズムで動かしてみる
自分で書いていて怪しい部分もあるので、間違い等あれば指摘していただけると助かります。
Quantum Oracle(量子オラクル)とは
Oracleを普通に辞書で調べても「神託」とかデータベースのオラクルとか、ここではよくわからない翻訳しか出てこなくてよくわかりません。量子コンピュータでのオラクルとは
QuantumKatasからの引用その他参考リンク
A quantum oracle is a "black box" operation which is used as input to another algorithm. This operation is implemented in a way which allows to perform calculations not only on individual inputs, but also on superpositions of inputs.
Oracles are often defined using a classical function, in the case of Deutsch-Jozsa algorithm the function \(f : \{0, 1\}^N \to \{0, 1\}\) takes an \(N\)-bit binary input and produces an 1-bit binary output.
The oracle has to act on quantum states instead of classical values. To enable this, integer input \(x\) is represented in binary \(x = (x_{0}, x_{1}, \dots, x_{N-1})\) and encoded into an \(N\)-qubit register: \(|\vec{x} \rangle = |x_{0} \rangle \otimes |x_{1} \rangle \otimes \cdots \otimes |x_{N-1} \rangle\)
\(f : \{0, 1\}^N \to \{0, 1\}^M\)はN-bitのバイナリデータを入力としM-bitのバイナリデータを出力とするという意味で、Deutsch–JozsaではM=1のケースを扱います。
N-bitのバイナリデータは\(|\vec{x} \rangle = |x_{0} \rangle \otimes |x_{1} \rangle \otimes \cdots \otimes |x_{N-1} \rangle\)で、各ビット(\(x_{0}\)など)は\(|0\rangle\)か\(|1\rangle\)のみをとり、そのテンソル積が入力となります。
Oracleの考え方は出力ビットyを用いた方法とPhase Oracleを用いた方法と2つありますが、 このチュートリアルでは \(U_f |\vec{x} \rangle = (-1)^{f(x)} |\vec{x} \rangle\) を基本としたPhase Oracleを中心に考えます。ここでは\(U_f |x\rangle\)のOperationを作ることを考えます。 \(f(x)\)は0か1しかとらないので、\(x=0\)の場合は、\(-1^0=1\)となり位相の変化なし、\(x=0\)の場合は\(-1^1=-1\)となり位相の変化が発生します。
これだけ見るとよくわからないですが、実際にDeutsch algorithmを適用した場合に
\(U_f \left( \frac{1}{\sqrt2} \big( |0\rangle + |1\rangle \big) \right) = \frac{1}{\sqrt2} \big( U_f |0\rangle + U_f |1\rangle \big) = \frac{1}{\sqrt2} \big( (-1)^{f(0)} |0\rangle + (-1)^{f(1)} |1\rangle \big) \)
となり
\(f(0) = f(1)\)の場合すべてのbasis stateの位相が同じとなり、最終的な結果が\(|+\rangle = \frac{1}{\sqrt2} \big( |0\rangle + |1\rangle \big)\)となります。
\(f(0) \neq f(1)\)の場合、\(-1^0\)と\(-1^1\)で位相が異なり、最終的な結果が \(|-\rangle = \frac{1}{\sqrt2} \big( |0\rangle - |1\rangle \big)\)となります。
\(|+\rangle\)と \(|-\rangle\)この状態はアダマール変換をかけるとそれぞれ\(|0\rangle\)と\(|1\rangle\)になるため、観測による状態判定可能になります。つまり、\(f(x)\)がConstantな場合は最終的に0が観測でき、Balancedな場合は1が観測できます。
Exercise 3: Implement a quantum oracle in Q#
Most Significant Bitが1の場合、そのbasis stateに-1のPhaseを与えるという問題。\(f(x) = x_{0}\), となり、
\[U_f = Z \otimes \cdots \otimes \mathbb{1} \otimes \mathbb{1}\]
\[U_f |x\rangle = (-1)^{f(x)} |x\rangle = (-1)^{x_{0}} |x\rangle = (-1)^{x_{0}}|x_{0} \rangle \otimes \cdots \otimes |x_{N-2} \rangle \otimes |x_{N-1}\rangle\]
となります。
%kata E3_QuantumOracle_Test
operation PhaseOracle_MostSignificantBit (x : Qubit[]) : Unit {
Z(x[0]);
}
