Filtering Variational Quantum Eigensolver (F-VQE)

F-VQEは、Cambridge Quantum Computingから２０２１年６月に発表されたフィルタリングオペレータを用い、組み合わせ最適化問題を解くVQEの最適解への収束をより速く、より確実にする アルゴリズムこのことです。まず、最初に、Cambridge Quantum Computingの Faster quantum algorithms for combinatorial optimization の記事で、その概要をみることとします。

Faster quantum algorithms for combinatorial optimization

多くの産業界では、古典コンピュータでは困難な最適化問題に直面しています。

製品を生産するメーカーでの生産計画、物流業界でのルートの最適化などです。これらは有限の回答候補のなかから最適な解をみつけだすという組み合わせ最適化問題の一例です。組合せ最適化問題を正確に解くことは、量子コンピュータを含むあらゆるコンピュータにとって非常に困難です。そのため、ヒューリスティクス（発見的手法）をもちいることになります。

量子ヒューリスティクスが難問を解決する

組み合わせ最適化問題を近似的に解く量子アルゴリズムが研究されてきました。新しいヒューリスティクスを強力な量子ハードウェアで実行すれば、近似解の精度が向上する可能性があります。

アルゴリズムの代表的な例としては、量子近似最適化アルゴリズム(QAOA)や、化学の問題でよく使われる変分型量子固有値ソルバー(VQE)などがあります。これらは、パラメータをもちいて表現されたハミルトニアン、すなわちエネルギー関数の一番低い状態を、勾配降下法で求めるというものでした。これらのヒューリスティックスを、現在のノイズの多い中間スケールの量子（NISQ）ハードウェアで使えるような新しいアルゴリズムが F-VQE です。

Filtering Variational Quantum Eigensolverは、斬新で高速かつ正確な量子ヒューリスティックである

Cambridge Quantum Computing は、標準的なVQEやQAOAと比較して、収束の高速化、解の質の向上、ハードウェアリソースの削減を実現する新しい手法、「Filtering Variational Quantum Eigensolver（F-VQE）」 を開発し、検証しました。この手法は、量子システムのエネルギーの最低値をより少ないステップで求めようというものです。

このアルゴリズムの基本的な考え方はシンプルですが、効果的です。最適化の各ステップで、アルゴリズムはフィルタを適用してエネルギー関数を修正します。フィルターとは、最低値の相対的な深さを増加させるが、最低値の位置は変えない変換のことです。その結果、アルゴリズムは、エネルギー関数そのものを使うときに比べて、より深い谷を見つけ、浅い谷から抜け出すのが速くなります。これを「収束が早い」と言います。シミュレータ上では、VQEやQAOAと比較して10〜100倍の速さで収束することが確認されており、Honeywell System Model H1トラップイオン量子コンピュータでもこの挙動が確認されています。

また、新しいアルゴリズムでもとめらた解は、各問題の最適解の周りにしっかりと集まっていることも分かりました。これは、これまでのアルゴリズムで見つけた解よりも、今回のアルゴリズムで見つけた解の候補の方が、最適解に近い可能性が高いことを意味しています。

因果コーン (causal cones) との組み合わせにより、F-VQEはより少ない量子ビットでより大きな最適化問題を解くことができる

新しい手法は、容量の限られたハードウェア上でも、大きな問題に対応することができます。多くの量子最適化アルゴリズムは、最適化問題の各二値変数を1つの量子ビットにほぼ対応させている。そのため、現在のハードウェアでは、インスタンスのサイズが数十個の変数に制限されています。この限界を超えるために、 Cambridge Quantum Computing は、フィルターと、以前に検討した「因果コーン(causal cones) 」という概念を組み合わせました。因果コーンとは、大規模な量子回路の評価を、数量子ビット程度の小さな評価に分割する体系的な方法です。この技術は、問題の大きさと必要な物理的量子ビットの数を切り離すことができます。例えば、23個の量子ビットの状態に埋め込まれた最適化問題を、最大6個のハードウェア量子ビットを使って解くことができました。

