Deutschアルゴリズム詳細版

Posted at 2025-05-27

量子アルゴリズムの初手

様々なネットを調べたが、どうしてももっとも基礎であるDeutschアルゴリズムが理解できない。
間の計算が飛んでいたりするからだと思ったので、Geminiに行間をすべて埋めてもらって勉強しました。
ようやく理解できた。

Deutschアルゴリズム

Deutsch（ドイッチュ）アルゴリズムは、与えられた関数 $f: {0, 1} \to {0, 1}$ が「定数関数」であるか「バランス関数」であるかを、古典的なアルゴリズムよりも少ない関数評価回数で判定できる量子アルゴリズムです。具体的には、古典的には最低2回の関数評価が必要なところを、量子力学の原理を利用することで、たった1回の関数評価（オラクルの呼び出し）で判定できます。

1. 問題設定

対象とする関数 $f$ は、1ビットの入力 $x$ を受け取り、1ビットの出力 $f(x)$ を返す関数です。
$$f: {0, 1} \to {0, 1}$$

このような関数は4種類考えられます。

定数関数 (Constant function): $f(0) = f(1)$
- $f_0(x) = 0$ （常に0を出力: $f(0)=0, f(1)=0$）
- $f_1(x) = 1$ （常に1を出力: $f(0)=1, f(1)=1$）
バランス関数 (Balanced function): $f(0) \neq f(1)$
- $f_2(x) = x$ （恒等関数: $f(0)=0, f(1)=1$）
- $f_3(x) = \text{NOT } x$ （否定関数: $f(0)=1, f(1)=0$）

Deutschアルゴリズムの目的は、与えられた関数 $f$ が上記のうち「定数関数」なのか「バランス関数」なのかを判定することです。

2. 古典的なアプローチ

古典的なコンピュータでこの問題を解く場合、関数 $f$ の性質を知るためには、f(0) と f(1) の両方の値を計算する必要があります。

もし $f(0) = f(1)$ ならば、関数 $f$ は定数関数です。
もし $f(0) \neq f(1)$ ならば、関数 $f$ はバランス関数です。
したがって、古典的には最低でも2回の関数評価が必要です。

3. Deutschアルゴリズムのステップ

Deutschアルゴリズムは、2つの量子ビット（qubit）を使用します。

第1量子ビット: 入力レジスタ
第2量子ビット: アンシラレジスタ（補助または出力レジスタ）

ステップ 0: 初期状態の準備

第1量子ビットを状態 $|0\rangle$ に初期化します。
第2量子ビットを状態 $|1\rangle$ に初期化します。

ステップ 1: アダマールゲートの適用

両方の量子ビットにアダマールゲート $H$ を適用します。
アダマールゲートの作用は以下の通りです。
$$H|0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$$
$$H|1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$$

状態 $|\psi_0\rangle$ に $H \otimes H$ （各量子ビットにアダマールゲートを適用）を作用させると、状態 $|\psi_1\rangle$ は次のようになります。
$$
\begin{aligned}
|\psi_1\rangle &= (H \otimes H) |\psi_0\rangle \
&= (H|0\rangle) \otimes (H|1\rangle) \
&= \left( \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \right) \otimes \left( \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) \right) \
&= \frac{1}{2} (|0\rangle + |1\rangle) \otimes (|0\rangle - |1\rangle) \
&= \frac{1}{2} \left( |0\rangle(|0\rangle - |1\rangle) + |1\rangle(|0\rangle - |1\rangle) \right) \
&= \frac{1}{2} \left( |00\rangle - |01\rangle + |10\rangle - |11\rangle \right)
\end{aligned}
$$
ここで、第1量子ビットの状態を $|\phi_A\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$、第2量子ビットの状態を $|\phi_B\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ と定義すると、
$$|\psi_1\rangle = |\phi_A\rangle \otimes |\phi_B\rangle$$
と書けます。さらに、$|\phi_A\rangle$ を展開すると、
$$|\psi_1\rangle = \left( \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle \right) \otimes |\phi_B\rangle = \frac{1}{\sqrt{2}} \left( |0\rangle \otimes |\phi_B\rangle + |1\rangle \otimes |\phi_B\rangle \right)$$
と書くこともでき、この形はオラクルの作用を考える際に便利です。

