サイモンのアルゴリズム

サイモンのアルゴリズムは、サイモン問題として知られる問題に対する量子クエリアルゴリズムです。 これは、ドイチュ・ジョザ問題やバーンスタイン・ヴァジラニ問題に似た性質を持つ約束問題ですが、詳細は異なります。

サイモンのアルゴリズムは、量子アルゴリズムが古典（確率的なものを含む）アルゴリズムに対して指数的な優位性を持つことを示すものとして重要です。また、このアルゴリズムで用いられた技法は、ピーター・ショアによる整数因数分解の効率的な量子アルゴリズムの発見に着想を与えました。

サイモン問題

サイモン問題への入力関数は次の形をとります。

$$f:\Sigma^n \rightarrow \Sigma^m$$

ここで $n$ と $m$ は正の整数です。 簡単のため $m = n$ の場合に限定することもできますが、この仮定から得られるものはほとんどありません。サイモンのアルゴリズムとその解析は、いずれの場合でも基本的に同じです。

サイモン問題

入力: 関数 $f:\Sigma^n \rightarrow \Sigma^m$
約束: すべての $x,y\in\Sigma^n$ に対して $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ を満たす文字列 $s\in\Sigma^n$ が存在する
出力: 文字列 $s$

約束の内容をすぐに詳しく説明しますが、まずはっきりさせておきたいのは、この約束が $f$ に非常に特殊な構造を要求しているという点です。つまり、ほとんどの関数はこの約束を満たしません。 また、この問題は実用的な重要性を意図したものではないことも認識しておくべきでしょう。 むしろ、量子コンピュータにとっては易しく、古典コンピュータにとっては難しいように、人工的に設計された問題です。

主に 2 つのケースがあります。第 1 のケースは $s$ がすべてゼロの文字列 $0^n$ であり、第 2 のケースは $s$ がすべてゼロの文字列ではない場合です。

• ケース 1: $s=0^n.$ $s$ がすべてゼロの文字列であれば、約束の必要十分条件を単純化して $[f(x) = f(y)] \Leftrightarrow [x = y]$ と表せます。 これは $f$ が全単射関数であることと同値です。

• ケース 2: $s\neq 0^n.$ $s$ がすべてゼロの文字列でない場合、この文字列に対して約束が満たされることは、$f$ が2対1であることを意味します。つまり、$f$ のすべての可能な出力文字列に対して、$f$ がその文字列を出力するような入力文字列がちょうど 2 つ存在します。さらに、それらの 2 つの入力文字列はある文字列 $w$ を用いて $w$ と $w \oplus s$ の形をとらなければなりません。

約束が満たされる場合、条件を満たす文字列 $s$ はただ 1 つしか存在し得ないことを認識することが重要です。つまり、約束を満たす関数に対しては常に一意の正しい答えが存在します。

次に、文字列 $s = 011$ に対して約束を満たす $f:\Sigma^3 \rightarrow \Sigma^5$ 形式の関数の例を示します。

$$\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}$$

入力文字列は $8$ 種類あり、出力文字列は $4$ 種類で、それぞれ 2 回ずつ現れます。つまりこれは 2 対 1 の関数です。 さらに、同じ出力文字列を生成する 2 つの異なる入力文字列の任意の組み合わせについて、それらのビット単位の XOR が $011$ に等しいことが確認できます。これは一方が他方と $s$ の XOR に等しいことと同値です。

実際の出力文字列について重要なのは、異なる入力文字列の選択に対して同じかどうかという点だけであることに注目してください。 例えば上の例では、$f$ の出力として $(10011,$ $00101,$ $00001,$ $11010)$ の 4 つの文字列が現れます。これらの 4 つの文字列をすべて異なる別の文字列に置き換えても、正しい解 $s = 011$ は変わりません。

アルゴリズムの説明

サイモンのアルゴリズムを表す量子回路図を以下に示します。

上部の $n$ 個の量子ビットがアダマールゲートによって操作され、下部の $m$ 個の量子ビットはクエリゲートに直接入力されます。 このレッスンでこれまで説明したアルゴリズムと非常によく似ていますが、今回は位相キックバックがありません。下部の $m$ 個の量子ビットはすべて $\vert 0\rangle$ の状態でクエリゲートに入力されます。

この回路を使ってサイモン問題を解くには、実際には回路を複数回独立して実行し、その後に古典的な後処理ステップを行う必要があります。後処理については、回路の動作を解析した後に説明します。

解析

サイモンのアルゴリズムの解析は、ドイチュ・ジョザアルゴリズムと同様の手順で始まります。 上部の $n$ 個の量子ビットに対して最初のアダマールゲートの層が実行されると、状態は次のようになります。

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.$$

