ドイチェとドイチェ・ジョザとサイモンのアルゴリズム

はじめに

この記事では、以下3つの量子アルゴリズムを紹介します。

• ドイチェのアルゴリズム
• ドイチェ・ジョザのアルゴリズム
• サイモンのアルゴリズム

特に、それぞれのアルゴリズムに対し、①対象の問題、②古典との比較、③アルゴリズムの詳細の3つの観点で説明します。

なお、細心の注意は払っていますが、私自身、量子の学習歴が短い人間であるため、もし、間違っている点、よろしくない表現等ありましたらご指摘をよろしくお願いいたします。

$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$

ドイチェのアルゴリズム

1985年にドイチェ（Deutsch）によって提案されたアルゴリズムであり、特定の問題に対して、量子コンピュータを利用して、効率的に解くことができるアルゴリズムとなっています。

対象の問題

ドイチェのアルゴリズムは、入力、出力がそれぞれ1ビットの2値関数$f(x)$が与えられた時、この関数$f(x)$は平衡関数(balanced)と定数関数(constant)のどちらなのかという問題を扱います。

ここで、平衡関数とは2種類の入力(0と1)に対し、0と1を1回ずつ出力関数であり、定数関数はどちらの入力に対しても、出力の値が同じ(0のみor1のみの)関数となっています。

具体的に、$f(x)$の考えられる入力と出力のパターンは4通りですが、平衡関数、および定数関数の分類は以下に示すとおりになります。

• 平衡関数
  • パターンA：$f(0)=0, f(1)=1$
  • パターンB：$f(0)=1, f(1)=0$
• 定数関数
  • パターンC：$f(0)=0, f(1)=0$
  • パターンD：$f(0)=1, f(1)=1$

まとめると、ドイチェのアルゴリズムは、$f(x)の4つのパターンからランダムで1つ選択された時、それが平衡関数なのか定数関数なのかを判定するアルゴリズムとなっています。

古典との比較

結論から言うと、古典コンピュータでこの問題を解いた時の関数の判定回数が2回、量子コンピュータでドイチェのアルゴリズムを用いた時の関数の判定回数は1回となります。ここでいう関数の判定回数とは、関数$f(x)$を評価した回数となっています。

どちらのコンピュータでも、ある入力を与えた、出力値を見て、$f(x)$が平衡関数or定数関数なのかを判断しますが、古典コンピュータでは、入力が0と1の時をそれぞれ1回ずつ評価するため、関数の判定回数は2回となります。

例えば、前のセクション「対象の問題」で挙げた4パターンの内、$f(x)$がパターンA（$f(0)=0, f(1)=1$）だった場合、古典コンピュータでは、以下の流れで、$f(x)$が平衡関数であることを判定します。

• 1回目：入力0を与え、出力$f(0)=0$を観測
• 2回目：入力1を与え、出力$f(1)=1$を観測　➡　つまり、平衡関数！！

一方、量子コンピュータのドイチェのアルゴリズムでは、いわゆる重ね合わせ状態の有効活用によって、関数の判定回数1回を実現しています。

アルゴリズムの詳細

ドイチェのアルゴリズムの説明に入る前に、$U_x$ゲートについて説明します。
量子コンピュータを利用して、入力$x$に対する、2値関数$f(x)$の値を取得したいとき、入力に制御ビット$y$を含む、以下のような量子回路をよく組みます。

式で表すと以下の通りです。

$$U_x(\ket{x}⊗\ket{y})=\ket{x}⊗\ket{y⊕f(x)}$$
（なお、$U_x$のように、「中身の処理は置いておいて、入力に対して、どう出力するべきか」を定めたものをオラクルと呼びます。）

しかし、ドイチェが扱った問題に対し、この回路を利用して、$f(x)$の値を1つずつ取得して、定数or平衡関数を判定しようとすると、結局、古典と同じ関数の判定回数（2回）を必要としてしまいます。

そこで、ドイチェのアルゴリズムでは、**「わざわざ、$f(x)$の値を求めなくても、定数or平衡関数を判定できさえすれば、良いじゃん」**という発想のもとで、回路を組み、関数の判定回数1回を実現しました。