量子ハードウェアとアルゴリズムの改善が、より優れた最適化ヒューリスティックへの道を切り開く

この手法は、現在のハードウェアで量子最適化ヒューリスティクスが扱える問題の大きさの限界を、一般的な数量子ビットから数十量子ビットへと押し上げるものです。この開発は、物理的に利用可能な量子ビットと、応用的な問題を解決するために効果的に利用できる量子ビットとの間のギャップを縮めるという点で重要です。F-VQEは、現在の量子ハードウェアを、製造、物流、サプライチェーンマネジメント、金融などの分野で遭遇する組み合わせ最適化問題に役立てるという目標に向けた一歩で、最終的には、ハードウェアの改良とアルゴリズムの革新を組み合わせることが、最適化における量子的な優位性を実現するために必要であると考えられています。

Filtering variational quantum algorithms for combinatorial optimization

ここからは、オリジナル論文に沿って、F-VQEが、どのようなアルゴリズムなのか、詳細を、見ていきます。以下、論文の抄訳と筆者のメモです。

論文では、因果コーン(causal cones)を用いて、量子コンピュータに必要な量子ビット数を削減することが検討されています。ランダム 重み付けされたランダムなMaxCut問題を用いて、オリジナルのVQEアルゴリズムと比較して優れた性能を発揮することを示したとしています。また，Honeywell社製のトラップイオン量子プロセッサを用いて，アルゴリズムが実験的に実現可能であることが示めされています。

Filtering variational quantum algorithms for combinatorial optimization
David Amaro et al., Cambridge Quantum Computing Limited, June 21, 2021

https://arxiv.org/pdf/2106.10055.pdf

はじめに

Variational Quantum Eigensolver (VQE) やQuantum Approximate Optimization Algorithm (QAOA) などの一般的な変分量子アルゴリズムは，エネルギー期待値を最小化する回路パラメータを探索することで、基底状態を求めます。

VQEは、アンサッツ回路に制限がなく、量子化学や組み合わせ最適化において強力な手法です．しかし，最適化問題では，最適ではない解を生成する傾向があります。QAOAは 断熱的量子計算やトロッター量子計算にヒントを得た特殊なアンサッツ回路を用いています。一般的にQAOAアンサッツは、現在の量子ハードウェアでは演算が困難な長さの回路のを必要とします。

パラメータ化された量子回路を最適化して、この回路の動作をフィルタリング演算子を用いて近似する量子変分フィルタリング（QVF）アルゴリズムを提案します。また、QVF の特殊例として、とくに有効でVQEに似たアルゴリズム　フィルタリングVAE(F-VQE）も合わせて提案します。

ハミルトニアン $\mathcal{H}$ とパラメータ $\tau$ からなる実数関数 $f$ によるフィルタリング演算子 $F \equiv f(\mathcal{H} ; \tau)$ を考えます。$f^{2}(E ; \tau)$ は、$\tau>0$ の場合に、エネルギー $E$ に対して単調減少するものとします。パラメータ $\tau$ は、imaginary time evolution （ITE) におけるタイムステップと同様の役割をし、ITE演算子　$\exp (-\tau \mathcal{H})$ は、この提案におけるフィルタリング演算子の例です。量子状態に対するフィルタリング演算子の繰り返しは、高エネルギー固有状態を投影し（組み合わせ最適化問題の次善の解に対応）、基底状態とのオーバーラップを増加させます。重要なのは、QVFとF-VQEにはアンザッツに制限がないため、対象とする量子ハードウェアに最も適したアンザッツを使用できることです。さらに、量子ハードウェアに必要な量子ビット数を大幅に削減できる因果コーンを最適化に使用することで、どのフィルタリング演算子が有益になるかという問題にも取り組みました。本論文で検討したフィルタリング演算子の中で、ITE演算子が因果コーンと組み合わせることで最も良い性能を発揮することが分かりました。そこで、F-VQE法がハードウェアに有利なITE法（HE-ITE)と同等である、因果コーンとITE法の組み合わせに注目します。

