Googleの量子コンピューターが「量子超越性」を実証したとのニュースが話題になっています。（参照：MIT Technology Review） 　経済新聞も一面で報じるなどIT業界を超えた話題になっているせいか、最近私のところにも「量子コンピューターって何がすごいの？」「量子超越性って何？」との質問を多くいただくようになりました。 　そこで今日は、まず量子コンピューターの概要を説明し、その後「量子超越性」の意義とそこから生じている都市伝説について述べてみたいと思います。 　量子コンピューターが注目を浴びているのは、現在のコンピューターでは「現実的な時間内に完了することが不可能な処理」を高速に処理できる可能性を持っているからです。 　現在のコンピューターが「現実的な時間内に完了することが不可能な処理」とはどんな処理でしょう？ 　現在のコンピューターは処理する桁数が増えると倍々ゲーム的に処理ステップが増えていくような処理が苦手です。 　この代表例が因数分解です。因数分解を解く効率的なアルゴリズムは無く、候補を一つ一つしらみつぶしに試していくしか方法がありません。このため桁数が増えていくと倍々ゲームで加速的にしらみつぶしの対象が増えていき、一定の桁数を超えると最新のスーパーコンピューターでも計算に宇宙の年齢以上の時間がかかってしまうような状態となるのです。 　この状態は組合せ爆発と呼ばれています。 　量子コンピューターを使えば、組合せ爆発により現在のコンピューターでは手に負えない処理を短時間で完了できる可能性があります。