具体的には、以下のような回路図¹を用います。

$H$はアダマールゲート、$U_x$は最初に紹介したオラクルを示しています。また、右上のメーターのような記号は測定記号であり、上位ビットのみを測定します。

ドイチェのアルゴリズムの大まかな流れとしては、3つにわけることができ、①アダマールゲートに通し、重ね合わせ状態を作る。②オラクルに通す、③再びアダマールゲートに通し、上位ビットを測定するといった順番で、問題を解いていきます。

なお、肝心の関数$f(x)$の判定については、入力$\ket{0} と\ket{1}$に対し、上位ビットの測定値が$\ket{0}$の時、定数関数、$\ket{1}$の時、平衡関数となるように、回路が組まれており、$f(x)$の値を直接取得しない構成となっています。

①アダマールゲートに通し、重ね合わせ状態を作る

入力$\ket{0} と\ket{1}$のそれぞれに対し、アダマールゲート$H$を適用すると、以下のようになります。
なお、$\ket{00}=\ket{0}⊗\ket{0}$です。

H(\ket{0})⊗H(\ket{1}) = \frac{1}{\sqrt{2}}(\ket{0} + \ket{1})⊗\frac{1}{\sqrt{2}}(\ket{0} - \ket{1})=\frac{1}{2}(\ket{00} + \ket{10}- \ket{01} - \ket{11})

②、③で説明しますが、アダマールゲートによって、重ね合わせ状態を作ることで、1回の実行のみで、$f(x)$が平衡関数なのか、定数関数なのかを判定することができます。

②オラクルに通す

①で得た重ね合わせ状態を入力として、オラクルを実行すると以下に示すとおりになります。

U_x\left(\frac{1}{2}(\ket{00} + \ket{10}- \ket{01} - \ket{11})\right)=\frac{1}{2}(U_x(\ket{00}) +U_x(\ket{10})- U_x(\ket{01}) - U_x(\ket{11}))=\frac{1}{2}((\ket{0}⊗\ket{0⊕f(0)}) + (\ket{1}⊗\ket{0⊕f(1)})- (\ket{0}⊗\ket{1⊕f(0)}) - (\ket{1}⊗\ket{1⊕f(1)}))

以上の式は、いくつかの式変換を通じて、最終的に以下のようになります。
$$\frac{1}{\sqrt{2}}((-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1})⊗\frac{1}{\sqrt{2}}(\ket{0} - \ket{1})$$

オラクルの出力と回路図の対応は、以下に示す通りです。

測定記号は上位ビットのみにしか配置していないため、③では$\frac{1}{\sqrt{2}}((-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1})$のみに注目していきます。

③再びアダマールゲートに通し、測定する

まず、以下の、②で得られたオラクルの出力の上位ビットをアダマールゲート$H$に通します。
$$\frac{1}{\sqrt{2}}((-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1})$$
ここで、平衡関数の時、$f(0)≠f(1)$であるため、アダマールゲートの適用によって、$\ket{1}$が測定されます。
$$H\left(\frac{1}{\sqrt{2}}((-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1})\right)=±H\left(\frac{1}{\sqrt{2}}(\ket{0} - \ket{1})\right)=±\ket{1}$$
また、定数関数の時、$f(0)=f(1)$であるため、アダマールゲートの適用によって、$\ket{0}$が測定されます。
$$H\left(\frac{1}{\sqrt{2}}((-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1})\right)=±H\left(\frac{1}{\sqrt{2}}(\ket{0} + \ket{1})\right)=±\ket{0}$$

このようにして、ドイチェのアルゴリズムは、1回の実行・測定のみで、関数$f(x)$が平衡関数なのか、定数関数なのかの判定を行います。

ドイチェ・ジョザのアルゴリズム

1992年に、ドイチェ・ジョザ(Jozsa)によって提案されたアルゴリズムであり、簡単に言うと、先ほど紹介したドイチェのアルゴリズムの一般化、つまり、f(x)の入出力がnビットであるバージョンとなっています。

