BLOG

NISQの時代は本当に来るのか？

PROBLEM

量子コンピュータが解くべき「難しい」問題とは何か

現在の社会において広く使用されている古典コンピュータでは手に負えないが量子コンピュータならば解ける問題を調べ上げることはできるのだろうか。そのための鍵となるのが複雑性クラスと呼ばれる概念である。古典コンピュータを用いて様々な問題を解くにあたっての難しさに基づく分類が複雑性クラスであり数学の一つの研究分野となっている。ここで言う難しさとは、問題を大規模化していくときの計算時間の増大の度合いである。古典コンピュータにとって難しいとされるのはNP困難と呼ばれる複雑性クラスであり最大カット(MAX CUT)問題、巡回セールスマン問題、ナップサック問題などさまざまな最適化問題がNP困難に属することが知られている。ここでは例としてMAX CUT問題を説明する。たとえば図2にあるように五つの頂点（白丸）と六本の辺から成るグラフが与えられたときに、一筆書き（各辺が零回または一回だけ通過されるという意味）による頂点集合の二分割のうち、切断される辺の数（カット数）が最大となるものを見つける問題である。図2には切断の仕方の例を描いてある。実際に調べれば分かるがカット数が6になるように分割することはできない。したがってこのグラフに関する最大カット数は5である。このグラフは小さいのですべての切断の仕方を列挙できるが、グラフの頂点数が増えるにつれて頂点集合の分割の場合の数が急激に増大する。頂点数が10ならば2^{10}=1024, 20ならば2^{20}=1048576, 30ならば2^{30}=1073741824という風にである。NP困難問題とは単純に言うと、規模が大きくなると計算時間が爆発的に増大する問題である。現状ではこれらの問題を古典コンピュータ上で解く際にはヒューリスティックな方法（経験に基づく方法。運が良ければ正解が得られる）が採用される。古典コンピュータにとって難しい問題を、量子コンピュータにとってさえ難しいものと量子コンピュータならば効率的に解けるものとに分類するのは興味深い課題である。

図2 左図内の破線のように一筆書きで分割したときのカット数は2である。真ん中図と右図にあるように分割したときのカット数は5である。

HYBRID

NISQ時代のための量子-古典混合アルゴリズム

本稿の冒頭で述べたように、NISQ時代の量子コンピュータは量子ビット数が少なく、しかも雑音の影響が大きいため大規模な問題を取り扱うことができない。このような現状での量子コンピュータを活用するために量子-古典混合アルゴリズムの開発が進められている。量子コンピュータが得意とする処理を量子コンピュータが担当し、古典コンピュータが得意とする処理を古典コンピュータが担当するアルゴリズムの総称が量子-古典混合アルゴリズムである。中でも変分量子アルゴリズム(Variational Quantum Algorithm, VQA)と呼ばれるものがすでに広く使われている。図3にあるように典型的な変分量子アルゴリズムにおいては、変分パラメータに基づいて量子重ね合わせ状態が量子コンピュータ上で生成され、変分パラメータの更新のために古典コンピュータが使われる。この処理を反復的に実行することにより最適な量子状態が取得される。これまでにさまざまなVQAが提案されているが、どれも基本的には図3に描かれている手順で進行する。

図3 VQAを用いた計算の模式図。Bittel and Klieschより転載。

EXAMPLE

変分量子アルゴリズムの例: QAOA

現実的な需要のある最適化問題の多くは二次無制約二値最適化(Quadratic Unconstrained Boolean Optimization, QUBO)問題として表現できることが知られており、それを量子コンピュータを用いて解くのが量子近似最適化アルゴリズム(Quantum Approximation Optimization Algorithm, QAOA)である[Blekos et al., arXiv:2306.09198]。

図4 QAOA法の手順。Blekos et al.より転載。

変分量子アルゴリズムの例: ADAPT-VQE

