Googleが実証し量子コンピューターが大きく前進したという「量子超越性」とは何を意味するのか？

by geralt

NASAがうっかりウェブサイトにGoogle研究者による論文を掲載したことをきっかけに、「Googleが量子超越性を実証した」というニュースを、2019年9月20日多くのメディアが報じました。当該論文はすでに削除されていますが、これを受けてコンピューター科学者のスコット・アーロンソン氏が「量子超越性とはなにか？」というFAQに答えています。

Shtetl-Optimized » Blog Archive » Scott’s Supreme Quantum Supremacy FAQ!
https://www.scottaaronson.com/blog/?p=4317

◆量子超越性とは？
量子超越性とは、量子コンピューターが従来型のコンピューターでは実現不可能な計算能力を備えていることを示す言葉。量子超越性という言葉を使う際に注意すべきなのは、まず問題が「量子的に」「確実に」解決されるということ。そして、従来の方法では「解くのが難しい」とされている問題であること。そして近いうちにスピードアップが見込めるものであるということ。問題解決が人々の役に立つということも重要ですが、これは必須ではないとのことです。

◆Googleが量子超越性を実現すれば、解読不能なコードはなくなるのか？

by Free-Photos

量子コンピューターの実現によって、2019年時点では解読不能なコードが解読できるようになるという声があります。しかし、IBMやGoogleが開発しているデバイスは50～100量子ビットのものであり、エラー訂正を行いません。ショアのアルゴリズムを走らせてRSA暗号を破るには数千量子ビットが必要だといわれており、現存するGoogleの技術ではまだまだ達成することができない域です。エラー訂正の手法が用いられるようになれば、より高いレベルの技術が生まれるとみられていますが、実現までには時間がかかるとのこと。

そして、仮にエラー訂正を行う量子コンピューターが実現しても、すべてのコードを解読することはできないとアーロンソン氏は考えています。また公開鍵は量子コンピューターに破られることがあっても、秘密鍵の暗号は影響をあまり受けません。加えて、「どのようにして公開鍵が量子的に破られるのか」ということは、20年以上の研究をもってしても、十分に理解されていないとアーロンソン氏は述べました。

◆従来型コンピューターが難しかったことを量子コンピューターが実現したとしても、問題自体に意味がなければ無意味ではないのか？
量子コンピューターは全てを解決するものではありませんが、決して無意味ではなく、「いくつかの問題を解決するもの」であるとのこと。

過去数十年にわたって、量子コンピューターは「何十億と使って、何十年も費やしても、ノートPCで解決できる問題さえ解決できない」といわれてきましたが、近年はもはやそのような嘲笑の対象ではありません。これまでのコンピューターでは大量のリソースを必要とした問題でもわずかなリソースで解けるようになっています。

ライト兄弟がライトフライヤー号を発明したとき、「空の旅など根本的に不可能だ」と考えていた人々は、当初は「プロペラ付きの気の抜けた乗り物」を軽視しました。インターネットのいたるところで量子コンピューターを軽視するコメントが見られますが、量子コンピューターもライトフライヤー号と同じことが言えるとアーロンソン氏は述べました。

◆量子コンピューターの行う実験結果は従来型のコンピューターがチェックします。つまり、スピードが遅くても従来型のコンピューターも量子コンピューターと同じ実験をシミュレートできるということになります。それでも「量子超越性」と呼べるのでしょうか？
この質問に対してアーロンソン氏は「53量子ビットのチップを使えば数百万倍の高速化が実現できます。量子ビットの数が増加すれば、この速度は指数関数的に増加すると、漸近解析で予測されています。ここに限界はありません」と返しています。

◆サンプリングベースの量子コンピューターに用途はありますか？

by MichaelWuensch

これまで、この質問の答えは「いいえ」だと考えられてきましたが、状況は変化しつつあります。近年は暗号通貨のプロトコルやブロックチェーンネットワークの仕組み「プルーフ・オブ・ステーク」での応用が可能だと考えられており、また今後ほかの応用分野が見つかる可能性もあるそうです。

◆量子力学ではベルの不等式の上限を破ることができますが、これは量子超越性とは言わないのでしょうか？
これは言葉の捉え方を混同していて、ベルの不等式に関しては別の形での「量子超越性」といえます。ベルの不等式を破るという意味での「quantum supremacy(量子超越性)」は「quantum correlational supremacy(量子の相関的な超越性)」とでもいえるもので、近年話題に上がっている「quantum computational supremacy(量子の計算的な超越性)」とは異なります。

◆あなたは量子超越性の概念を発明しましたか？
この質問には「いいえ」とアーロンソン氏。アーロンソン氏は量子超越性の概念が形成される上で一部の役割を担った人物です。量子超越性という用語は2012年に理論物理学者のジョン・プレスキル氏によって作られましたが、コンセプトの核は1980年代から存在する量子コンピューティングそのものにさかのぼります。

1994年、ショアのアルゴリズムを使って大きな数の因数分解をすることが量子超越性を示す主たる実験の1つになりました。サンプリング問題を使って量子超越性を示すアイデアは2002年頃から提案されるようになったもので、その1つである「ランダム回路サンプリング」という方法が、2015年12月に送ったアーロンソン氏のメールから生まれたものとのこと。その後、Googleはランダム回路サンプリングの分析を膨大に行い、量子コンピューティングの研究を深めました。

◆量子超越性が達成された場合、量子コンピューターの懐疑論者にとって何を意味するのでしょうか？
この質問には「今、彼らにはなりたくありませんね」とアーロンソン氏。「彼らは『量子超越性は可能だ』と意見を変えることができました。私のよい友人であるギル・カライなど『量子超越性は根本的な理由によって達成できない』と考えていた人の何人かは考えを変えましたが、いまだ考えを変えない人もいます。私は彼らに逃げ口上を与えたくありません」とのことです。

◆次は何が起こると思いますか？

by Lennart Wittstock

次のマイルストーンの1つはプログラミング可能な50～100量子ビットの量子コンピューターを使うこと、そして従来のコンピューターよりも高速により有用な量子シミュレーションを行うことだと考えられています。また量子超越性と有用なエラー訂正を1つのシステムで実現することもマイルストーンだとアーロンソン氏は述べました。