猫でもわかる量子情報（２２）

函数おみくじ（オラクル）

　こうして古典的な回路と少なくとも同等なことが「可逆性」という制限をおいた量子素子から作った量子回路でもできることが示されましたが、これだけだとやはりもの足りませんよね。通常の力学よりずっと難しい量子力学なんだから、通常の計算よりずっと優れた事が何かできるので無いととっても割にあわない気がします。量子状態はベクトルで、量子演算は行列の積なのですから、なにかこれをうまく使うと計算効率が上げられないでしょうか。
　そのためにはまず、また一つ風変わりな「オラクル」という概念を導入します。
　いや、その前にまず「計算」という作業を少し違った風に考えてみます。ある入力を与えてある規則に従ってある出力が出てくるのが計算ですが、これを今、数 x から函数 f(x) を得る作業だと表現してみます。x も f(x) も整数値だけをとるものに制限すれば、可能な函数の形も有限個のに制限されます。いま極端な例を考えて、函数の出力としては１ビット、すなわち０か１しかないものだけを考察してみます。 x のほうは n ビットの数で、０、１、２、... 、２^n 個の値がとれるとします。N = ２^n という表示も使う事にします。例えば n = 1 なら N = 2 となって、可能な函数を書き出してみると

　　　場合A : f(0) = 0, f(1) = 0、　場合B : f(0) = 0, f(1) = 1、
　　　場合C : f(0) = 1, f(1) = 0、　場合D : f(0) = 1, f(1) = 1

の４つの型ですべての場合が尽くされることがわかります。このように可能性が有限なので、函数を計算するという事を「函数がA 、B、C、Dのうちのどれなのか決める」という事だと言い直してもいいですよね。いま４つの場合に相当する「数を食って数を吐き出す装置」A、B、C、Dの４種類そろえておくとします。いま装置をどれかとってきて０と１を食わせて２回動かして結果を見ればその装置の性質がわかり、それがどれだったかわかる訳です。こういう装置のことを「オラクル」つまり「神託」と呼ぶ事になっていますが、「おみくじ」って思えばいいでしょう。たとえば

　　　　　　「函数 f がA、B、C、Dのどれか１つだとして、
　　　　　　それから z= f(0) .xor. f(1) という量を計算する」

というのはこの言い方でいうと

　　「f のオラクル（A、B、C、Dのどれか）を持ち出して０と１を入れ
　　総計２回動作させて、出てきた２つの数の .xor. 操作をしてみる」

となります。これだけだとなんだか、面倒な言い換えごっこのようです。オラクルを２回動かさないと結果がでないのは、f(0)とf(1)両方計算しなきゃならないので当然ですよね。でもこういう主張をしたらどうでしょう？
　　「A、B、C、Dの量子的オラクルをつくって取り揃えておけば、どの場合でも、一回だけの操作で z= f(0) .xor. f(1) という量が計算できる。」
実はそんな事がほんとうにできるのです。
　少し興味がわきましたか？