量子化学計算のためのVQAとして変分量子固有解法(Variational Quantum Eigensolver, VQE)がある。それの改良版のうち特に有望視されているのがADAPT-VQEである[Grimsley et al., Nature Communications 10, 3007 (2019)]。図5にあるように変分回路を生成するための演算子の候補の集まり（演算子プール）を定義し、それらの中から分子系の相関エネルギーが最も低くなるように候補を選んで変分回路を増設していく手法である。増設のための演算子を決定してからのパラメータ最適化は通常のVQEと同様である。図5はBeH2分子の全エネルギー計算のためのADAPT-VQEと他の手法の比較である。図6を見れば分かるようにADAPT-VQEは他の手法よりも少ない回路パラメータで小さい誤差を達成できる。量子回路が深くなることが信頼性に重大な影響を与えるNISQ時代の量子コンピュータにとって、ADAPT-VQEのこの特徴は大きな強みである。

図5 ADAPT-VQE法の手順。Grimsley et al.より転載。

図6 ADAPT-VQEと他の手法でのBeH2分子の全エネルギーと厳密解の差。Grimsley et al.より転載。

PROSPECTS

これまでにさまざまなVQAが提案されており、概念実証のための単純な問題に対しては成功を収めている。しかしここで留意するべきは、VQAを使用して問題を解く際の量子部分の計算時間が0であると仮定しても、古典部分によってその問題はNP困難になってしまうことが数学的に証明されている[Bittel and Kliesch, Phys. Rev. Lett. 127, 120502 (2021)]ということである。複雑性クラスは最悪の場合（最も時間がかかる事例）での計算時間に基づく分類であるからVQAには実用性が無いというわけではないが、アルゴリズムの量子部分がどんなに優れていても古典部分に足を引っ張られる可能性がある。VQAに付随するNP困難性を回避する方策の一つとして、非変分アルゴリズムの使用がある。VQA由来のNP困難性を回避したからといって非変分アルゴリズムが種々のNP困難問題を効率的に解けると保証されるわけではないので、各々の非変分アルゴリズムにとって解ける問題とそうでない問題の区別が重要である。我々は最近、古典コンピュータの併用を前提としない一般的な非変分アルゴリズムとして確率的虚時間発展法(Probabilistic Imaginary-Time Evolution, PITE®️)を提案した[Kosugi et al., Phys. Rev. Research 4, 033121 (2022)]。変分回路が想定する範囲内でしか量子状態を最適化できないVQAとは異なり、PITE®️は真の量子最適化を実行できるのが特長の一つである。将来的にハードウェア技術の発展により量子コンピュータを成す量子ビット数が増え、しかも誤り訂正が実装されたNISQ後の時代にPITE®️の有用性が発揮されると期待できる。

変分量子アルゴリズムのNP困難性とNISQ後に向けて

量子コンピュータの開発には最先端のハードウェア技術が要求される

2019年のグーグル社による量子超越性の達成の発表以来、量子コンピュータの研究開発はますます活発になっている。国立研究開発法人科学技術振興機構　研究開発戦略センターは、図1にあるように量子ビット数が推移していくと予想した。我々が現在も日常的に利用している古典コンピュータを凌駕する性能を量子コンピュータが発揮するには量子ビット数が10000を超え、しかも誤り耐性を備えた量子ビットを使用しなければならないと考えられている。穏当な予測ではそこに到達するのは2050年頃であるとみられており、現在からの約30年は雑音なし中規模量子デバイス(noisy intermediate-scale quantum device, NISQ)の時代と呼ばれている。誤り耐性を備えた量子コンピュータの将来的な使用を前提とした有用なアルゴリズムの開発と、それらをNISQ時代向けに修正したり中規模な問題に適用したりする近未来的な試みの両方が活発に行われている。2023年7月時点で433量子ビットから成る量子コンピュータがIBM社により開発されており、大規模化が順調に進んでいると言える。

INTRODUCTION

図1　ゲート方式量子コンピュータを成す量子ビット数の推移。国立研究開発法人科学技術振興機構　研究開発戦略センター「みんなの量子コンピューター」（2018年）より転載。