$U_f$ が実行されると、関数 $f$ の出力が下部の $m$ 個の量子ビットのすべてゼロの状態に XOR として書き込まれ、状態は次のようになります。

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.$$

2 番目のアダマールゲートの層が実行されると、以前と同じアダマールゲートの層の作用の式を使って次の状態が得られます。

$$\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle$$

この時点で、解析はこのレッスンの前のアルゴリズムとは異なる方向へ進みます。

ここでの関心は、測定によって各可能な文字列 $y\in\Sigma^n$ が得られる確率です。 量子情報の基礎コースの複数系のレッスンで説明した測定の解析規則を用いると、文字列 $y$ が得られる確率 $p(y)$ は次のように表されることがわかります。

$$p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.$$

これらの確率をより詳しく把握するために、若干の記法と用語が必要です。 まず、関数 $f$ の値域はすべての出力文字列を含む集合です。

$$\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}$$

次に、各文字列 $z\in\operatorname{range}(f)$ に対して、関数がこの出力文字列 $z$ に評価されるすべての入力文字列の集合を $f^{-1}(\{z\})$ と表します。

$$f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}$$

集合 $f^{-1}(\{z\})$ は $f$ による $\{z\}$ の逆像として知られています。 同様の方法で、$\{z\}$ の代わりに任意の集合に対する $f$ による逆像を定義できます。これは $f$ がその集合に写像するすべての元の集合です。 （この記法は関数 $f$ の逆関数と混同しないでください。逆関数は存在しない場合があります。 左辺の引数が元 $z$ ではなく集合 $\{z\}$ であることが、この混同を避けるための手がかりです。）

この記法を用いて、上記の確率の式における和を分割すると次のようになります。

$$p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.$$

$x\in\Sigma^n$ のすべての文字列は 2 つの和によってちょうど 1 回ずつ表されます。基本的には、関数 $f$ を評価したときに生成される出力文字列 $z = f(x)$ に応じてこれらの文字列を別々のバケツに分け、すべてのバケツに対して別々に和をとっているだけです。

ユークリッドノルムの 2 乗を評価すると次のようになります。

$$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.$$

これらの確率をさらに簡略化するために、次の値を見てみましょう。

$$\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}$$

これは任意の $z\in\operatorname{range}(f)$ の選択に対するものです。

$s = 0^n$ の場合、$f$ は全単射関数であり、すべての $z\in\operatorname{range}(f)$ に対して $f^{-1}(\{z\})$ の元はただ 1 つだけです。 この場合、式 $(1)$ の値は $1$ です。

一方、$s\neq 0^n$ の場合、集合 $f^{-1}(\{z\})$ にはちょうど 2 つの文字列があります。 具体的に言えば、$w\in f^{-1}(\{z\})$ をこれら 2 つの文字列のうち任意の 1 つとすると、もう 1 つの文字列はサイモン問題の約束によって $w \oplus s$ でなければなりません。 この観察を用いると、$(1)$ を次のように簡略化できます。

$$\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}$$

したがって、値 $(1)$ は両方のケースにおいて $z\in\operatorname{range}(f)$ の具体的な選択に依存しないことがわかります。

前と同じ 2 つのケースを個別に見ることで、解析を完結させることができます。

• ケース 1: $s = 0^n.$ この場合、関数 $f$ は全単射なので $z\in\operatorname{range}(f)$ の文字列は $2^n$ 個あり、次のようになります。

  $$p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.$$

  つまり、測定の結果として $y\in\Sigma^n$ の文字列が一様ランダムに選ばれます。

• ケース 2: $s \neq 0^n.$ この場合、$f$ は 2 対 1 なので $\operatorname{range}(f)$ の元の数は $2^{n-1}$ です。 上の式を用いると、各 $y\in\Sigma^n$ を測定する確率は次のようになります。

  $$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}$$

  つまり、$2^{n-1}$ 個の文字列を含む集合 $\{y\in\Sigma^n : y \cdot s = 0\}$ から一様ランダムに選ばれた文字列が得られます。（$s\neq 0^n$ なので、長さ $n$ の 2 進文字列のうちちょうど半分が $s$ との 2 進内積が $1$ になり、残り半分が $0$ になります。これはドイチュ・ジョザアルゴリズムのバーンスタイン・ヴァジラニ問題の解析ですでに観察したことです。）

古典的な後処理

サイモンのアルゴリズムの量子回路を実行したときの可能な測定結果の確率がわかりました。 これは $s$ を決定するのに十分な情報でしょうか？

答えはイエスです。ただし、プロセスを数回繰り返し、回路を十分な回数実行することで非常に小さくできるある確率での失敗を許容する必要があります。 基本的なアイデアは、回路を 1 回実行するたびに $s$ に関する統計的な証拠が得られ、十分な回数回路を実行すれば非常に高い確率で $s$ を見つけるためにその証拠を活用できるというものです。