対象の問題

ドイチェ・ジョザのアルゴリズムは、関数$f(x)$の入力、出力がそれぞれnビットであること以外、ドイチェのアルゴリズムと基本的に同じであり、関数$f(x)$が平衡関数(balanced)と定数関数(constant)のどちらなのかという問題を扱います。ここで、入出力がnビットの場合での平衡関数とは、n個の入力変数の組み合わせ（$2^{n}$組）に対し、半分が1、半分が0を出力する関数であることを示し、定数関数はどの入力に対しても出力値が同じ関数であることを示します。

具体的に$n=2$の場合を以下に示します。

• 平衡関数（4つの入力組に対し、2つが1、2つが0を出力する）

  • パターンA：$f(0,0)=0, f(0,1)=0,f(1,0)=1, f(1,1)=1$
  • パターンB：$f(0,0)=0, f(0,1)=1,f(1,0)=1, f(1,1)=0$
  • パターンC：$f(0,0)=0, f(0,1)=1,f(1,0)=0, f(1,1)=1$
  • パターンD：$f(0,0)=1, f(0,1)=1,f(1,0)=0, f(1,1)=0$
  • パターンE：$f(0,0)=1, f(0,1)=0,f(1,0)=1, f(1,1)=0$
  • パターンF：$f(0,0)=1, f(0,1)=0,f(1,0)=0, f(1,1)=1$

• 定数関数（すべて同じ値を出力する）

  • パターンG：$f(0,0)=0, f(0,1)=0,f(1,0)=0, f(1,1)=0$
  • パターンH：$f(0,0)=1, f(0,1)=1,f(1,0)=1, f(1,1)=1$

注意点として、$f(x)$が平衡関数でも、定数関数でもない場合は、ドイチェ・ジョザのアルゴリズムでは扱いません。

例えば、$n=2$の場合、以下のような、出力の半分が1、半分が0でない、かつすべて同じ出力値をとらないパターンは今回考えません

• 平衡関数でも、定数関数でもないパターンの例
  • $f(0,0)=1, f(0,1)=0,f(1,0)=0, f(1,0)=0$
  • $f(0,0)=0, f(0,1)=1,f(1,0)=1, f(1,0)=1$

古典との比較

古典コンピュータでは、この問題を解く際、最良の場合$2$回、最悪の場合$2^{n-1}$回の計算量が必要であるのに対し、量子コンピュータのドイチェ・ジョザのアルゴリズムでは、やはり、1回のみの計算で関数の判定を行うことができます。

古典コンピュータでは、$2^{n}$組の入力の組み合わせに対する出力値（$f(x)$の値）を1組ずつ検証しますが、今回は$f(x)$が平衡関数でも、定数関数でも無い場合は扱わないため、1回目と2回目の検証で、0と1の出力値を1回ずつ得ることができれば、最良で2回で$f(x)$は平衡関数であると判断することができます。
一方で、出力値が$0$or$1$のみの検証が続くと、平衡関数か定数関数かの判断に、最悪の場合、$2^{n-1}$回の検証が必要になります。

アルゴリズムの詳細

利用する回路図¹は以下に示す通りです。

入力は、$f(x)$の引数であるnビットの$\ket{0}$と制御ビットの$\ket{1}$であり、最終的に、上位nビットを測定し、関数の判定を行います。回路の記号の意味は基本的にドイチェのアルゴリズムと同様であり、$H$はアダマールゲート、$U_x$はオラクルを示しています。

書籍や文献によっては、上の回路図を、以下のように、$H^{⊗n}$を用いて、コンパクトにまとめることもあります。

ドイチェ・ジョザのアルゴリズムの大まかな流れも同様に3つにわけることができ、①アダマールゲートに通し、重ね合わせ状態を作る。②オラクルに通す、③再びアダマールゲートに通し、上位ビットを観測するといった順番で、問題を解いていきます。詳細はドイチェのアルゴリズムとほぼ同じであるため、省略します。

