2-1. NISQアルゴリズムとlong-termアルゴリズム

現在発明・発見されている量子アルゴリズムは、実現可能性の観点から2つのグループに大別できる。 一つはNISQアルゴリズム、もう一つはlong-termアルゴリズムである。（これらの単語は一般的ではないので、他の文献を見る際には注意すること。また、この２つの区別は絶対的なものではなく、解くべき問題の大きさや技術の進歩などによって移り変るものであることに留意されたい。）それらの代表例を表に示す。

2-1

(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（NISAではない）デバイスとは何なのであろうか。
NISQ（一般に「ニスク」と発音される）デバイスとはNoisy Intermediate-Scale Quantum deviceの略で、数年〜十年以内に実現可能と考えられている、小～中規模（量子ビット数〜数百個程度）の量子コンピュータの総称である。NISQデバイスは、大量の量子ビットを必要とする「量子誤り訂正」（[第9章]）を行う事ができず、計算途中で起こる誤り（ノイズ）の影響をもろに受けてしまう（このような意味でNoisyという形容詞が付されている）。計算途中での誤りを随時訂正できる真の量子コンピュータにはまだ遠く、通常のコンピュータに例えるなら、集積回路の発明以前のトランジスタ式や真空管式のコンピュータのような段階と言っても良いかもしれない。

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アルゴリズムについて取り扱う。

より深く知るには：