ついに量子コンピュータだけが解決できる問題が

量子コンピュータ研究の初期段階において、コンピュータ科学者たちはある疑問を提起しました。その答えは、この未来的なマシンの持つ力について深い何かを解き明かすだろうと彼らは確信していました。25年後、その疑問はほぼ解決されました。5月末にオンラインに投稿された論文の中で、コンピュータ科学者のラン・ラズ氏とアヴィシャイ・タル氏は、量子コンピュータが従来のコンピュータが達成できる範囲をはるかに超える計算能力を備えていることを示す強力な証拠を示しています。

プリンストン大学とワイツマン科学研究所の教授であるラズ氏と、スタンフォード大学のポスドク研究員であるタル氏は、特定の種類の計算問題を定義しました。彼らは、ある一定の条件付きで、従来のコンピュータでは永遠に解決できない問題を、量子コンピュータが効率的に処理できることを証明しました。コンピュータ科学者たちは、1993年に「BQP」と呼ばれる一連の問題を初めて定義して以来、このような問題を探求してきました。BQPは、量子コンピュータが解けるすべての問題を包含するものです。

それ以来、コンピュータ科学者たちはBQPを「PH」と呼ばれる種類の問題と対比させたいと願ってきました。PHは、あらゆる古典的コンピュータで解ける問題、さらには未来の文明が設計する計り知れないほど高度な問題さえも包含します。この対比を実現するには、BQPには存在するがPHには存在しないことが証明できる問題を見つける必要がありました。そして今、ラズとタルはそれを成し遂げました。

この結果は、量子コンピュータが実用的な意味で古典コンピュータよりも優れていることを示すものではありません。まず、理論計算機科学者は、量子コンピュータが古典コンピュータが解けるあらゆる問題を解けることを既に知っていました。そして、エンジニアたちは今もなお、実用的な量子コンピュータの構築に苦心しています。しかし、ラズ氏とタル氏の論文は、量子コンピュータと古典コンピュータが実際には全く異なるカテゴリーであることを示しています。古典コンピュータがあらゆる現実的な夢を超えて成功を収めたとしても、量子コンピュータは依然として古典コンピュータを凌駕する存在であり続けるでしょう。

量子クラス

理論計算機科学の基本的な課題は、問題を複雑度クラスに分類することです。複雑度クラスには、与えられたリソース予算内で解決できるすべての問題が含まれます。ここで、リソースとは、時間やメモリなどです。

コンピュータ科学者は、例えば、ある数が素数かどうかを判定するための効率的なアルゴリズムを発見しました。しかし、大きな数の素因数を特定するための効率的なアルゴリズムは発見できていません。そのため、コンピュータ科学者は、これら2つの問題は異なる計算量クラスに属すると考えています（ただし、証明はできていません）。

最も有名な2つの複雑性クラスは「P」と「NP」です。Pは、古典的なコンピュータが迅速に解決できるすべての問題です。（「この数は素数か？」はPに属します。）NPは、古典的なコンピュータが必ずしも迅速に解決できないが、答えが提示されれば迅速に検証できるすべての問題です。（「その素因数は何か？」はNPに属します。）コンピュータ科学者は、PとNPは異なるクラスであると考えていますが、実際にその違いを証明することが、この分野で最も困難かつ最も重要な未解決問題です。

1993年、コンピュータ科学者のイーサン・バーンスタインとウメシュ・ヴァジラニは、「限界誤差量子多項式時間」の略称であるBQPと呼ばれる新しい計算量クラスを定義しました。彼らはこのクラスを、量子コンピュータが効率的に解けるすべての決定問題（答えが「はい」か「いいえ」である問題）を含むものと定義しました。ほぼ同時期に、彼らは量子コンピュータが古典コンピュータが解けるすべての問題を解けることも証明しました。つまり、BQPはPに含まれるすべての問題を含むということです。

1. 複雑性クラスを考える際には、例が役立ちます。「巡回セールスマン問題」は、いくつかの都市を通る経路のうち、ある距離よりも短い経路が存在するかどうかを問うものです。これはNP問題です。より複雑な問題は、それらの都市を通る最短経路がまさにその距離であるかどうかを問うものです。この問題はPH問題である可能性が高いです（ただし、証明されていません）。

しかし、彼らは BQP に「多項式階層」を表す「PH」として知られる別の重要な問題クラスに見つからない問題が含まれているかどうかを判断できませんでした。PH は NP の一般化です。つまり、NP の問題から始めて、「存在する」や「すべてに対して」などの修飾ステートメントを重ねてより複雑にした場合に発生するすべての問題が含まれています。1現在^の古典的なコンピュータは PH の問題のほとんどを解決できませんが、P が NP に等しいことが判明した場合に古典的なコンピュータが解決できるすべての問題のクラスとして PH を考えることができます。言い換えれば、BQP と PH を比較することは、古典的なコンピュータが（予想外に）今日よりも多くの問題を解決できたとしても生き残るほどの、量子コンピュータが古典的なコンピュータに対して優位性を持っているかどうかを判断することです。

