(定義)広義量子超越性(仮) - 竜太のテクニカルメモ

どーも，竜太です．

今回はぼくが考案した『広義量子超越性』という概念についてご紹介します．その前に，まず，従来の『量子超越性』について見てみましょう．

(狭義)量子超越性

あるアルゴリズムを考えるとき一般にある自然数 $k$ があって，与えられた十分大きなデータ $n$ に対し，その計算ステップ数 $S(n)$ が $S(n) \lt O(n^k)$ とできるとき，多項式時間で解けるアルゴリズムといい，多項式時間で解けないアルゴリズムを超多項式時間かかるアルゴリズムと呼びます．

従来の狭義の意味での量子超越性はチューリングマシンで超多項式時間かかる問題を量子力学の性質を使って多項式時間で解ける場合，『量子超越性』がある問題，と定義していました．ここで注意すべきは例えば並び替えの問題のように同じ仕事をさせる場合でも大きなステップ数が必要なアルゴリズムもあれば，小さなステップ数のアルゴリズムもあるので比較する際には知られているチューリングマシンで計算できるもっとも小さなステップ数のアルゴリズムと比較する必要があることです．例えば，量子計算を使用した素因数分解をするショアのアルゴリズムは $O(n^3)$ の計算量のオーダーであるのに対し，知られているチューリングマシンで計算できる最良の素因数分解のアルゴリズムは $2^{O(n^{1/3})}$ のオーダーの計算量のため量子超越性があると呼ばれています．このように従来の量子超越性は主にチューリングマシンで多項式時間に解けない問題が量子力学を用いて多項式時間で解けるとき量子超越性があると呼んでいました．しかし，実際には多項式時間で解けるアルゴリズム同士の計算量の比較や多項式時間で解けないアルゴリズム同士の計算量の比較などさまざまです．これらの場合に，従来の量子超越性という単語を用いてよいのかどうかがはっきりしませんでした．

そこで僕は広義の量子超越性という概念を定式化することにしました．

広義量子超越性

ある問題のチューリングマシンでの最良の計算量のアルゴリズムの計算量を $f(n)$ のオーダーとし，同じ問題の量子アルゴリズムの計算量を $g(n)$ のオーダーとするとき，この問題が量子超越性を持つとは $\frac{f(n)}{g(n)}$ が $o(1)$ のオーダー，つまり， $1$ より大きなオーダーを持つ場合を言いいます．例えば，素因数分解の問題では $f(n)\sim n^3,g(n)\sim 2^{n^{1/3}}$ より $O\left(\frac{f(n)}{g(n)}\right) > O(1)$ より，広義の量子超越性も持っていることが分かります．

広義量子超越性から広義計算量超越性へ

突然ですが $n$ 本の長さの違う(ゆでる前の)スパゲッティーの束を長い順に並べることを考えましょう．これは実質上， $n$ 個の数値を降順にソーティングすることに相当します．チューリングマシンで動かせる比較ソートの場合オーダーは平均的には $O(n\log n)$ になります．しかしスパゲッティーの束を縦にまとめてトン，と一回平らなところで均して一番長いスパゲッティーを1本抜き出す操作を1ステップとすると，僅か $n-1$ ステップ数でスパゲッティの束を降順に並べることができることが分かります．つまりオーダーは $n$ しかありません．

こうして考えてみると広義量子超越性はなにも量子力学に限った話ではないことが分かります．そこで一般に次のように定義しましょう：

広義計算量超越性

あるチューリングマシンで計算できる問題 $Q(n)$ が与えられたとき，チューリングマシンで動かせる最良のアルゴリズム $AL(n)$ の計算量を $f(n)$ のオーダーとし，別の方法で動かせるアルゴリズム $QAL(n)$ の計算量を $g(n)$ のオーダーとするとき， $O\left(\frac{f(n)}{g(n)}\right) > O(1)$ のとき $QAL(n)$ は広義計算量超越性があるアルゴリズムであるといい，問題 $Q(n)$ は広義計算量超越性があると呼ぶ．

広義計算量超越性があり通常の超越性がない問題の例

実はあみだくじを1ステップで解く光学回路の例がこれに相当します．任意の置換を互換の積に分解するにはオーダーにして $O(n\log n)$ が必要ですから，これは立派な広義計算量超越性があることになります．

広義計算量超越性は何の役に立つか？

人間は難しい問題に直面したとき，とりあえず名前を付けることでより扱いやすくしてきました．例えば「こころ」に対して「こころ」と名前を付けずに議論することは大変困難です．広義計算量超越性という名前ができたことで，量子力学によらず，一般の問題に対して計算量の比較が容易になることでしょう．これは計算量の問題が扱いやすくなることを意味します．

ここまで読んでくださって有難うございます．何か間違い等ございましたら，ご報告いただけると幸いです^^

物理学ランキング