量子超越性を30年ぶりに超越！
すごいタイトルですが、事実です。
いくつか用語が分かりにくいと思いますので、今回はこの前提についてかみ砕いて補足しておこうと思います。
まずひっかかるのが「量子超越性」という言葉だと思います。
ちょっとカッコつけすぎな言葉な気がしますが、
ようは、今我々が馴染みのあるデジタルコンピュータ方式（スーパーコンピュータ含む）よりも高速に計算できるよ、ということです。
どんな解法（アルゴリズム）でも構いませんが、そのなかで歴史的に知られているのが1994年に提案された「ショアのアルゴリズム」と呼ばれているものです。ですのでほぼ30年ぶりの快挙になります。
このショアという方は、以前に投稿でもふれたとおり今年のブレークスルー賞でも選出されています。
このショアのアルゴリズム解説はいくつかありますが、がっつり説明したものを２つほど紹介しておきます。
日本語だとこちらがお勧めです。
英語・日本語を問わずとても難解なので、重要な個所をイメージだけ説明します。
この解法テーマは「素因数分解」で、おそらくは中学校で習うと思います。
たとえば、
21＝3×7
という具合に、3と7という素数の掛け算に分解できます。
ただ、この数が大きくなると、しらみつぶしに探さないと解けず、その困難さを利用して現代の暗号の主流であるRSA方式が開発されています。
ショアは量子コンピュータの特性を生かした高速な解法を考案したと思ってください。
例えば、15という数字を例にこのアルゴリズムを追ってみます。
まず、ランダムに15未満の整数(aとします)を選び、それを累乗（自身を掛ける）して余りを計算します。
例えば、aに3を選んで3回自身をかけると
$${3^3}$$ ÷15 = 1 余り 12
ですね。
このランダム値aを1つずつ増やしていくと実はパターンがあり、ショアはそこに目をつけました。
要は、下記の解法が量子コンピュータの特性が活かせるところです。
$${a^r}$$をNで割ると1になる r の最小値を見つける（１）
N=15の例でランダム値a=4とすると、$${4^r}$$の余りが1になる最小値は、
$${4^2}$$÷15=1余り1
で、最小値は2ということが分かります。
実はこの値rが見つかると、あとは従来のデジタルコンピュータ方式でも割と簡単に素数を見つけることが出来ます。（相当精度の高い当たり付けを量子コンピュータがしてくれる、ということです）
なぜ量子コンピュータだと（１）の計算が楽かというと、この周期性を角度に見立てて数学的な変換（フーリエ変換の応用）を施すと計算できるのですが、その角度とみたてたものを量子状態にした回路で設計することで計算ステップを節約することが出来るわけです。
この最後の表現はとても難解かつテクニカルな話なので、もっと知りたい方は上記で紹介した資料にチャレンジしてください。
つらい方は、無理をせずにイメージで量子コンピュータの強みである重ね合わせが活かしやすいんだなぁと自分を納得させるほうがよいかと思います☺
と、今回はショアのアルゴリズムを中心に話しましたが、これはあくまで「素因数分解」という特定のテーマに絞った話です。
今回30年ぶりにみつけたのは、「ハッシュ関数」です。
ハッシュとはマクドナルドの定番「ハッシュドポテト」と同じ言葉で、「バラバラに切り刻む」という語感です。
要は元の素材をバラバラに分解して、同じ入力値は同じ、違うものは違うものを返す手続きを施した関数、です。
何を当たり前のことを・・・と思うかもしれませんが、この関数のすごいところは、切り刻むことで元の値を「逆引き」できないところにあります。
ちなみにこの特性をいかしているのが、ブロックチェーンです。
相手に渡したい数字（金額とか）をハッシュ関数で全く元の値が分からない状態で生成し、それがブロックとしてチェーンで繋げたものです。
このハッシュ関数は素因数分解と違い、なかなか周期性が見いだせない領域です。そして今回の発表はその新しい解法だそうで、近いうちにその論文も公開されると思います。
また続報が分かればお伝えしますが、上述のとおりブロックチェーンの要素技術でもあるので、もしかしたらWeb3の世界にも影響をあたえるかもしれませんね。