様々なフィルタリング演算子を用いたF-VQEと、大きさの異なるランダム3正則重み付きグラフのMaxCut問題を用いたHE-ITEの性能を調べました。図に示すように，F-VQEはVQEやQAOAよりも少ない最適化ステップで一貫して大きな近似比を達成しています．さらに、F-VQEは実際の量子計算機上で容易に動作します。また、HE-ITEアルゴリズムは、少ない量子ビット数とゲート数で同様の結果を得ることができます。

手法

まずフィルタリング演算子を定義します。次に、QVFとF-VQEのアルゴリズムについて説明します。F-VQEでは、最適化中に $τ$ を動的に更新する手順を紹介します。さらに、F-VQEでは、どのフィルタリング演算子が因果関係のあるコーンを使用できるかという問題に取り組みます。

フィルタリング演算子

与えられた $n$ Qビットのハミルトニアン $\mathcal{H}$ にたいして、フィルタリング演算子 $F \equiv f(\mathcal{H} ; \tau)$ を、エネルギー $E$ と、パラメータ $\tau>0$を用いた実数関数 $f(E ; \tau)$ を定義します。

量子状態 $|\psi\rangle$ が。ハミルトニアンの固有状態 $\left|\lambda_{x}\right\rangle: \quad x=0,1, \ldots, 2^{n}-1$ から選ばれるとすると、固有ベクトルの確率密度は、 $P_{\psi}\left(\lambda_{x}\right)=\left|\left\langle\psi \mid \lambda_{x}\right\rangle\right|^{2}$　で与えられます。その量子状態にフィルタリング演算子をを作用させると、新しい量子状態は、 $|F \psi\rangle=F|\psi\rangle / \sqrt{\left\langle F^{2}\right\rangle_{\psi}}$ となり、エネルギー $E_{x}$ と固有状態 $\left|\lambda_{x}\right\rangle$ に依存した確率密度を求めることができます。

$$
P_{F \psi}\left(\lambda_{x}\right)=\frac{f^{2}\left(E_{x} ; \tau\right)}{\left\langle F^{2}\right\rangle_{\psi}} P_{\psi}\left(\lambda_{x}\right)
$$

非固有状態 $|\psi\rangle$ については、フィルタリング演算子は、$f^{2}\left(E_{x} ; \tau\right)>\left\langle F^{2}\right\rangle_{\psi}$ となるオーバーラップする固有状態 $\left|\lambda_{x}\right\rangle$ ($\left.P_{\psi}\left(\lambda_{x}\right)>0\right)$ との確率を増加させ、 $f^{2}\left(E_{y} ; \tau\right)<\left\langle F^{2}\right\rangle_{\psi}$　となるオーバーラップする固有状態 $\left|\lambda_{y}\right\rangle$ との確率を減少させます。

$f^{2}(E ; \tau) $は、E に対して厳密に減少するので、低いエネルギー状態の量子状態のサンプリングの確率は、増加し、高いエネルギー状態の量子状態の確率は減少する。つまり、平均エネルギーを減少させることになる。特に、基底状態 $\left|\lambda_{0}\right\rangle$ が、初期状態と有限のオーバーラップ $\left(P_{\psi}\left(\lambda_{0}\right)>0\right)$ を持つとき、サンプリングの確率は、フィルタリング演算子を施すたびに増加する。十分な数の演算子を施すと、基底状態が作られます。

フィルタリング関数の定義例を、図にしめします。

