はじめに
近年は量子コンピュータがアカデミックな研究の世界だけでなく、各テクノロジー企業にて実用化を目指した研究・開発が行われるようになってきました。企業がこの分野に本格的に参入するということは、発展の余地と開発コストの間で十分なメリットがあると判断したからであると考えられます。
さて、そのような考えで量子コンピュータを考えてみると、「やっぱり量子コンピュータはすごいんだ」、「従来のコンピュータよりも圧倒的に高性能なんだ」と思いたくなります。私自身、全くこの分野には無知だったのですが、ついつい興味が湧き出てきたところです。
そこで、量子コンピュータが従来のコンピュータを計算量の観点から少しまとめてみたいと思います。
計算量理論
概要
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。（wikipediaより）
簡単に言えば、計算量理論ではとある問題（とその解法であるアルゴリズム）がどれほどのリソース（時間・メモリ）を要するのかを論じるということです。
例えば、「あるアルゴリズムへの入力データの長さを増やしたとき、実行時間や必要な記憶量はどのように増えるか？」という問いに答えます。近年は計算機の性能は向上してきていますが、それに負けず劣らず解析すべきデータも増加しているため、アルゴリズムが入力データ長の増大にうまく対応できるか否かは極めて関心の深いテーマです。
また、問題Aと問題Bではどちらの方が複雑であるか（解くのに時間がかかるか）などの関係性を示すなどの役割も担っています。問題の難しさをしっかり分類しておくことができれば、計算機を用いて実際に問題をどれくらいのリソースで解くことができるのかを把握できるため、これも重要なテーマです。
問題の難しさ
問題の難しさは、以下の観点によって評価されます。
- 時間計算量（入力データの長さが増えたときに、解くのに掛かる時間がどのように変化するか）
- 空間計算量（解くのにどれくらいメモリを要するか）
これら２つをまとめて計算量と言いますが、どちらか一方のことを指して使うこともあるので、それは文脈で判断しなければなりません。
問題の難しさを分類するときには、例えば「スカラーの足し算とスカラーの割り算はどちらが難しいですか」など細かく分けていったら切りがありません。また、「スカラーの足し算と行列積」はどちらが難しいですかということも（後者の方が難しそうだが）、区別すべきか否かは考えものです。
計算機を使って問題を解くという事を考える上では、複雑性クラスなるものを導入し、ある個別の問題は何らかの複雑性クラスに属させることにしておき、クラス間の相互関係を示すことで計算問題の難しさを論じていきます。
判定問題（決定問題）
先程は行列積だとか割り算だとかの、よくある数学の計算の話を出しましたが、計算量理論で扱われる最もメジャーな問題はこれから述べる「判定問題」と呼ばれるものです。判定問題とは簡単に言えば「YesかNo」で答えられる問題、すなわち何らかの入力を受け取ったときに計算機が「1か0」を出力するような問題を言います。
これだけを聞くと、「なんだ、そんなことを明らかにしたところで普段の計算について論じることはできないじゃないか」と思うかもしれません。しかし実際には、多くの問題は判定問題に焼き直すことが可能であることが分かっているため、計算量理論では判定問題に関する難しさを論じるのがスタンダードとなっています。
以下、判定問題のみを扱うことにすれば、計算機としては入力はビット列$x\in \{0,1\}^*$で、出力は1ビット$y\in \{0,1\}$となるようなものを扱えば良いことになります。計算機が$1$を出力することを「受理（accept）」と呼び、$0$を出力することを「拒否（reject）」と呼びます。
問題そのものは、すべてのビット列の集合の部分集合によって記述することができます。この言い方は極めて抽象的なので具体例を書いてみましょう。例えば、$x$は$2$で割り切れるか否かという問題に関しては以下のように表現します。まず、$L$（$L$は「言語」と言う）というものを考えます。
$$ L = \{0, 2, 4, 6, 8, 10... \}_{10} = \{0, 10, 100, 110, 1000, 1010,...\}_{2} $$
これは単に、問題の答えの要素（偶数）をすべて含んだ集合を、2進数で表しているだけです（つまりすべてのビットの集合の中で、2の倍数となっている2進数のみを取り出した集合）。このように言語$L$を書いておくと、問題というのは特定の適当なビット列（例えば$x=\{101\}$）が$L$に含まれているか（$x\in L$であるか）を確認するものとして書くことができます。
一般の言語$L$に関して（これがどのような問題に関する話かはとりあえず置いておくとして）、とある計算機（あるいは計算モデル）が、入力ビット列$x$に対して出力ビット$y$を
$$ \begin{align} y &= 1 (x \in L) \\ y &= 0 (x \notin L) \end{align} $$
としてくれるのであれば、上手く問題が解けていると言えます。
計算量クラス
さて、判定問題を分類することで、さまざまな計算量クラスというものを考えることができます。 先程までで説明した通り、判定問題というのは「Yes, No」に答える問題でした。 言語$L$というのは、問題の答えとなるビット列をすべて格納した集合であったので、$x\in L$ならばこれを受理し、$x \notin L$ならばこれを拒否することで、問題を正しく解いたことになります。ここで重要なのは、正しく判定することがどれくらいの計算量で実施できるかという点です。
まずは最も基本的と思われるPというクラスについて説明します。
P
ある言語$L$が$P$に属するというのは、多項式時間決定的チューリングマシンによって $$ \begin{align} x \in L &\to y = 1 \\ x\notin L &\to y = 0 \end{align} $$ となる場合を指します。
ここで多項式時間というのは入力ビット列$x$の長さ$|x|$の多項式で表せるような時間のことです。例えば$|x|^2$に比例する程度であるとかの場合は、長さが4倍に増えたときには計算時間は16倍掛かりそうだと言えます。これはすごく時間が掛かる！！と思うかもしれないですが、実は計算機にとっては多項式時間程度ならば大した問題にはならないケースが多いです。
そして、決定的チューリングマシンというのは概ね私達が普通に使っているコンピュータのことを考えれば良いです。すなわち、普通のコンピュータを使えば多項式時間で完全に正しく解けてしまうような判定問題が$P$クラスであり、「簡単に解ける問題」くらいのイメージで良いでしょう。
BPP
ある言語$L$が$BPP$に属するというのは、多項式時間確率的チューリングマシンによって $$ \begin{align} x \in L &\to p(y = 1) \geq \frac{2}{3} \\ x\notin L &\to p(y = 1) \leq \frac{1}{3} \end{align} $$ となる場合を指します。
まず多項式時間は先ほど説明したとおりです。確率的チューリングマシンというのは、例えばモンテカルロ法のように確率的に動作が変わるような計算手法を想像していただけると良いと思います。このような計算モデルでは、判定問題を正しく受理・拒否できるとは限らなくなりますが、願わくばなるべく高い確率で正しく受理と拒否を行って欲しいところです。
そこで、$x\in L$（すなわち入力$x$は実際に正しい答え）であるとき、それが正しい答えであると判定する確率$p(y=1)$が$2/3$以上であり、かつ$x\notin L$（すなわち入力$x$は問題の解ではない）であるときに、それが正しい答えであると誤認してしまう確率$p(y=0)$が$1/3$以下である場合を、まあそこそこ上手く行く、と考え、BPPクラスと名付けています。
ちなみに、「え、その程度の確率でいいの！！？結構間違った判定しちゃうんじゃ！？」と思うところでしょう。私もそう思います。 しかし、$x$に対して判定を1回しかしなかった場合には、確かに間違ってしまっているかもしれませんが、1つの入力に対して判定を100回くらいしてやれば、70回くらいは受理するかもしれません。そしたら最終的にこれを受理としてやれば良いでしょう。要するにたくさんの判定を行って多数決を取るということです。仮に100回実行して55回受理ならば、最終的に受理としてしまうことにします。
100回くらいじゃ信用ならんというのであればもっとたくさん実行すればいいです。1回1回の判定はたかだか多項式時間で終わるのですから、多項式回数計算を実行したところで多項式時間に収まります。
そして、これは判定回数を増やせば増やすほど、結果として正しく判定できる確率はどんどん高まっていきます。具体的には判定回数を表す多項式を$r$として
$$ \begin{align} x \in L &\to p(y = 1) \geq 1-\frac{1}{2^r} \\ x\notin L &\to p(y = 1) \leq \frac{1}{2^r} \end{align} $$
とできます。要するに増やせば増やすほど限りなく正しい判定結果に近づいていくということです。
NP
ある言語$L$が$NP$に属するというのは、多項式時間確率的チューリングマシンによって $$ \begin{align} x \in L &\to p(y = 1) > 0 \\ x\notin L &\to p(y = 1) = 0 \end{align} $$ となる場合を指します。
これはBPPで説明した、判定をたくさん行って多数決を取ればいいという考えを使えば、それなりに有用なクラスです。 もしも入力ビット列$x$が問題の答えでなければ、絶対に判定結果は$0$になります。しかし、$x$が問題の答えならば、判定結果はほんの小さな確率にすぎないかもしれないが、$1$となる場合もあるということです。すなわち1000000回くらい判定を繰り返してみて、1回でも$1$が出たならば、最終的に受理をするということで正しく問題を解くことができます。
しかし、こちらは$BPP$とは違って正しい判定結果になる確率を都合よく増やすことは出来ません。
量子コンピュータの優位性
非決定性チューリングマシン
さて、ここまでいろいろな複雑性クラスを概観してきました。 ここで一旦「非決定性チューリングマシン」なるものを考えてみましょう。これは確率的チューリングマシンに似ていますが、少し概念が違います。非決定性チューリングマシンでは確率的に計算が分岐していくのではなく、すべての分岐を同時並行的に試すようなものをイメージすると良いでしょう。
確率的チューリングマシンでは、受理するか否かが確率でしか記述できなかったのですが、それは判定の際の計算を実際に確率的に分岐させてとある1つの結果しか見ないからです。そこで、何度も確率的チューリングマシンを使って判定を行って多数決を取ると良いよという話がBPPのところで出ました。
一方で非決定性チューリングマシンは、いろいろな分岐をすべて同時並行的に調べ尽くしてしまうようなものをイメージしていただけると良いでしょう。これは確率的チューリングマシンによって受理が$\frac{11}{16}$で起こるような問題を、非決定性チューリングマシンで判定してみると、（例えば）16個の分岐のうち11個が受理という結果に辿りつき5個の分岐が拒否という結果に辿りつくということになります。
極めて大雑把に行ってしまえば、確率的チューリングマシンが繰り返し判定を行うような様を、1回の判定で（すべての分岐を同時に網羅することで）表してしまうようなものが非決定的チューリングマシンというわけです。
この非決定性チューリングマシンを使うと、$NP$について以下のように記述し直せます。
$$ \begin{align} x \in L &\to 受理する分岐が少なくとも1つ存在 \\ x\notin L &\to 受理する分岐が存在しない \end{align} $$
量子計算
さて、今までは電圧の有無をビット$\{0,1\}$で表し、ビット列を使って構築していたコンピュータの計算（プログラム）を、量子ビットに置き換えたものが量子コンピュータです。通常の古典的ビット列の操作はいろいろな論理ゲートを用いて行えるので、それになぞらえて、量子ビットの操作を行う処理を量子ゲートと表現します。
量子ビットというのは、古典ビットとは異なり、$\{0,1\}$のいずれか一方の値を取るのではなく、同時に両方の値を有します。ということは古典ビットを使った確率的チューリングマシンでの判定を複数回行うような処理は、非決定性チューリングマシンでの（たった1回の）判定に置き換えてしまえ（物理的に実行可能かはともかくとして）、更に量子コンピュータであれば理屈上その計算が実行できてしまえそうである。
というのが思いあたる期待です。しかし、実際にはそれはどうも困難らしいことが分かっており、分岐させた計算パスの結果である量子ビットを正しく観測するためのうまい方法が見つかっていません（すなわち内部的には計算は行われているとしても、それを実際に取り出すことが現状不可能に見えるようです）。
量子計算機特有の複雑性クラス：BQP
上記のような理想的サクセスストーリーが上手く行かなかったとしても、量子計算機の可能性を捨てるにはまだ早いです。 量子計算機で解けるような複雑性クラスを考え、それが古典計算機の複雑性クラスよりも大きな範囲をカバーできるとなれば、それは量子計算機が古典計算機よりも上手く計算をこなせる問題を多く含んでいるということになります。
複雑性クラスとしてBQPというものがあります。この$BQP$は$BPP$を含んでおり（$BPP \subseteq BQP$であることが知られており）、今のところこれらが全く等価なものであるということは証明されていません。仮に$BPP \supseteq BQP$が証明された暁には、このクラスの問題に関しては量子計算機の古典計算機に対する優位性は完全に失われることになります。
要するに古典計算機の優位性を信じるというのは、ある側面では$BPP \neq BQP$であると信じるということなります。ではこの関係性が示せているかというと、実はそうでもないのです。$BPP$の問題はすべて$BQP$に含まれていることがわかっているだけで、$BQP$の問題が$BPP$でないようなケースがあるのかはまだ分かっていません。ということは、今のところ$BQP$の問題に関しては古典的非決定性チューリングマシンで多項式時間で解けてしまうのです。
更に実は古典計算量理論の世界で、 $$ P \subseteq BPP \subseteq PSPACE $$ という関係性が既に知られており、$BQP \subseteq PSPACE$であることも知られているため、全体としては $$ P \subseteq BPP \subseteq BQP \subseteq PSPACE $$ という現状にあります。$PSPACE$という複雑性クラスは、時間計算量については何も言及せず（無限に時間がかかっても解ける形式であれば構わない）、空間計算量が多項式程度に抑えられる（多項式程度のメモリ数で足りる）という問題を表します。つまり、$P,BPP,BQP$はいずれもメモリという観点では現実性のある話であることが分かっており、あとは時間計算量の関係が明らかになってほしいという状態です。
そして、古典計算量の世界では$P \neq PSPACE$であるか否かというのは未だに未解決の問題です。そこで$BPP \neq BQP$である（$BPP$よりも$BQP$の方が難しい問題を含んでおり、すなわち量子計算機の方が有利である）ということが証明されたとすれば$P\neq PSPACE$が同時に成り立つこととなります。すなわち$BPP \neq BQP$を示すというのは、長年解かれていない未解決問題を解くことになるということです。
そんなことは到底簡単なことではないというのは想像できるところでしょう。古典計算機に対する量子計算機の$BQP$に関する優位性は未だはっきりしない状態ということです。
量子コンピュータの優位性について（追記）
さて、優位性を証明することが難しいということを述べましたが、実際、多くの計算量クラスに関する関係性を証明することは、今回の件に限らず極めて困難だそうです。 すなわち「量子コンピュータの優位性が本当にあるのか怪しいから、証明が難しい」のではなく、「量子コンピュータが本当に優位だったとしても、それを数式的に証明することは根源的に難しい」のです。 では、どうすれば量子コンピュータが優位であることを知ればよいのでしょうか。というふうに感じます。 現状では量子計算でしか効率的に動作しないようなアルゴリズムを見つけるという状況証拠を集めるということになっています。
例えばあまりにも有名な「ショアのアルゴリズム」は因素因数分解を効率よく解く事が可能であり、「膨大な数の素因数分解は現実に時間では不可能、ということに基づいているRSA暗号を解くことができてしまう！！」と話題になりました。 このアルゴリズムは古典計算機では計算できないであろうとされています（つまり$BPP$ではない！）。だからこそRSA暗号が使われてきたわけです。一方でショアのアルゴリズムは量子計算機で計算できます（$BQP$である！）。すなわちショアのアルゴリズムの現状を見るに、$BPP \neq BQP$であろうと考えられるのです。
更に現在では「oracle separation」（私はまだ勉強できていません）などの新たな証拠も見つかっているようです。
最後に
さて、とりあえずここまでで記事を切ります（というかここまでしか勉強していない）。 古典的な複雑性クラスである$NP$の量子バージョン$NQP$に関してはまだ言及していませんし、また、「検証が多項式時間決定的チューリングマシンで可能である複雑性クラス」として$NP$を表現した場合の量子バージョンは$QMA$と呼ばれ、こちらについてもまだ勉強が出来ていません（状態の検証とは、とある状態が正しい状態であるかをチェックすることだそうです）。
ちなみに、今回は量子コンピュータの優位性について、結局のとこをポジティブな話を出せませんでしたが、判定問題でない場合においては、量子計算機が古典計算機を上回る例が報告されているようです。また、通信複雑性という分野においては量子が古典を圧倒するような結果が得られているようです。
以降、「測定型量子計算」や「状態の検証」、そして「量子対話型証明系」などのトピックが待ち構えているようですが、勉強できるのか、理解できるのかは謎ですがしばらく量子計算の世界を散歩してみようと思います。