サイモンのアルゴリズム

サイモンのアルゴリズムは、1997年にサイモンによって提案された、特定の問題を解くアルゴリズムです。ドイチェ、ドイチェ・ジョザのアルゴリズムと異なる点として、量子アルゴリズムと古典アルゴリズムを併用して、求解を行います。

対象の問題

以下の条件を持つ、関数$f(x)$とnビット列$s$を考えます。

• 入力、出力がそれぞれnビット
• ある入力$x$に対し、出力値が一致する、$x'$が必ず存在する。（つまり、$f(x)=f(x')$）
• 任意の$x$に対して、$x' = s ⊕ x$が成り立つ。（つまり、$f(x)=f(s ⊕ x)$）
• $s≠00...0$ である。

サイモンのアルゴリズムは、$f(x)$が以上のような条件を満たすときの、$s$を求めるという問題を扱います。

少しわかりずらいと思うので、$n=3$ の場合を例に取り、説明します²。
まず、条件「ある入力$x$に対し、出力値が一致する、$x'$が必ず存在する。」についてですが、これは、以下のように、出力が一致する、入力のペアができることを示しています。

$$ f(000)=f(110),　f(001)=f(111),　f(010)=f(100),　f(011)=f(101)$$

また、「任意の$x$に対して、$x' = s ⊕ x$が成り立つ。」という条件は、以下のように、出力が一致する入力のペアの片方と$s$の排他的論理和（$x⊕s$）が、ペアのもう片方（$x'$）と一致することを示しています。
$$ 000 = s ⊕ 110,　001 = s ⊕ 111,　010 = s ⊕ 100,　011 = s ⊕ 101 $$

この時、$s = 110$ ですが、サイモンのアルゴリズムを利用することで、この$110$という値を効率的に求めることができます。

古典との比較

以上で紹介した問題に対し、古典コンピュータでは、最悪$2^{n-1}+1$回の関数の評価を必要とするのに対し、サイモンのアルゴリズムでは、連立方程式を解く段階（後で説明）になれば、$O(n^2)$で解くことができます。

アルゴリズムの詳細

サイモンのアルゴリズムでは、ドイチェ・ジョザのアルゴリズムとは異なり、量子アルゴリズムを利用する部分と古典アルゴリズムを利用する部分が存在します。
それぞれの部分の入力と出力は以下の通りとなっています。

	入力	処理内容	出力(量子の場合は測定値)
量子部分	$\ket{0...0}$ (2nビット)	後述の「利用する量子回路」で説明	$s・x=0$を満たす$\ket{x}=\ket{x_1x_2...x_n}$ （nビット）
古典部分	$s・x=0$を満たす、n-1個の異なる$x$（nビット）	連立方程式を解く。	$s$の値

ここで、$s・x$はドット積と呼ばれており、$x=x_0x_1...x_n$、$s=s_0s_1...s_n$ $(x_k,s_k=\{0,1\})$とすると、以下のように定義されています。
$$s・x=s_0×x_0⊕s_1×x_1⊕...⊕s_n×x_n$$
$×$は乗算、$⊕$は排他的論理和を示しています。
表に示されている通り、サイモンのアルゴリズムは、まず、量子部分では、2nビットの入力から、$s$とドット積が0になるnビット列を取得します。つまり、測定値$\ket{x}=\ket{x_1x_2...x_n}$が、$s・x=0$を満たすように量子回路を組むことが必要となります。
そして、その量子回路を複数回実行し、$s$とのドット積が0となるビット列をn-1個取得することで、n-1個の連立方程式を解くという問題に落とし込み、$s$を求めます。

例えば、$n=5$で、$s= 01011$を求めるという問題[^3]を考えます。
まず、量子回路（後で詳細を説明）をn-1回（4回）以上実行、測定によって、以下のビット列群を取得します。
$$10100,00100,11110,00111$$
これらは、$s$とのドット積が0となるように、量子回路が組まれているため、以下の方程式が成り立ちます。

