こんにちは、田中芳治といいます。これまで大学・研究機関で情報技術の研究をしてきました。色々なPJに関わってきましたが、博士論文は「量子テレポーテーション」の研究でした。よろしくお願いいたします。
前回は、楕円曲線上の離散対数問題（ECDLP）について解説し、公開鍵から秘密鍵を計算することができないという意味を解説しました。今回はECDLPを破るといわれている量子計算についての解説です。ショアのアルゴリズムと呼ばれる素因数分解用の量子アルゴリズムを少し改良して、ECDLP用にしたものがあり、今回はそれを紹介します。
現在有力とされる量子コンピューターは、「量子アニーリング」という方式と、量子版の基本ゲートを組み合わせて実現する「ゲート型」方式があります。前者はD-waveなどが有名で、探索問題などの特定の問題を解くことができるものです。一方、後者はより一般的な問題にできるため汎用性があるものです。これら２つの方式は全く異なるので、混同しないようにしてください。
ECDLP問題を解くアルゴリズムはゲート型量子コンピューターの利用を想定しています。しかし、そのゲート型量子コンピューター自体はまだ完成していません。開発のどこに難しさがあるのかなど、今回は、その困難さについても説明できれば良いかなと思います。
現在皆さんが使っているスマホやPCは様々な計算を行いますが、まず、通常の計算機による計算がどういう方法で実現されるかについて説明します。例えば２つの数を足し算する場合、それぞれ足される数は２進数（ビット列）で表され、計算はそれらの＜ビット列に対する操作＞として実行されます。「０」を電圧の低い状態、「１」を高い状態として１ビットを表し、集積回路に流れる電気的な状態として実現されています。基本論理ゲートと呼ばれる２ビット操作を考え、それを実現する基本素子（トランジスタなど）をシリコンウェハー上にレイアウトします。例えば、1ビットの足し算をするのであれば、0+0=1, 0+1=1, 1+0=1, 1+1=0の４パターンなので、XOR（排他的論理和）ゲートに対応します。実際は複数桁あるので、繰り上がりもあって複雑になりますが、基本的なゲートの組み合わせで実現できます。様々な計算は基本論理ゲートの組み合わせで実現されています。
量子計算でも基本的には同じです。ただし、通常のビットに代わって、＜量子ビット＞を利用するところが違います。ここが量子計算のポイントの一つです。量子ビットは、0 or 1いずれかの値に確定した状態をとるだけではなく、それらの＜重ね合わせ状態＞も許容されます。この量子力学的重ね合わせの状態というのは、量子力学特有な物理状態で、電子・原子・光子などといった微視的な物理系に特有な状態で、電子のスピンや光子の偏光など、いくつかの物理系が知られています。このあたりも非常に高度な物理学の知識を必要とするので、詳細は割愛いたしますが、重ねあわせを利用する点が通常のコンピューターと違う、ということをここでは理解してください。
