量子計算学習ノート - 計算問題の解析1

---

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。

---

ここからは計算機によって計算される問題自体についての考察を深める。まず、計算問題についての私たちの基本的疑問は次の3つである。

1. 計算問題とはいったいどんな問題か？

2. 与えられた計算問題を解くためのアルゴリズムをうまく設計する方法は？

3. 与えられた計算問題を解くために必要最小限なリソースは何か？

ここから数回は1と3について、3から1の順番で議論していくことにする。2については実際に量子アルゴリズムを構成するうえでも精通しておくべき話題であるが、すでに議論されている研究が膨大にあるので、実際に量子アルゴリズム設計をする際に焦点を絞って議論することにする。

3について、計算問題においてリソースといっても様々なリソースを利用しているが、私たちは「時間・空間・エネルギー」にその焦点を絞ることにする。特に最初は時間と空間について議論しよう。

さて、計算問題を解く計算モデル同士の違いと、その違いにほぼ関与しない無関係なリソース要求について定量化を行いたい。そのために私たちは「漸近表示」というもの用いる。

まず記号$${O}$$を関数の振る舞いの上界を設定するのに用いる。具体的には二つの関数$${f(n), g(n)\ (n \in \mathbb{N})}$$に対し、ある$${n_0 \in {\mathbb{N}, c \gt 0}}$$が存在して

$$
n \gt n_0 \Rightarrow f(n) \le cg(n)
$$

が成立するとき、「関数$${f(n)}$$はクラス$${O(g(n))}$$の関数である」という。これはつまり「十分大きな$${n}$$に対して$${f(n)}$$は、$${n}$$の増減によって変化しないという意味で重要でない定数因子$${c}$$を除き、関数$${g(n)}$$で押さえられる」ということを意味する。
$${O}$$記法は特定のアルゴリズムの最悪ケースの振る舞いを調べるのに便利である。

同様に関数の振る舞いの下界を設定することも重要だ。これは$${\Omega}$$記法によって定義される。つまり二つの関数$${f(n), g(n)\ (n \in \mathbb{N})}$$に対し、ある$${n_0 \in {\mathbb{N}, c \gt 0}}$$が存在して

$$
n \gt n_0 \Rightarrow f(n) \ge cg(n)
$$

が成立するとき、「関数$${f(n)}$$はクラス$${\Omega(g(n))}$$の関数である」という。$${\Omega}$$記法は特定のアルゴリズムの最良ケースの振る舞いを調べるのに便利である。

関数の振る舞いが$${n}$$の増減によって変化しないという意味で重要でない定数因子を除き、同じであることは$${\Theta}$$記法によって定義されることになる。つまり$${f(n)}$$がクラス$${O(g(n))}$$かつ$${\Omega(g(n))}$$の関数であるとき、「関数$${f(n)}$$はクラス$${\Theta(g(n))}$$の関数である」という。

次回はこの$${O, \Omega, \Theta}$$記法の性質についてみていくことにする。