s_0×1⊕s_1×0⊕s_2×1⊕s_3×0⊕s_4×0=0 　　・・・①\\
s_0×0⊕s_1×0⊕s_2×1⊕s_3×0⊕s_4×0=0 　　・・・②\\
s_0×1⊕s_1×1⊕s_2×1⊕s_3×1⊕s_4×0=0 　　・・・③\\
s_0×0⊕s_1×0⊕s_2×1⊕s_3×1⊕s_4×1=0 　　・・・④

連立方程式を解くと、①より$s_0=s_2$、②より$s_2=0$であるため、以下が成り立ちます。
$$s_0=s_2=0　　・・・⑥$$
また、③、⑥より、$s_1=s_3$、④、⑥より、$s_3=s_4$であるため、$s_1=s_3=s_4$が成り立ちます。
ここで「対象の問題」で述べた条件より、$s≠00000$であるため、$s_1=s_3=s_4=1$となることがわかります。

まとめると、サイモンのアルゴリズムは、量子回路を利用して、$s$とドット積が0になるnビット列を取得し、その後、得られる連立方程式を古典アルゴリズムで解くことで、$s$の値を求めるという流れになっています。

利用する量子回路

以下のような2nビットの入力を持つ回路を利用します²。

なんとなくドイチェ・ジョザのアルゴリズムと似ていますが、制御ビットがnビットあり、また、制御ビットをアダマールゲート$H$を通さない点が違います。

大まかな流れとしては、やはり3つにわけることができ、①上位ビットのみをアダマールゲートに通し、重ね合わせ状態を作る。②オラクルに通す、③再び上位ビットの身をアダマールゲートに通し、測定するといった順番で、問題を解いていきます。

今回は、$n=2$の時を例として、量子回路に沿った、式の変形の流れを説明します²。

①上位ビットのみをアダマールゲートに通し、重ね合わせ状態を作る。

入力のうち、上位ビットの$\ket{00}$のみに対し、アダマールゲート$H$を適用すると、以下のようになります。

H(\ket{00})⊗\ket{00} = \frac{1}{2}(\ket{00} + \ket{01}+\ket{10} +\ket{11})⊗\ket{00}

②オラクルに通す

①で得た重ね合わせ状態を入力として、オラクルを実行すると以下に示すとおりになります。

U_x(\frac{1}{2}(\ket{00} + \ket{01}+\ket{10} +\ket{11})⊗\ket{00})=\frac{1}{2}U_x((\ket{00}⊗\ket{00} + \ket{01}⊗\ket{00}+\ket{10}⊗\ket{00} +\ket{11}⊗\ket{00}))\\
=\frac{1}{2}U_x(\ket{00}⊗\ket{00} )+ U_x(\ket{01}⊗\ket{00})+U_x(\ket{10}⊗\ket{00}) +U_x(\ket{11}⊗\ket{00})\\

ここで、$x_0,x_1=0,1$とすると、$U_x(\ket{x_0x_1}⊗\ket{00})=\ket{x_0x_1}⊗\ket{00⊕f(x_0x_1)}=\ket{x_0x_1}⊗\ket{f(x_0x_1)}$ であるため、以下のように表せます。

\frac{1}{2}U_x(\ket{00}⊗\ket{00} )+ U_x(\ket{01}⊗\ket{00})+U_x(\ket{10}⊗\ket{00}) +U_x(\ket{11}⊗\ket{00})=\\
\frac{1}{2}(\ket{00}⊗\ket{f(00)}+ \ket{01}⊗\ket{f(01)}+\ket{10}⊗\ket{f(10)}+ \ket{11}⊗\ket{f(11)})

③再び上位ビットのみをアダマールゲートに通し、測定する

②で得られた結果に対し、以下のように、上位ビットのみにアダマールゲート $H$を適用します。

