2-1. NISQアルゴリズムとlong-termアルゴリズム¶
現在発明・発見されている量子アルゴリズムは、実現可能性の観点から2つのグループに大別できる。 一つはNISQアルゴリズム、もう一つはlong-termアルゴリズムである。(これらの単語は一般的ではないので、他の文献を見る際には注意すること。また、この2つの区別は絶対的なものではなく、解くべき問題の大きさや技術の進歩などによって移り変るものであることに留意されたい。)それらの代表例を表に示す。
(VQE = Variational Quantum Eigensolver (5-1節), QAOA = Quantum Approximate Optimization Algorithm (5-3節), QCL = Quantum Circuit Learning (5-2節), QFT = Quantum Fourier Transform (2-3節), QPE = Quantum Phase Estimation (2-4節、7-1節), HHL = Harrow-Hassidim-Lloyd algorithm (7-2節))
NISQ アルゴリズム¶
NISQとは¶
NISQアルゴリズムの概要¶
NISQデバイスでは、前述のようにノイズの影響が不可避である。このノイズは、計算が長ければ長くなるほど(アルゴリズムが複雑になればなるほど)蓄積していき、最終的には出力結果をデタラメにしてしまう。例えば、有名な量子アルゴリズムであるShorのアルゴリズムやGroverのアルゴリズムは回路が複雑(操作の回数が多い)であり、エラー耐性の低いNISQではパワー不足で実行することが難しい。
一方で、NISQを用いたとしても何か実用的に役立つ例を見つけられないか、ということで生み出されたのがNISQアルゴリズムである。上のような言い方をするとネガティブな印象を持たれるかもしれないが、化学反応のシミュレーションなどのタスクにおいて、NISQが古典コンピュータを上回る可能性が示唆されている(Qmedia記事量子コンピュータの現在とこれから)。NISQは、量子コンピュータの古典コンピュータに対する優位性が示される「量子スプレマシー」の担い手として注目を集めているのである。
一般に量子計算は、量子ビット数が大きく、量子演算の回数が多くなるほど、エラーの影響を受けやすくなる。そのため、NISQアルゴリズムは少数の量子ビットで、かつ浅い量子回路(少ない量子ゲート数)で行える必要がある。このような背景から、NISQアルゴリズムの研究においては、「量子-古典ハイブリッドアルゴリズム」というアプローチが主流となっている。これは、行いたい計算のすべてを量子コンピュータに任せるのではなく、量子コンピュータの得意な部分のみを量子計算機に任せ、残りは古典コンピュータで処理する、というものである。Quantum Native Dojoで扱うNISQアルゴリズムは、基本的にこの量子-古典ハイブリッドアルゴリズムのアプローチに基づいている。
Long-Termアルゴリズム¶
一方、long-termアルゴリズムは、多数の量子ビットが利用可能、かつ誤り訂正が可能という仮定のもとで初めて可能になるアルゴリズムである。もちろん、NISQで実行できるかどうかは解きたい問題のサイズや精度に依存するので、どのアルゴリズムがNISQで、どのアルゴリズムがlong-termであるということに深い意味はない。基本的に全ての量子アルゴリズムはlong-termアルゴリズムであり、その一部がNISQデバイスでも実行なアルゴリズムであると考えるのが良いかもしれない。
この章で学んでいくアルゴリズムは、long-termアルゴリズムのうち入門的なものである(上表の黄色の部分を参照)。後半の章では、近年盛んに研究が進んでいるNISQアルゴリズムの他、Groverのアルゴリズムといったより高度なlong-termアルゴリズムについて取り扱う。
より深く知るには:¶
Qmedia 量子コンピュータの現在とこれから https://www.qmedia.jp/nisq-era-john-preskill/
Quantum Algorithm Zoo http://quantumalgorithmzoo.org/
Quantum Algorithm Zoo 日本語訳 https://www.qmedia.jp/algebraic-number-theoretic-algorithms/