フィルタリング演算子の定義にあるパラメータ $\tau$ は、量子断熱計算のタイムステップパラメータにヒントを得ています。実際，上の図の指数フィルタリング演算子では，$\tau$はまさにこのタイムステップです．このパラメータは、フィルタリング演算子の作用を2つの限界間で補間します。 $\tau \rightarrow 0$ の場合、フィルタリング演算子は恒等演算子となり、$\tau \rightarrow \infty$の場合、フィルタリング演算子は基底状態への射影演算子となります。

Quantum Variational Filtering (QVF) 量子変分フィルタリング

QVFアルゴリズムは、パラメータ化された量子回路の変分パラメータを逐次最適化することで、ある初期量子状態に対するフィルタリング演算子の繰り返し作用を近似します。このアルゴリズムは，最適化ステップ$t=0$で，基底状態と有限の重なりを持つ初期状態 $\left|\psi_{0}\right\rangle$ から開始します．このアルゴリズムは繰り返し実行され，各最適化ステップにおいて $\left|F_{t} \psi_{t-1}\right\rangle$ の状態に近づきます。$F_i$ は、フィルタリング演算子を各最適化ステップで、変えることができることをしめします。

フィルタリング演算子を作用を近似するために、$m$ 個のパラメータ$\boldsymbol{\theta}=\left(\theta_{1}, \ldots, \theta_{m}\right) . \quad$をもつ、量子回路アンザッツ $|\psi(\boldsymbol{\theta})\rangle$ を用意します。おのおのの最適化ステップ $t$ において、パラメータ化された量子状態と $\left|F_{t} \psi_{t-1}\right\rangle$ の間のユークリッド距離が最小となるパラメータを探索します。

$$
\begin{aligned}
\mathcal{C}_{t}(\boldsymbol{\theta}) &=\frac{1}{2} ||\psi(\boldsymbol{\theta})\rangle-\left|F_{t} \psi_{t-1}\right\rangle |^{2} \\
&=1-\frac{\operatorname{Re}\left\langle\psi_{t-1}\left|F_{t}\right| \psi(\boldsymbol{\theta})\right\rangle}{\sqrt{\left\langle F_{t}^{2}\right\rangle_{\psi_{t-1}}}}
\end{aligned}
$$

上の式の最小化の最後のステップで得られたパラメータが、最適化ステップ $t$ の量子状態、 $\left|\psi_{t}\right\rangle \equiv\left|\psi\left(\boldsymbol{\theta}_{t}\right)\right\rangle$ を決めます。この損失関数はアダマールテストをもちいて、最小化できます。

Filtering VQE (F-VQE)

QVFでのアダマールテストに必要な追加の量子ビットの追加を避けるため　F-VQEが開発されました。F-VQEのアルゴリズムは、特定の勾配ベースの手順を用いており、VQEと基本的に同じ回路を必要とします。

上の式のコスト関数の1つのパラメータ$\theta_{j}$に対する偏微分は、以下の通りとなります。

$$
\frac{\partial \mathcal{C}{t}(\boldsymbol{\theta})}{\partial \theta{j}}=-\frac{\operatorname{Re}\left\langle\psi_{t-1}\left|F_{t}\right| \psi\left(\boldsymbol{\theta}+\pi \boldsymbol{e}{j}\right)\right\rangle}{2 \sqrt{\left\langle F{t}^{2}\right\rangle_{\psi_{t-1}}}}
$$

ここで、角度のベクトルをパラメータ$\theta_{j}$の方向に$\pi$だけシフトさせる以外は同じアンサツ回路で生成された状態$\left|\psi\left(\boldsymbol{\theta}+\pi \boldsymbol{e}_{j}\right)\right\rangle$が生成されます。勾配をパラメータの現在のベクトル $\boldsymbol{\theta}_{t-1}$ で評価すると、次のパラメータシフトルール が成り立ちます。

$$
\left.\frac{\partial \mathcal{C}_{t}(\boldsymbol{\theta})}{\partial \theta{j}}\right|_{\boldsymbol{\theta}_{t-1}}=-\frac{\left\langle F_{t}\right\rangle_{\psi_{t-1}^{j+}}-\left\langle F_{t}\right\rangle_{\psi_{t-1}^{j-}}}{4 \sqrt{\left\langle F_{t}^{2}\right\rangle_{\psi_{t-1}}}}
$$