\frac{1}{2}(H(\ket{00})⊗\ket{f(00)}+ H(\ket{01})⊗\ket{f(01)}+H(\ket{10})⊗\ket{f(10)}+ H(\ket{11})⊗\ket{f(11)})\\
= \frac{1}{4}(\ket{00} + \ket{01})+\ket{10} +\ket{11})⊗\ket{f(00)}\\
+ \frac{1}{4}(\ket{00} - \ket{01})+\ket{10} -\ket{11})⊗\ket{f(01)}\\
+ \frac{1}{4}(\ket{00} + \ket{01})-\ket{10} -\ket{11})⊗\ket{f(10)}\\
+ \frac{1}{4}(\ket{00} - \ket{01})-\ket{10} +\ket{11})⊗\ket{f(11)}

以上の式を$\ket{00}, \ket{01}, \ket{10}, \ket{11}$ごとにまとめると以下のようになります。

\frac{1}{\sqrt{2}}\ket{00}⊗\frac{1}{\sqrt{2}}(\ket{f(00)} + \ket{f(01)}+\ket{f(10)} +\ket{f(11)})\\
+\frac{1}{\sqrt{2}}\ket{01}⊗\frac{1}{\sqrt{2}}(\ket{f(00)} - \ket{f(01)}+\ket{f(10)}-\ket{f(11)})\\
+\frac{1}{\sqrt{2}}\ket{10}⊗\frac{1}{\sqrt{2}}(\ket{f(00)} + \ket{f(01)}-\ket{f(10)}-\ket{f(11)})\\
+\frac{1}{\sqrt{2}}\ket{11}⊗\frac{1}{\sqrt{2}}(\ket{f(00)} - \ket{f(01)}-\ket{f(10)}+\ket{f(11)})

以上の式の上位ビットがサイモンのアルゴリズムで利用される量子回路の測定値と確率振幅となります。

・・・といっても、さすがにわかりずらいと思うので、具体的に$s$の値を当てはめて説明します²。
例えば、$s=10$とすると、$f(00)=f(10)$かつ$f(01)=f(11)$であるため、いくつかの式変形を経て、以下の式が得られます。

\frac{1}{\sqrt{2}}\ket{00}⊗\frac{1}{\sqrt{2}}(\ket{f(00)} + \ket{f(01)})
+\frac{1}{\sqrt{2}}\ket{01}⊗\frac{1}{\sqrt{2}}(\ket{f(00)} - \ket{f(01)})

上の式の上位ビット（$\frac{1}{\sqrt{2}}\ket{00},\frac{1}{\sqrt{2}}\ket{01}$）に注目すると、1/2の確率で$\ket{00}$、同じく1/2の確率で$\ket{01}$が量子回路で測定されるということがわかると思います。また、00、01ともに、$s=10$とのドット積は0となっています。

あとは、得られた測定値を利用して連立方程式を立てて、古典的アルゴリズムを用いて、$s$を求めるという流れになります。なお、今回の例では、$s・01=0$という$n-1 = 1$個の式から、$s=10$を求めます。

以上が、サイモンのアルゴリズムの大まかな流れの説明となります。

#まとめ
この記事では、以下3つの量子アルゴリズムを紹介しました。

• ドイチェのアルゴリズム
• ドイチェ・ジョザのアルゴリズム
• サイモンのアルゴリズム

いずれも、簡単な問題を扱うアルゴリズムですが、今後アドベントカレンダーでも登場する、より複雑なアルゴリズム（グローバー、ショアなど）を理解する上での足掛かりにしていただければと思います。

もしご指摘等ありましたら、コメントまでお願いします！

参考

• 書籍：みんなの量子コンピュータ（著：Chris Bernhardt、翻訳・監修：湊 雄一郎、中田 真秀）
• 書籍：量子コンピューティング: 基本アルゴリズムから量子機械学習まで（著：情報処理学会 出版委員会 監修、嶋田 義皓 著）
• Youtube：量子コンピュータ授業 #3 ドイチェ・ジョザアルゴリズム（慶應義塾Keio University）

1. overleafで作成しました。また、量子回路の作成については、こちらの記事を参考にしました。 ↩ ↩²

2. 説明の際に用いられる具体例は、書籍：みんなの量子コンピュータから引用しています。 ↩ ↩² ↩³ ↩⁴