Shorのアルゴリズムの秘密

 【 Shorのアルゴリズムの秘密 】　

かつて暗号の世界を震撼させたShorのアルゴリズムには秘密があった。それは、隠しておきたい秘密ではない。なぜ、それがそんなにも速いのかという秘密である。　

Shorのアルゴリズムでは、普通のコンピューターがn個の計算をするときに、量子コンピューターは2^n個の計算をする。普通のコンピューターが10歩進めば、量子コンピューターは、1,024歩も進むのだ。こうした「指数関数的高速化」がなぜ可能かという秘密である。

「そもそも、量子コンピューターには 2^n個の計算をパラレルに実行する能力がある」と考えている人も多いと思うのだが、それは微妙な間違いだ。

確かに「量子の世界」では、そうした計算は可能である。ただ、その計算結果を量子コンピューターは、2^n個の計算結果の量子状態の「重ね合わせ」として返すのだ。

その計算結果を「現実の世界」に取り出そうとすると（それを量子状態の「観測」という）、2^n個の量子状態の「重ね合わせ」は一瞬にして消え去り、一個の状態だけが観測されることになる。

目の前には、といっても「量子の世界」のことだが、2^n個の計算結果があるのに、それがうまくは取り出せないのだ。

「観測することで、量子コンピューターの2^n倍の計算能力が消えてしまうのなら、観測なんてやめればいいだろう。」

それも実は一理はある。「量子の世界」は、我々人間の観測とは無関係に存在し、運動しているのだから。それはそうなのだが、それは量子コンピューターを走らせても、計算結果を求めないということになる。それでは量子コンピューターの意味がない。

それでは、Shorのアルゴリズムでは、なぜ、2^n倍の高速化を実現できるのだろうか？

まず、Shorのアルゴリズムでは、2^n個の量子状態の「重ね合わせ」を観測しようとしないのだ。

2^n個の量子状態の「重ね合わせ」を生み出す計算は、副作用として、量子の「位相 phase」を微妙に変化させる。これをphase kickbackと言う。Shorのアルゴリズムでは、この位相の変化に注目する。

驚くべきことに、この位相の変化の評価から、2^n個の情報が復元できるのである。フーリエ変換を使う。それは、結果的には、2^n倍の高速化を実現したことになる。

目の前にあるのに使えない、使おうとすると使えなくなるという禅問答のような袋小路を、位相に注目するという回り道で突破したのが、Shorである。

Shorのアルゴリズムの秘密は、まず、ここにあるのである。