今日から学ぶサクッと量子コンピュータ講座【上級編】第17回：量子計算複雑性クラスとBQP問題

サマリ

量子コンピュータが従来型コンピュータとどれほど異なるのかを理解するには、計算複雑性クラスの知識が欠かせません。この記事では、量子計算の難しさを分類するBQPクラスについて、わかりやすく解説します。

詳細

計算複雑性クラスとは何か

まず基本から始めましょう。計算複雑性クラスは、「問題を解くのに必要な時間や計算量によって問題を分類する」という考え方です。想像しやすくするために、料理の難易度を考えてみてください。カレーを作るのと、フレンチフルコースを作るのでは、必要な時間も技術も全く異なりますよね。計算の世界も同じです。

従来型コンピュータの世界では、Pクラスという概念が重要です。これは「多項式時間で解ける問題」つまり「比較的短時間で確実に答えが出せる問題」の集合です。一方、NPクラスは「答えが正しいかどうかを多項式時間で検証できる問題」を指します。足し算の答えが正しいか確認するのは簡単ですが、その足し算問題を最初から解くのはどちらも難しくない、という感覚です。

BQPクラスの登場

さて、ここで量子コンピュータが登場します。BQPクラスは「Bounded-error Quantum Polynomial time」の略で、日本語では「量子多項式時間」と呼ばれます。これは、量子コンピュータが多項式時間で高い確率で解ける問題のクラスです。

ポイントは「高い確率」という部分です。従来型コンピュータが「必ず正しい答え」を求めるのに対し、量子コンピュータは「確率的に正しい答えを出す」という特性があります。具体的には、少なくとも2/3以上の確率で正しい答えを出すことができれば、BQPクラスに属していると言えます。

BQPと他のクラスとの関係

では、BQPはPクラスやNPクラスとどのような関係にあるのでしょうか。これが非常に興味深い部分です。

現在のところ、PクラスはBQPに含まれていると予想されています。つまり、従来型コンピュータで簡単に解ける問題は、量子コンピュータでも簡単に解けるということです。これは直感的に理解できますね。

一方、BQPがNPクラスに含まれるのかは、まだわかっていません。この問題は、計算理論における最大のミステリーの一つです。もしBQPがNPに含まれれば、量子コンピュータでNP問題を多項式時間で解けることになり、コンピュータサイエンス全体が大きく変わります。

現実世界での意味

では、BQPの理論的な理解が、実際の生活にどう影響するのでしょうか。

量子コンピュータが得意とされている問題の多くが、BQPクラスに属しています。例えば、大きな数を素因数分解する「因数分解問題」はBQPに属すると考えられており、Shorのアルゴリズムという有名な量子アルゴリズムで解くことができます。これは現在の暗号技術に大きな脅威をもたらす可能性があります。

また、量子データベース検索の「Groverのアルゴリズム」も、BQPの代表的な例です。これは従来型コンピュータより約2倍高速に検索できます。

BQPクラスの大きさ

興味深いことに、BQPクラスはPクラスと比べて、かなり広いと予想されています。図で表現するなら、BQPの方が大きな円を描くイメージです。ただし、NPクラスほどは大きくないと考えられています。

2022年の研究では、量子コンピュータの能力は、古典的なコンピュータ理論の予測とおおむね一致していることが確認されました。これまで約2000台の量子ビットを持つ実験用量子コンピュータで検証されています。

今後の展開と課題

BQPクラスの研究は、量子コンピュータの実用化に向けた重要なステップです。将来、量子コンピュータが十分に大規模化されれば、医薬品開発や材料科学、金融シミュレーションなど、BQPに属する問題を現実的に解くことができるようになるでしょう。

ただし、現在の量子コンピュータはまだ発展途上です。量子ビットのエラー率を下げることが、BQPクラスの真の力を引き出すための最大の課題となっています。