回路を $k = n + 10$ として $k$ 回独立して実行するとします。 この反復回数に特別な意味はなく、後述するように許容する失敗確率に応じて $k$ を大きく（または小さく）することができます。 $k = n + 10$ を選ぶと、$s$ を回復できる確率が $99.9$% を超えることが保証されます。

回路を $k$ 回実行することで、文字列 $y^1,...,y^{k} \in \Sigma^n$ が得られます。 ここで上付き文字はこれらの文字列の名前の一部であり、指数やビットへのインデックスではないことに注意してください。したがって次のようになります。

$$\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}$$

次に、これらの文字列のビットを 2 値の要素として使い、$k$ 行 $n$ 列の行列 $M$ を形成します。

$$M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}$$

この時点では $s$ が何であるかはわかっていません。この文字列を見つけることが目標です。 しかし、仮に文字列 $s$ を知っているとして、$s = s_{n-1} \cdots s_0$ のビットから次のように列ベクトル $v$ を形成します。

$$v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}$$

行列-ベクトル積 $M v$ を $2$ を法として計算すると（つまり通常の乗算を行い、その後結果の各要素を $2$ で割った余りをとる）、すべてゼロのベクトルが得られます。

$$M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}$$

つまり、文字列 $s$ は、上述のような列ベクトル $v$ として扱うと、$2$ を法とした演算のもとで行列 $M$ の零空間の元になります。 これは $s = 0^n$ の場合も $s\neq 0^n$ の場合も成り立ちます。 より正確に言えば、すべてゼロのベクトルは常に $M$ の零空間に含まれており、$s\neq 0^n$ の場合には $s$ のビットを要素とするベクトルも零空間に加わります。

残る問題は、$0^n$ と $s$ に対応するベクトル以外に $M$ の零空間に他のベクトルが含まれるかどうかです。 $k$ が増えるにつれてその可能性はますます低くなります。$k = n + 10$ を選べば、$99.9$% を超える確率で $M$ の零空間には $0^n$ と $s$ に対応するベクトル以外が含まれないでしょう。 より一般的には、$k = n + 10$ を $k = n + r$（任意の正整数 $r$ の選択）に置き換えると、$0^n$ と $s$ に対応するベクトルだけが $M$ の零空間に含まれる確率は少なくとも $1 - 2^{-r}$ です。

線形代数を用いると、$2$ を法とした $M$ の零空間の記述を効率的に計算することが可能です。 具体的には、ガウス消去法を使って行うことができます。この方法は、$2$ を法として演算を行う場合でも、実数や複素数と同じように機能します。 $0^n$ と $s$ に対応するベクトルだけが $M$ の零空間に含まれる場合（これは高い確率で起こります）、この計算の結果から $s$ を導き出すことができます。

古典的な困難さ

古典的なクエリアルゴリズムがサイモン問題を解くには何回のクエリが必要でしょうか？ 答えは、一般的にはたくさんです。

この問題の古典的な困難さについてはさまざまな正確な言明が可能ですが、ここではその 1 つを示します。 任意の確率的クエリアルゴリズムが $n$ に対して指数的な回数である $2^{n/2 - 1} - 1$ 回未満のクエリしか行わない場合、そのアルゴリズムは少なくとも $1/2$ の確率でサイモン問題の解法に失敗します。

このような不可能性の結果を証明することは非常に難しい場合がありますが、これは初等的な確率論的解析によって比較的難しくなく証明できます。 ただしここでは、その背後にある基本的な直感を簡単に検討するだけにとどめます。

目的は隠れた文字列 $s$ を見つけることですが、同じ出力値を持つ 2 つの文字列に対してクエリを行わない限り、$s$ についての情報はほとんど得られません。 直感的に言えば、わかることは隠れた文字列 $s$ がクエリした 2 つの異なる文字列の排他的論理和ではないということだけです。 そして $2^{n/2 - 1} - 1$ 回未満の文字列にクエリした場合、ペアの数が足りないため、まだ除外されていない $s$ の選択肢がたくさん残ります。 これは形式的な証明ではなく、基本的なアイデアに過ぎません。

つまり、まとめると、サイモンのアルゴリズムはクエリモデルにおいて量子アルゴリズムが古典アルゴリズムに対して顕著な優位性を持つことを示しています。 特に、サイモンのアルゴリズムは関数の入力ビット数 $n$ に対して線形な回数のクエリでサイモン問題を解きます。一方、古典アルゴリズムは確率的なものであっても、合理的な成功確率でサイモン問題を解くためには $n$ に対して指数的な回数のクエリが必要です。