このように、違っったパラメータの３つの回路 $\left|\psi_{t-1}\right\rangle$ and $\left|\psi_{t-1}^{j \pm}\right\rangle \equiv$ $\left|\psi\left(\boldsymbol{\theta}_{t-1} \pm \frac{\pi}{2} \boldsymbol{e}_{j}\right)\right\rangle$ がアンザッツで生成されます。なお、分母の期待値は、特定の$t$におけるすべての偏微分について同じです。

F-VQEアルゴリズムは、この有利なケースを次のように利用しています。最適化ステップ $t$ において、F-VQE は単一の勾配降下の更新を実行します。

$$
\boldsymbol{\theta}{t}=\boldsymbol{\theta}{t-1}-\left.\eta \sum_{j=1}^{m} \frac{\partial \mathcal{C}_{t}(\boldsymbol{\theta})}{\partial \theta_{j}}\right|_{\boldsymbol{\theta}{t-1}} \boldsymbol{e}_{j}
$$
$\eta>0$ は学習率です。

フィルタリング演算子の期待値 $\left\langle F_{t}\right\rangle_{\psi}$ は、ハミルトニアン固有状態の量子状態をサンプリングすることによって、効率的に評価できます。固有状態 $\left|\lambda_{x}\right\rangle$ が、 $M$ 個のサンプルにたいして、$M_{x}$ 回サンプリングされるとすると、 フィルタリング演算子の期待値は、次のモンテネカルロ推定値 $f(E ; \tau)$ で近似できます。

$$
\left\langle F_{t}\right\rangle_{\psi} \approx \frac{1}{M} \sum_{x} M_{x} f\left(E_{x} ; \tau\right)
$$

本論文では、組み合わせ最適化問題を、対角線QUBO（Quadratic Unconstrained Binary Optimization）ハミルトニアンで表現します。このハミルトニアンでは、固有基底が計算基底(computational basis)となり、エネルギーが効率的に計算できます。そのため、フィルタリング演算子の期待値は、計算基底の量子状態をサンプリングすることで近似することができます。

各ステップ $t$ において、サンプルは、 $\left\langle F_{t}^{2}\right\rangle_{\psi_{t-1}}$ を計算するのに用いられ、また、平均エネルギー $\langle\mathcal{H}\rangle_{\psi_{t-1}} $ を計算するのにも用いられます。 $t$ が増加するのに従って、平均エネルギーは減少することが期待され、基底状態をサンプリングする確率が増加することが期待されます。このように、 F-VQE では、平均エネルギーとエネルギー基底状態をサンプリングする機会の増加を、さらには、追加のコストなしに基底状態をもとめることができます。

$F-VQE$ の最小化プロセスは、$\mathrm{VQE}$ の一般化と考えることができます。 $\mathrm{VQE}$ における損失関数は、平均エネルギー $\langle\mathcal{H}\rangle_{\psi(\boldsymbol{\theta})}$ です。 分析的勾配降下は、F-VQE における次のフィルタリング演算子を作用させることと等価です。

$\lambda$ の採用

コスト関数と勾配は，フィルタリング演算子の期待値を介して，パラメータ$\tau$に依存します．各最適化ステップにおいて、勾配ノルムをある望ましい大きな固定値にできるだけ近づけるように、$\tau$を動的に適応させます。これにより、勾配消滅防ぎ、固定回の測定でより正確にその値を決定することができます。

