🏞

近い未来のための量子アルゴリズム : 変分量子アルゴリズム

2022/01/25に公開

はじめに

先日、IBM社が 127 量子ビットの新型量子コンピュータ「Eagle」を公開し、量子コンピュータは身近なものになりつつあります。しかしながら、現時点で存在する量子コンピュータは、誤り訂正機能を持たず、正確な計算を行うことはできません。一方、誤り訂正機能を持つ量子コンピュータの実現には、まだ数十年かかると言われています。そこで、今後数十年という近い未来に、量子コンピュータで何かできないかと、近年盛んに研究が行われています。

誤り訂正機能を持たない量子コンピュータを用いた最も代表的なアルゴリズムとして、変分量子アルゴリズムが挙げられます。そこで、本稿では変分量子アルゴリズムについて述べていこうと思います。より詳しく知りたい方は、こちらのレビュー論文をおすすめします。

数理最適化問題

変分量子アルゴリズムでは、量子コンピュータを用いて、数理最適化問題を解きます。そこで、数理最適化問題について簡単におさらいしておきましょう。

数理最適化問題とは、関数の最小化問題のことです。ここでは、最小化すべき関数をコスト関数 C(\bm{\theta}) と呼びます。コスト関数の最小化には、オプティマイザーを用います。オプティマイザーは、コスト関数の値や微分値を求め、パラメータ \bm{\theta} の更新を繰り返し行うことで、その最小点を探索します。

下の図では、オプティマイザーがコスト関数の最小点を探索している様子を表しています。

変分量子アルゴリズム

変分量子アルゴリズムでは、量子コンピュータと従来のコンピュータをハイブリッドに用いて、数理最適化問題を解きます。

変分量子アルゴリズムでは、コスト関数の値や微分値を量子コンピュータ上で計算します[1]。したがって、従来のコンピュータでは計算できなかったような複雑なコスト関数を計算できる可能性があります。

こうして量子コンピュータ上で計算されたコスト関数の値や微分値をもとに、従来のコンピュータ上のオプティマイザーを用いて、パラメータのアップデートを行います。このパラメータ更新を何度も繰り返すことで、複雑なコスト関数の最小点を求めます。

下の図では、変分量子アルゴリズムの流れを示しています。IBM社の開発している量子コンピュータの写真を用いました。

コスト関数をうまく定義することで、変分量子アルゴリズムは様々な分野への応用が可能です。すでに、

  • 量子化学計算[2]

  • 組み合わせ最適化問題[3]

  • 機械学習[4]

などの幅広い分野への応用例が提案されています。

変分量子アルゴリズムの問題点

変分量子アルゴリズムでは、従来のコンピュータでは計算できなかった複雑なコスト関数を計算できる可能性があります。しかしながら、そんな複雑なコスト関数の最小点を効率的に求めることができるのでしょうか。

近年、バレンプラトー (barren plateau) と呼ばれる、変分量子アルゴリズムのコスト関数の勾配消失問題が起こりうることが分かってきました。 バレンプラトーとは、日本語で「不毛な大地」という意味です。コスト関数が「不毛な大地」のように平坦になってしまい、その最小点を求めることが難しくなってしまうというのです。実際、バレンプラトーが起こるような変分量子アルゴリズムのコスト関数の最適化に要する計算量は、問題サイズに対して指数的に増えていくことが示唆されています。つまり、バレンプラトーが起こるような変分量子アルゴリズムはスケーラブルではないのです。

現時点では、変分量子アルゴリズムによって従来のコンピュータ上では解けなかった複雑な問題を効率良く解けるかどうかは明確ではありません。変分量子アルゴリズムが効率的に実行可能なのか否かを理解しようと、

  • どのような変分量子アルゴリズムにバレンプラトーが生じるのか[5]

  • なぜバレンプラトーが生じるのか[6]

  • バレンプラトーを解決する手法は存在するのか[7]

といった観点から研究が進められているのが現状です。

まとめ

本稿では、今後数十年という近い未来に実現されると期待されている、変分量子アルゴリズムと呼ばれるアルゴリズムについて述べました。そして、その応用範囲は幅広い一方で、必ずしも効率実行できるわけではないことに触れました。

今後は、より具体的な量子コンピュータのアルゴリズムについての記事を書いていきたいと考えています。

脚注
  1. 量子コンピュータの動作原理を知っている方向けに、変分量子アルゴリズムのコスト関数について詳しく述べておきます。最も基本的な変分量子アルゴリズムのコスト関数は、C(\bm{\theta})=\braket{\psi(\bm{\theta})|O|\psi(\bm{\theta})} で定義されます。ここで、Oは物理量、\ket{\psi(\bm{\theta})} は量子コンピュータ上で生成されるパラメータ \bm{\theta} を持つ量子状態としました。n 量子ビットの量子コンピュータを使うことでこのコスト関数を最適化することを考えてみます。これは、2^n次元複素内積空間の単位ベクトルの中から最適解を探索していると理解することができます。このように空間計算量 n に対して 2^n 次元の問題のコスト関数を表現できるという意味で、本稿では変分量子アルゴリズムのコスト関数が複雑だと表現しています。 ↩︎

  2. 変分固有値ソルバーと呼ばれる、量子系の基底状態のエネルギーを求めるアルゴリズムが有名です。 ↩︎

  3. 量子近似最適化アルゴリズムと呼ばれるアルゴリズムが有名です。 ↩︎

  4. 機械学習への応用は多数提案されています。例えば量子回路学習と呼ばれるアルゴリズムが有名です。 ↩︎

  5. 例えばこちらの論文では、変分量子アルゴリズムにバレンプラトーが起こるか否かを判定するための手法を提案しています。 ↩︎

  6. 例えばこちらの論文では、量子コンピュータの持つ表現能力の豊かさがバレンプラトーを引き起こすことを示しています。 ↩︎

  7. 例えばこちらの論文では、バレンプラトーの影響を緩和するパラメータ初期化の手法を提案しています。 ↩︎

Discussion