ステップ 2: オラクルの適用

次に、関数 $f$ を計算する量子オラクル $U_f$ を適用します。
オラクル $U_f$ は、入力 $|x\rangle|y\rangle$ に対して $|x\rangle|y \oplus f(x)\rangle$ と作用します。ここで $\oplus$ は排他的論理和 (XOR) です。

位相キックバックの導出

$|\phi_B\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ に対してオラクル $U_f$ がどのように作用するかを見てみましょう。
$$
\begin{aligned}
U_f (|x\rangle \otimes |\phi_B\rangle) &= U_f \left( |x\rangle \otimes \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) \right) \
&= \frac{1}{\sqrt{2}} U_f \left( |x\rangle \otimes |0\rangle - |x\rangle \otimes |1\rangle \right) \
&= \frac{1}{\sqrt{2}} \left( U_f (|x\rangle \otimes |0\rangle) - U_f (|x\rangle \otimes |1\rangle) \right) \
&= \frac{1}{\sqrt{2}} \left( (|x\rangle \otimes |0 \oplus f(x)\rangle) - (|x\rangle \otimes |1 \oplus f(x)\rangle) \right) \
&= \frac{1}{\sqrt{2}} |x\rangle \otimes \left( |0 \oplus f(x)\rangle - |1 \oplus f(x)\rangle \right)
\end{aligned}
$$
ここで、$0 \oplus f(x) = f(x)$ です。

もし $f(x) = 0$ ならば、$\left( |f(x)\rangle - |1 \oplus f(x)\rangle \right) = |0\rangle - |1\rangle$
もし $f(x) = 1$ ならば、$\left( |f(x)\rangle - |1 \oplus f(x)\rangle \right) = |1\rangle - |0\rangle = -(|0\rangle - |1\rangle)$
これらはまとめて $(-1)^{f(x)}(|0\rangle - |1\rangle)$ と書けます。
よって、
$$
U_f (|x\rangle \otimes |\phi_B\rangle) = \frac{1}{\sqrt{2}} |x\rangle \otimes \left( (-1)^{f(x)}(|0\rangle - |1\rangle) \right) = (-1)^{f(x)} |x\rangle \otimes \left( \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) \right) = (-1)^{f(x)} |x\rangle \otimes |\phi_B\rangle
$$
これが位相キックバックです。関数 $f(x)$ の値が、第1量子ビットの位相に反映されます。

状態 $|\psi_1\rangle$ へのオラクルの適用

