近い未来のための量子アルゴリズム : 変分量子アルゴリズム
はじめに
先日、IBM社が 127 量子ビットの新型量子コンピュータ「Eagle」を公開し、量子コンピュータは身近なものになりつつあります。しかしながら、現時点で存在する量子コンピュータは、誤り訂正機能を持たず、正確な計算を行うことはできません。一方、誤り訂正機能を持つ量子コンピュータの実現には、まだ数十年かかると言われています。そこで、今後数十年という近い未来に、量子コンピュータで何かできないかと、近年盛んに研究が行われています。
誤り訂正機能を持たない量子コンピュータを用いた最も代表的なアルゴリズムとして、変分量子アルゴリズムが挙げられます。そこで、本稿では変分量子アルゴリズムについて述べていこうと思います。より詳しく知りたい方は、こちらのレビュー論文をおすすめします。
数理最適化問題
変分量子アルゴリズムでは、量子コンピュータを用いて、数理最適化問題を解きます。そこで、数理最適化問題について簡単におさらいしておきましょう。
数理最適化問題とは、関数の最小化問題のことです。ここでは、最小化すべき関数をコスト関数
下の図では、オプティマイザーがコスト関数の最小点を探索している様子を表しています。
変分量子アルゴリズム
変分量子アルゴリズムでは、量子コンピュータと従来のコンピュータをハイブリッドに用いて、数理最適化問題を解きます。
変分量子アルゴリズムでは、コスト関数の値や微分値を量子コンピュータ上で計算します[1]。したがって、従来のコンピュータでは計算できなかったような複雑なコスト関数を計算できる可能性があります。
こうして量子コンピュータ上で計算されたコスト関数の値や微分値をもとに、従来のコンピュータ上のオプティマイザーを用いて、パラメータのアップデートを行います。このパラメータ更新を何度も繰り返すことで、複雑なコスト関数の最小点を求めます。
下の図では、変分量子アルゴリズムの流れを示しています。IBM社の開発している量子コンピュータの写真を用いました。
コスト関数をうまく定義することで、変分量子アルゴリズムは様々な分野への応用が可能です。すでに、
などの幅広い分野への応用例が提案されています。
変分量子アルゴリズムの問題点
変分量子アルゴリズムでは、従来のコンピュータでは計算できなかった複雑なコスト関数を計算できる可能性があります。しかしながら、そんな複雑なコスト関数の最小点を効率的に求めることができるのでしょうか。
近年、バレンプラトー (barren plateau) と呼ばれる、変分量子アルゴリズムのコスト関数の勾配消失問題が起こりうることが分かってきました。 バレンプラトーとは、日本語で「不毛な大地」という意味です。コスト関数が「不毛な大地」のように平坦になってしまい、その最小点を求めることが難しくなってしまうというのです。実際、バレンプラトーが起こるような変分量子アルゴリズムのコスト関数の最適化に要する計算量は、問題サイズに対して指数的に増えていくことが示唆されています。つまり、バレンプラトーが起こるような変分量子アルゴリズムはスケーラブルではないのです。
現時点では、変分量子アルゴリズムによって従来のコンピュータ上では解けなかった複雑な問題を効率良く解けるかどうかは明確ではありません。変分量子アルゴリズムが効率的に実行可能なのか否かを理解しようと、
といった観点から研究が進められているのが現状です。
まとめ
本稿では、今後数十年という近い未来に実現されると期待されている、変分量子アルゴリズムと呼ばれるアルゴリズムについて述べました。そして、その応用範囲は幅広い一方で、必ずしも効率実行できるわけではないことに触れました。
今後は、より具体的な量子コンピュータのアルゴリズムについての記事を書いていきたいと考えています。
-
量子コンピュータの動作原理を知っている方向けに、変分量子アルゴリズムのコスト関数について詳しく述べておきます。最も基本的な変分量子アルゴリズムのコスト関数は、
で定義されます。ここで、C(\bm{\theta})=\braket{\psi(\bm{\theta})|O|\psi(\bm{\theta})} は物理量、O は量子コンピュータ上で生成されるパラメータ\ket{\psi(\bm{\theta})} を持つ量子状態としました。\bm{\theta} 量子ビットの量子コンピュータを使うことでこのコスト関数を最適化することを考えてみます。これは、n 次元複素内積空間の単位ベクトルの中から最適解を探索していると理解することができます。このように空間計算量2^n に対してn 次元の問題のコスト関数を表現できるという意味で、本稿では変分量子アルゴリズムのコスト関数が複雑だと表現しています。 ↩︎2^n -
量子近似最適化アルゴリズムと呼ばれるアルゴリズムが有名です。 ↩︎
Discussion