各最適化ステップで、勾配ノルムと $\tau$ の依存性 $g(\tau) \equiv\left|\left.\nabla \mathcal{C}_{t}(\tau)\right|{\boldsymbol{\theta}_{t-1}}\right|^{2}$ が、勾配ノルムが、$\tau_t$ ある閾値 $g_c > 0 $ より小さくて、より近づくようにするために使われます。各最適化ステップにおいて、そのような値 $\tau_t$ は、$g(\tau_t) = g_c$を解くことによて得られます。$\tau=0$ のときは、フィルタリング演算子が恒等演算子となるので、$g(0)=0$ です。より大きな $\tau$ にたいしては、勾配ノルムは、勾配回路と基底状態のオーバーラップできまる有限の値で飽和します。これを考慮すると、 $\tau$ は、以下のように決めることができます。勾配ノルムを　$\tau$ を評価しながら、(i) 上限 $\tau_u > \tau_t$ が、$g\left(\tau_{u}\right)>g_{c}$ となるまで大きくする、または、(ii) $g(\tau)$ が定数に収束するまで大きくる。

この発見的手法は、勾配を定数で単純に再スケーリングすることとは異なることを強調しておきます。図に示すように、各偏微分は$\tau$の関数として非自明に変化します。さらに、シミュレーションでは、最適化のステップや問題が異なっていても、勾配ノルムが$\tau$に一貫して依存していることを確認しています。

パラメータ$tau$の関数としての勾配。13量子ビットのMaxCut問題の1つについて、アンサッツ回路の4つのパラメータに対する勾配ノルムと偏微分の絶対値をプロットしたもの。
偏微分は，量子ビット1の最初のパラメータ（緑の破線），量子ビット1の最後のパラメータ（マゼンタの点線），量子ビット13の最初のパラメータ（黄色の連続），量子ビット13の最後のパラメータ（赤の破線-点線）に対応している．これらの最適化ステップで選択された$\tau_{t}$の値は，灰色の縦線で示されている．

因果コーン (Causal cones)

観測値の因果コーンは、期待値に実際に影響を与えるアンザッツ回路の量子ビットとゲートのみで構成される量子回路です。一般に、因果コーンは局所的な観測値の期待値の計算を単純化することができます。この単純化は、局所演算子の因果コーンの外側では、ユニタリーゲートがその隣接部分と相殺されるという事実に基づきます。

下の図は、隣り合う2つの量子ビットと、隣り合わない2つの量子ビットをサポートする観測量の因果コーンをそれぞれ示しています。因果コーンの内側にある量子ビットとゲートだけを実験的に準備する必要があります。なお、離れた量子ビットに対応する観測量の場合、因果コーンは2つの分離可能な因果コーンに分かれ、それぞれ独立してハードウェアで実現することができます。因果コーンは、観測量のサポートが小さい場合、ゲートと量子ビットの数を減らすことができます。

フィルタリング演算子、指数フィルタ、べき乗フィルタ、チェビシェフフィルタに因果関係のあるコーンが利用できることがわかります。指数フィルタ $\exp (-\tau \mathcal{H})$は、2つの局所項の積と等価であり、近似を加えれば独立して処理することができます 。また、$\tau$の整数値に対するパワーフィルター$(1-\mathcal{H})^{\tau}$は、多くても$2 \tau$-局所(local) 項の和と等価であるため、より単純な期待値の和から全体の期待値を決定することができます。同様に、チェビシェフフィルターの期待値は、チェビシェフフィルターの演算子が次数$\tau$の多項式であることから、多くても$2 \tau$-局所(local) 観測値の期待値の和を用いて計算することができます。

F-VQEのまとめ

VQEは、アンサッツ回路に制限がなく、量子化学や組み合わせ最適化において強力な手法です．しかし，最適化問題では，最適ではない解を生成する傾向があります。
QAOAは 断熱的量子計算やトロッター量子計算にヒントを得た特殊なアンサッツ回路を用いています。一般的にQAOAアンサッツは、現在の量子ハードウェアでは演算が困難な長さの回路のを必要とします。QVFとF-VQEにはアンザッツに制限がないため、対象とする量子ハードウェアに最も適したアンザッツを使用できることです。