$|\psi_1\rangle = \frac{1}{\sqrt{2}} \left( |0\rangle \otimes |\phi_B\rangle + |1\rangle \otimes |\phi_B\rangle \right)$ に $U_f$ を適用します。
$$
\begin{aligned}
|\psi_2\rangle &= U_f |\psi_1\rangle \
&= U_f \left[ \frac{1}{\sqrt{2}} \left( |0\rangle \otimes |\phi_B\rangle + |1\rangle \otimes |\phi_B\rangle \right) \right] \
&= \frac{1}{\sqrt{2}} \left[ U_f \left(|0\rangle \otimes |\phi_B\rangle\right) + U_f \left(|1\rangle \otimes |\phi_B\rangle\right) \right] \
&= \frac{1}{\sqrt{2}} \left[ (-1)^{f(0)} |0\rangle \otimes |\phi_B\rangle + (-1)^{f(1)} |1\rangle \otimes |\phi_B\rangle \right] \
&= \left( \frac{1}{\sqrt{2}} \left( (-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle \right) \right) \otimes |\phi_B\rangle \
&= \left( \frac{1}{\sqrt{2}} \left( (-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle \right) \right) \otimes \left( \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) \right) \
&= \frac{1}{2} \left[ (-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle \right] \otimes (|0\rangle - |1\rangle)
\end{aligned}
$$

ステップ 3: 再度アダマールゲートの適用（第1量子ビットのみ）

第1量子ビットにのみアダマールゲート $H$ を適用します（第2量子ビットには何もしません、すなわち恒等ゲート $I$ を適用します）。
状態 $|\psi_2\rangle$ に $H \otimes I$ を作用させると、状態 $|\psi_3\rangle$ は次のようになります。
$$ |\psi_3\rangle = (H \otimes I) |\psi_2\rangle $$
第1量子ビットの部分 $\left( \frac{1}{\sqrt{2}} \left( (-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle \right) \right)$ に $H$ を作用させます。
Let $|\phi_A'\rangle = \frac{1}{\sqrt{2}} \left( (-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle \right)$.
$$
\begin{aligned}
H |\phi_A'\rangle &= H \left( \frac{1}{\sqrt{2}} \left( (-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle \right) \right) \
&= \frac{1}{\sqrt{2}} \left( (-1)^{f(0)} H|0\rangle + (-1)^{f(1)} H|1\rangle \right) \
&= \frac{1}{\sqrt{2}} \left( (-1)^{f(0)} \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) + (-1)^{f(1)} \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) \right) \
&= \frac{1}{2} \left[ ((-1)^{f(0)} + (-1)^{f(1)})|0\rangle + ((-1)^{f(0)} - (-1)^{f(1)})|1\rangle \right]
\end{aligned}
$$
これを $|\psi_2\rangle$ の式全体に適用すると（$|\phi_B\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ を思い出すと）、
$$
\begin{aligned}
|\psi_3\rangle &= (H |\phi_A'\rangle) \otimes |\phi_B\rangle \
&= \left( \frac{1}{2} \left[ ((-1)^{f(0)} + (-1)^{f(1)})|0\rangle + ((-1)^{f(0)} - (-1)^{f(1)})|1\rangle \right] \right) \otimes \left( \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle) \right) \
&= \frac{1}{2\sqrt{2}} \left[ ((-1)^{f(0)} + (-1)^{f(1)})|0\rangle + ((-1)^{f(0)} - (-1)^{f(1)})|1\rangle \right] \otimes (|0\rangle - |1\rangle)
\end{aligned}
$$

ステップ 4: 測定

第1量子ビットを計算基底（${|0\rangle, |1\rangle}$）で測定します。
第1量子ビットの状態の振幅に注目します。
第1量子ビットの状態を $|\text{qubit1}\rangle = c_0 |0\rangle + c_1 |1\rangle$ とすると、
$c_0 = \frac{1}{2} ((-1)^{f(0)} + (-1)^{f(1)})$
$c_1 = \frac{1}{2} ((-1)^{f(0)} - (-1)^{f(1)})$
（規格化係数 $1/\sqrt{2}$ はアンシラビットと全体の規格化で考慮されるため、ここでは第1量子ビットの相対的な振幅を見ます）

ケース 1: $f$ が定数関数の場合
このとき、$f(0) = f(1)$ なので、$\alpha = f(0) = f(1)$ とすると、
$(-1)^{f(0)} = (-1)^{\alpha}$
$(-1)^{f(1)} = (-1)^{\alpha}$
よって、
$c_0 = \frac{1}{2} ((-1)^{\alpha} + (-1)^{\alpha}) = \frac{1}{2} (2(-1)^{\alpha}) = (-1)^{\alpha}$
$c_1 = \frac{1}{2} ((-1)^{\alpha} - (-1)^{\alpha}) = \frac{1}{2} (0) = 0$
第1量子ビットの状態は $(-1)^{\alpha}|0\rangle$ となります。
測定すると $|0\rangle$ が確率 $1$ で得られます (確率 $|c_0|^2 = |(-1)^{\alpha}|^2 = 1$）。
ケース 2: $f$ がバランス関数の場合
このとき、$f(0) \neq f(1)$ なので、
$(-1)^{f(0)} = -(-1)^{f(1)}$
よって、
$c_0 = \frac{1}{2} ((-1)^{f(0)} + (-1)^{f(1)}) = \frac{1}{2} ((-1)^{f(0)} - (-1)^{f(0)}) = 0$
$c_1 = \frac{1}{2} ((-1)^{f(0)} - (-1)^{f(1)}) = \frac{1}{2} ((-1)^{f(0)} - (-(-1)^{f(0)})) = \frac{1}{2} (2(-1)^{f(0)}) = (-1)^{f(0)}$
第1量子ビットの状態は $(-1)^{f(0)}|1\rangle$ となります。
測定すると $|1\rangle$ が確率 $1$ で得られます (確率 $|c_1|^2 = |(-1)^{f(0)}|^2 = 1$）。

測定結果の解釈

第1量子ビットの測定結果が $0$ であれば、関数 $f$ は定数関数です。
第1量子ビットの測定結果が $1$ であれば、関数 $f$ はバランス関数です。

このように、Deutschアルゴリズムでは、関数 $f$ の量子オラクル $U_f$ を一度だけ呼び出すだけで、関数が定数関数かバランス関数かを100%の確率で判定できます。

4. 量子オラクル $U_f$ について

量子アルゴリズムの文脈で「オラクル $U_f$」という表現がよく使われます。これは、特定の古典関数 $f$ の計算を量子回路内で実現するための、一種の「ブラックボックス」あるいは「サブルーチン」のようなものです。

定義: オラクル $U_f$ は、入力用の量子ビット $|x\rangle$ と補助的なアンシラ量子ビット $|y\rangle$ を取り、以下のように作用します。
$$U_f : |x\rangle|y\rangle \to |x\rangle|y \oplus f(x)\rangle$$
ここで、$\oplus$ は排他的論理和 (XOR) です。
背景: この定義は、以下の理由に基づいています。
1. 量子計算の可逆性 (Unitarity): 量子演算は可逆でなければなりません。$U_f$ のこの形式は、同じ操作を2回行うと元に戻るため（$(A \oplus B) \oplus B = A$）、可逆性を満たします。
2. 入力情報の保持: 入力 $|x\rangle$ は変化せずに保持されます。
3. 関数値のエンコード: アンシラビットの初期状態を $|0\rangle$ とすると、$U_f |x\rangle|0\rangle = |x\rangle|f(x)\rangle$ となり、関数値が直接アンシラビットに書き込まれます。
4. 位相キックバックの実現: アンシラビットを特定の重ね合わせ状態（例：$(|0\rangle - |1\rangle)/\sqrt{2}$）にすると、$f(x)$ の情報が入力ビット $|x\rangle$ の位相に「キックバック」される現象が起こり、これがDeutschアルゴリズムなどの鍵となります。

5. まとめと意義

Deutschアルゴリズムは、

初期化: $|01\rangle$
アダマール変換 (両ビット): $(H \otimes H)$
オラクル適用: $U_f$
アダマール変換 (第1ビットのみ): $(H \otimes I)$
測定 (第1ビット)
というステップで構成されます。

このアルゴリズムは、量子計算が古典計算に対して特定の種類の問題で優位性を持つことを示した最初の例です。「量子の並列性」（重ね合わせ状態にある複数の入力に対して一度に演算を適用できる能力）と、「量子干渉」（望ましい結果の振幅を増幅し、望ましくない結果の振幅を相殺する）を利用して、この効率化を達成しています。

Deutschアルゴリズム自体は実用的な問題を解くものではありませんが、より複雑で強力な量子アルゴリズム（Deutsch-Jozsaアルゴリズム、Shorの因数分解アルゴリズム、Groverの探索アルゴリズムなど）の基礎となる重要な概念を提示しています。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Deutschアルゴリズム 詳細版