「PHは、古典的複雑性理論の最も基本的なクラスの一つです」と、テキサス大学オースティン校のコンピュータ科学者、スコット・アーロンソン氏は述べた。「ですから、量子コンピューティングが古典的複雑性理論の世界でどこに位置づけられるのかを知りたいのです。」

2つの複雑性クラスを区別する最良の方法は、一方に該当し、他方には該当しないことが証明できる問題を見つけることです。しかし、根本的な問題と技術的な問題が重なり、そのような問題を見つけることは困難でした。

BQPには存在するがPHには存在しない問題を解きたい場合、「定義上、古典コンピュータでは答えを見つけるどころか、効率的に検証することさえできない」問題を特定する必要があるとアーロンソン氏は述べた。「これは、コンピュータサイエンスで私たちが考える多くの問題を除外することになります。」

オラクルに聞く

問題はこうです。2つの乱数生成器があり、それぞれが数字の列を生成するとします。コンピュータにとっての問いは、この2つの列は完全に独立しているのか、それとも隠れた形で関連しているのか（一方の列がもう一方の「フーリエ変換」となっている場合）ということです。アーロンソンは2009年にこの「相互関係」問題を提起し、それがBQPに属することを証明しました。残るはより難しい2番目のステップ、すなわち相互関係がPHに含まれないことを証明することです。

まさにそれが、ラズとタルが特定の意味で成し遂げたことです。彼らの論文は、BQPとPHの間のいわゆる「オラクル」（または「ブラックボックス」）分離を実現しました。これはコンピュータサイエンスにおいて一般的な結果であり、研究者が本当に証明したいことが手の届かないところにある場合に頼るものです。

BQPやPHのような複雑性クラスを区別する最良の方法は、それぞれの問題を解くのに必要な計算時間を測定することです。しかし、トロント大学のコンピュータ科学者ヘンリー・ユエン氏は、「コンピュータ科学者は実際の計算時間について、それほど高度な理解や測定能力を持っていません」と述べています。

そこでコンピュータ科学者は、測定できない計算時間に関する洞察が得られることを期待して、別のものを測定します。それは、コンピュータが答えを出すために「オラクル」に何回相談する必要があるかを計算することです。オラクルとはヒントを与える人のようなものです。オラクルがどのようにヒントを出すのかは分かりませんが、そのヒントが信頼できるものであることは分かります。

2つの乱数生成器が密かに関連しているかを判定する問題であれば、「それぞれの生成器の6番目の数字は何か？」といった質問をオラクルに投げかけることができます。そして、それぞれの種類のコンピュータが問題を解くのに必要なヒントの数に基づいて計算能力を比較します。より多くのヒントを必要とするコンピュータは遅くなります。

「ある意味で、このモデルははるかに深く理解できます。計算よりも情報に関する話が多いのです」とタル氏は語った。

ラズ氏とタル氏による新しい論文は、量子コンピュータが対関係問題を解くのに古典コンピュータよりもはるかに少ないヒントしか必要としないことを証明しています。実際、量子コンピュータに必要なヒントはたった1つですが、たとえヒントを無制限に与えたとしても、PHではこの問題を解決できるアルゴリズムは存在しません。「これは、この問題を解決できる非常に効率的な量子アルゴリズムが存在することを意味します」とラズ氏は述べています。「しかし、古典アルゴリズムだけを考えた場合、たとえ古典アルゴリズムの非常に高度なクラスにまで達したとしても、それらのアルゴリズムは解決できません。」これは、オラクルを用いると、対関係問題はBQPでは存在するがPHでは存在しない問題であることを示しています。

ラズ氏とタル氏は約4年前にこの結果にほぼ到達しましたが、証明の1ステップも完了できませんでした。そしてちょうど1ヶ月前、タル氏は擬似乱数生成器に関する新しい論文の講演を聞き、その論文に書かれている手法こそが、彼とラズ氏が自身の証明を完成させるのにまさに必要なものだと気づきました。「これが欠けていたピースだったんです」とタル氏は言います。

この研究は、量子コンピュータが古典コンピュータとは異なる計算領域（少なくともオラクルと比較すると）に存在するという確固たる証拠を提供している。PがNPに等しい世界、つまり巡回セールスマン問題がスプレッドシート上で最適な直線を見つけるのと同じくらい単純な世界であっても、ラズとタルの証明は、量子コンピュータにしか解けない問題が依然として存在することを実証している。

「たとえPがNPに等しいとしても、そのような強い仮定を立てたとしても、それは量子コンピューティングを捉えるのに十分ではないだろう」とフォートナウ氏は語った。

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。