Backpropagation scaling in parameterised quantum circuits
/icons/hr.icon
和訳
0. Abstruct
バックプロパゲーションアルゴリズムの発見は、機械学習の歴史において最も重要な瞬間の1つであり、モデル評価とほぼ同じ計算コストで勾配を計算できる能力により、大規模なニューラルネットワークのトレーニングを可能にしました。その重要性にもかかわらず、パラメーター化された量子回路の勾配評価における同様のバックプロパゲーションのようなスケーリングは、いまだ実現していません。
現在、最も一般的な方法は、回路パラメーターの数に応じてサンプリングする回路の数が増えるため、実際には大規模な量子回路のトレーニングが法外に高価になっています。本稿では、古典的にシミュレート可能であるとは知られていない構造化された回路のクラスを導入し、大幅に少ない回路で勾配推定を可能にすることで、この問題に対処します。
最も単純なケース（パラメーターが可換な量子ゲートに入力される場合）では、これらの回路は勾配、高次の偏導関数、およびフィッシャー情報行列の高速推定を可能にします。さらに、古典的なバックプロパゲーションに沿った勾配推定のスケーリングを示す特定のパラメーター化された回路群が存在し、それにより大規模なトレーニングが可能になります。16量子ビットの玩具分類問題では、このような回路は他の方法と比較して競争力のある性能を示し、トレーニングコストを約2桁削減します。
1. Introduction
最適化や機械学習における多くのタスクは、一連のパラメーターに対する連続的なコスト関数の最小化を伴い、勾配ベースのアプローチが、しばしばそのようなタスクに取り組むための有力な手段となります。これらの手法では、勾配を評価できる効率が極めて重要です。なぜなら、それがアルゴリズムの実行時間とコストによって決まる最適化ステップの実用的な上限を設定するからです。例えば、機械学習におけるニューラルネットワークモデルの成功は、多くの場合、バックプロパゲーションによる高速な勾配評価の可能性に起因しており [1, 2)、これによりモデルが今日見られるような巨大なサイズにスケールすることを可能にしています。
量子計算の分野では、最適化や機械学習タスクのための強力な新しいアンザッツ（試行関数）を提供するものとして、パラメーター化された量子回路に大きな期待が寄せられています [3, 4)。そのため、量子回路の勾配を推定する能力に依存する多種多様な変分量子アルゴリズムが設計されてきました。それにもかかわらず、高速な勾配推定が可能な回路のクラスは依然として不足しています。現在、勾配を計算する標準的な方法はパラメーターシフト法 [5, 6, 7, 8)であり、最も単純なケースでは、モデル内のすべてのパラメーターについて、2つの異なる回路からサンプリングする必要があります。このため、勾配を推定するコストは、関数自体を評価するよりも著しく高くなる可能性があります。これは、関数自体を評価するのに必要な時間とメモリとほぼ同じで、正確な勾配計算を可能にするバックプロパゲーション [2)のような自動微分法とは対照的です。 さらに、量子モデルの確率性により、勾配推定の精度（1/精度2）に反比例する追加のサンプリングコストが発生します[6)。パラメーターの数が多い問題では、これがすぐに勾配推定を実質的に法外な費用にしてしまいます。具体的な数値で見てみましょう。1000個のデータポイントを持つデータセットを、1000個のパラメーターを持つ量子モデルで1エポックの勾配降下を行い、$ 10^{-4}の勾配精度を達成するには、$ 2 \times 10^{14}回の量子回路ショットが必要になります。クロック速度1MHzで連続稼働する量子コンピューターを使用した場合、これには約6年かかります。
これらのことから、変分量子アルゴリズム、特に量子機械学習アルゴリズムは、パラメーターシフトルールよりも高速な勾配推定を可能にするアンザッツを切実に必要としていることが示唆されます。この目的のために、多くの研究が他の方法 [9, 10, 11, 12, 13, 14, 15)やフレームワーク [16)を探求してきました。しかし、一般的で非構造化なパラメーター化された量子回路の場合、高速な勾配推定は困難であるように思われます。なぜなら、未知の入力状態の単一コピーにしかアクセスできない場合、バックプロパゲーションのようなスケーリングは不可能であることが知られているからです [17)。したがって、この方向で進歩するためには、特定の回路構造に焦点を当てる必要がありそうです。これはある意味で驚くべきことではありません。成功する機械学習モデルの構築は、常に高速な最適化に適したうまく設計された構造を見つけることでした。量子モデルに移行しても、この状況が変わると期待すべきではありません。
本研究では、パラメーターシフト法よりも高速な勾配推定を可能にする、パラメーター化された量子回路のクラスを提案します。最も単純なケース（セクション3）では、これらの回路は互いに可換なパラメーター化されたゲートを特徴とし、これを「可換ジェネレーター回路」と呼びます。これらの回路のゲートは可換であり、同時に対角化できますが、入力状態と最終的な測定がこの基底である必要はないため、古典的なシミュレーションはできません。可換ゲートへの制限により、勾配推定を回路のパラメーター全体で並列化できます。パラメーターシフト法が各パラメーターに対して一対の回路からのサンプリングを必要とするのに対し、私たちの方法は、同じ数の量子ビットを持つ単一の回路からサンプリングすることで、同じ精度で完全な勾配ベクトルを返します。これにより、回路ショット数を大幅に削減でき、場合によってはバックプロパゲーションのスケーリングに匹敵します。驚くべきことに、このクラスの回路は、フィッシャー情報行列や特定の次数のすべての偏導関数を推定する際にも並列化を可能にします（ただし、次数とともに分散が指数関数的に増加します）。これはニューラルネットワークモデルですら提供できないものであり、効率的な高次最適化手法の可能性を開きます。
セクション4では、可換ゲートの制限を超えて、非可換なパラメーター化ゲートを持つ回路のクラスを設計する方法も示します。これらは可換ブロック回路と呼んでいます。これらの回路は特定のブロック構造を持つ必要があり、ブロック内ではゲートが可換でなければならず、異なるブロックのジェネレーターは固定された可換または反可換な関係を持つ必要があります。この追加された自由度により、このクラスのパラメーター化された回路は、可換なものよりも表現力が豊かになり得ます。このことは、これらのモデルの表現力の究極的な限界は何であるかという疑問を提起しますが、これは未解決の問題として残します。
次に、可換ジェネレーター回路の具体的な例を2つ提示し、偏導関数の評価に必要な対応する回路を導出します（セクション5）。これらの回路の1つは、量子ビットの並進置換に対して等変な層を持つ量子モデルを構築するための基礎として使用されます。このモデルは、非可換ゲートを持つ別の並進等変モデルや、並進対称性を持つ分類タスクにおける量子畳み込みニューラルネットワークと比較されます（セクション6）。16量子ビットモデルのシミュレーションにより、可換ジェネレーターを持つ回路が、3つのモデルの中で最も低いトレーニングコストと最高のテスト精度を達成し、桁違いに少ない回路ショット数で済むことを示します。
今後、私たちの研究が、一般的な非構造化量子回路を最適化や機械学習の有効なアンザッツと見なすことから脱却し、適切に設計され目的に合った構造を持つ量子回路アンザッツの必要性と可能性の両方を強調することを願っています。
/icons/hr.icon
2. パラメータ化された量子回路における逆伝播スケーリング
本研究で検討する回路のクラスは、古典的にパラメーター化された量子回路の形をとっています。
https://scrapbox.io/files/688b620ac7cea0e3c0cdb942.png
ここで、
$ U(\theta) = \Pi_{j=0}^{L} e ^ {-i\theta_j G_j}
$ = u_L(\theta_L) \cdot u_{L-1}(\theta_{L-1}) \cdot ... \cdot u_0(\theta_0) (松本解釈用)
は、エルミート生成子$ G_jと古典パラメーター$ θを持つユニタリ演算子であり、$ Hは何らかのエルミート観測量です。ハードウェア上では、$ Hを測定し、$ Mショットを収集することで、$ C(θ)の不偏推定値が、$ O(1/M)でスケーリングする分散とともに得られます。
ーーーーーーーーーーーーーーーーーーーーー
(パラメータシフト法の話)
このような回路の勾配$ ∇C(θ)を計算するための最も一般的なアプローチは、パラメーターシフト法を用いることです [18, 5, 6, 7, 8, 19)。2つの異なる固有値を持つゲート生成子の最も単純なケースでは、モデル内のすべてのパラメーターについて2つの回路を評価することで、勾配の不偏推定値を得ることができます。
https://scrapbox.io/files/688b64d72f30bbedd5f7cc70.png
ここで、$ α_jは j 番目の成分以外すべてゼロのベクトルです。$ C(θ)と同じ精度で勾配の推定値を得るには、各回路から $ Mショットを取得する必要があり、その結果、各成分の分散は$ O(1/M)となります。したがって、この方法による勾配推定のコストは、学習可能なパラメーターの数に比例する係数分だけ、$ C(θ)の推定コストよりも大きくなります。
[17)と同様の考え方で、私達は バックプロパゲーションスケーリング を持つメソッドを、$ C(θ)の評価と比較して、パラメーター数における対数的なオーバーヘッドで、$ C(θ)と同じ精度で$ ∇C(θ)の不偏推定値を返すものと定義します。
ーーーーーーーーーーーーーーーーーーーーー
定義2.1 Backpropagation Scaling
形式 (1) の$ n個のパラメーターを持つパラメーター化された量子回路を考えます。この回路から$ Mショットをサンプリングすることで、$ C(θ)の不偏推定値が分散$ O(1/M)で得られます。この手続きの時間計算量を$ TIME(C)、空間計算量を $ MEM(C)とします。また、要素ごとの分散が$ O(1/M)である勾配の不偏推定値を得るための時間計算量を$ TIME(∇C)、空間計算量を$ MEM(∇C)とします。このとき、勾配計算手法がバックプロパゲーションスケーリングを持つとは、以下の条件を満たす場合を指します。
$ TIME(∇C) ≤ c_t TIME(C) (4)
かつ
$ MEM(∇C) ≤ c_m MEM(C) (5)
ここで、$ c_t,c_m=O(log(n))です。
本研究では、このようなスケーリングを達成する回路群と勾配計算手法を提示します。さらに、$ c_t,c_mが定数スケーリングを持つ例も示します。
/icons/hr.icon
3. 可換生成子回路
本研究で私たちが検討する最初のクラスの回路は、任意の入力状態準備、互いに可換なパラメーター化されたゲート、およびオブザーバブルの測定で構成されます（図1(a)参照）。これらの回路は次のように与えられます。
https://scrapbox.io/files/688b687ea675b39618089a65.png
ここで、$ Vは任意のユニタリ演算子、$ Hはオブザーバブル、そしてパラメーター化されたユニタリ演算子$ U(θ)は以下の形式を取ります。
https://scrapbox.io/files/688b68a13534d52f681742d0.png
ただし、すべての$ j,k ∈ \lbrack n \rbrack $ (\lbrack n \rbrack ={1,…,n} ) について、$ \lbrack G_j,G k\rbrack = 0、すなわち$ G_jと$ G kは互いに可換であるとします。さらに、オブザーバブル$ Hについて、各 $ G_jと$ Hの関係が $ \lbrack H,G_j \rbrack = 0（可換）または $ \lbrace H,G j\rbrace=0（反可換）のいずれかである場合に限定します。例えば、すべての生成子とオブザーバブルがパウリ演算子のテンソル積である場合がこれに該当します。多くのアプリケーションでは、この形式のオブザーバブルの合計を評価しますが、これは任意のエルミート多量子ビット演算子がパウリ基底で分解できるためです。ただし、ここでは簡潔にするため単一の$ Hのみを考慮します。合計に対する勾配の評価は、通常通り個々のオブザーバブルの寄与を合計することで達成できます。 そのような回路を可換生成子回路と呼ぶ。このクラスの回路は、回路の冒頭にある任意のユニタリー演算子$ Vのため、計算量理論で一般的に研究されている「可換量子回路」[20, 21)とは異なる点に注意が必要だ。興味深いことに、このクラスの回路では、次の意味で勾配を並列に推定することができる。
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
定理1
式(6)の形式を持つ可換生成子回路$ C(\theta)を考える。このとき、勾配
$ \nabla C(\theta) = \left(\frac{\partial C}{\partial\theta_1}, \frac{\partial C}{\partial\theta_2}, \cdots, \frac{\partial C}{\partial\theta_n}\right) \tag{8}
の不偏推定量は、$ Cと同じ数の量子ビットを持つ単一の回路$ C'を古典的に後処理することで得られる。$ C'の測定統計はすべての導関数を同時に推定するために使用されるため、各導関数推定量の分散は$ O(1/M)となる。ここで$ Mは、$ C'の評価に使用されるショットの総数である。
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
生成子が可換であるため、
https://scrapbox.io/files/688cb061501a4fa0f7078ede.png
となる。ここで、$ |ψ_0\rangle = V|0\rangleである。したがって、$ θ_jに関する勾配は、$ |ψ_0\rangleに対するオブザーバブル$ O_j = i \lbrack G_j, H \rbrackの期待値を測定することに対応する。これは、$ G_jと$ Hが可換であればゼロになるため、ここでは$ Hと反可換な生成子のみを考慮すればよい。このような2つの生成子$ G_j, G_kを考えよう。反可換性を用いると、$ i \lbrack G_j,H \rbrack = 2iG_jHとなるため、 https://scrapbox.io/files/688cb1c27f19c7ba9b90379e.png
この結果から、演算子$ O_jは互いに可換であり、同時に対角化できることがわかる。$ O_jが対角化される基底を$ {|\psi_i\rangle}とすると、
$ O_j = \sum_i \lambda_i(O_j) |\psi_i\rangle\langle\psi_i| \tag{11}
となる。ここで、$ {\lambda_i(O_j)}は$ O_jに対応する固有値である。勾配を並列に推定するために、$ C(\theta)と同じ回路を使用しますが、基底$ {|\psi_i\rangle}で測定します。つまり、分布
https://scrapbox.io/files/688cb28fed5342cf1c7cabd1.png
からサンプリングを行います。式(11)と(9)から、
https://scrapbox.io/files/688cb2a4e295ed00886c589a.png
となります。
この$ \frac{\partial C}{\partial\theta_j}を推定するには、分布$ P(i)からM個のショット$ {i_1, \cdots, i_M}をサンプリングし、期待値(13)を以下によって推定します。
$ \frac{\partial C}{\partial\theta_j} \approx \frac{1}{M} \sum_{k=1}^M \lambda_{i_k}(O_j) \tag{14}
中心極限定理によれば、有界な確率変数の標本平均の分散は$ O(1/M)でスケールするため、これにより主張が証明されました。
オブザーバブル$ O_jが対角化される基底$ {|\psi_i\rangle}は必ず存在しますが、この基底に回転させるためのユニタリー演算子を見つけたり実装したりするのが困難な場合があります。しかし、場合によってはこの手順は単純なものです。そのため、私たちは生成子とオブザーバブルがパウリ積（$ {I, X, Y, Z}の演算子のテンソル積）である回路にしばしば焦点を当て、このクラスの回路を可換パウリ生成子回路と呼ぶことにします。これらの回路では、演算子$ O_jもパウリ積となるため、対角化を行うユニタリー演算子を効率的に実装できます。
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
系1
N量子ビットの可換パウリ生成子回路を考える。このとき、勾配は、$ Cと同じ数の量子ビットを持ち、かつ$ Cよりも深さが最大で$ O \left( \frac{N}{\log N} \right)だけ大きい回路$ C'によって並列に推定できる。
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
上記の深さの限界は[22, Cor 1.2)に由来する。なお、追加の補助量子ビットを犠牲にすれば、深さをさらに$ O(\log N)まで減らすことも可能である。この場合、対角化を行うユニタリー$ Dはクリフォード演算子となり、したがって偏導関数は、量子ビットの部分集合におけるパウリ$ Z演算子の積を評価することに対応する。安定化演算子の集合を同時に対角化するための効率的なアルゴリズムも存在する[23, 24, 25)。また、多くの構造を持つ演算子の集合については、適切な回路を手作業で見つけることもできる（第5.1節で示す）。
上記の深さの限界は$ Nに依存するが、生成子とオブザーバブルの選び方によっては、対角化を行うユニタリーは一定の深さとなる。このような場合、勾配の評価はモデル評価と同じ計算コストで行うことができ、バックプロパゲーションのスケーリングが可能になる。第5節では、このような回路の2つの例を見ることにする。
3.1 高次偏導関数
定理1の証明と同じ手順を繰り返すことで、任意次数の偏導関数も並列に推定できることがわかる。
定理2
定理1と同様の可換生成子回路$ C(\theta)と固定整数$ tを考える。
$ Cのすべての$ t次の偏導関数の不偏推定量は、$ Cと同じ量子ビット数を持つ単一の回路 $ C'を古典的に後処理することで得られる。
各導関数推定量の分散は$ Mを$ C'の評価に使ったショット数とすると$ O(1/M)に比例する。
証明
まず$ t=2の場合を考える。
式 (9) をもう一度微分すると、二階偏導関数は次のようになる：
https://scrapbox.io/files/689dc1d45c337d25da876ec6.png
ただし、$ G_jと$ G_kがどちらも$ Hと反可換である場合に限り非ゼロであり、それ以外の場合はゼロである。
非ゼロの場合には$ [G_j G_k H, G_l G_m H] = 0 が成り立つため、これらの偏導関数も単一の基底で行った測定結果を後処理することで並列に測定できる。
このパターンを続け、マルチインデックス$ \alpha \in [n]^t を定義すると、$ t次偏導関数は次のようになる：
https://scrapbox.io/files/689dc26dbf7359a3d86bfb7e.png
ここで、$ G_{\alpha_1}, \dots, G_{\alpha_t}がすべて$ Hと反可換である場合に限り非ゼロであり、それ以外はゼロとなる。
非ゼロの$ t次導関数は、以下の観測量を測定することで評価できる：
https://scrapbox.io/files/689dc2d8712fa6e30b1a165f.png
さらに$ [O_\alpha, O_{\alpha'}] = 0 が成り立つため、$ t次偏導関数も$ C'に対するショット数の逆数に比例する分散で並列に取得できる。
ただし、係数$ 2^tのため、推定量の分散は一般に導関数の次数とともに指数関数的に増加する。そのため、実用上は比較的低い次数までしか到達できない。それでも、この方法は一次の手法と比べても量子リソースに定数倍程度のオーバーヘッドで二次の近似最適化を可能にする。
最後に、式 (17) の形からは定理2よりもさらに強い主張が導けることを付記しておく。
！！！残り未翻訳
/icons/hr.icon
4. 可換ブロック回路
このたび、高速な勾配推定という特性を維持する、より大きなクラスの回路を提示します。これらの回路は、可換生成子回路と類似した構造を持ちますが、パラメーター化された部分が可換ゲートのブロックで構成されています（図2参照）。これらのブロックは、あるブロック内の生成子は可換である一方で、異なるブロック間の生成子は固定された交換関係（可換または反可換）を持つように作られています。より厳密に言えば、$ g_1 = \{ G^1_{j} \}と$ g_2 = \{G^2_{k}\}が2つの異なるブロック$ j, kからの生成子である場合、以下のいずれかの関係が成り立ちます。
https://scrapbox.io/files/688cb91a00275686ea8d0154.png
したがって、このクラスのB個のブロックを持つ一般的な回路は、式(6)の形式を持ち、
https://scrapbox.io/files/688cb96c355e914549c25a67.png
と表されます。ここで、ブロック$ g_b = \{G^b_{j}\}は、上述の交換構造に従います。このような回路を可換ブロック回路と呼びます。これらの回路の勾配は、パラメーターの数ではなく、ブロックの数に応じてスケールする数の回路を用いて評価することができます。これは次の意味においてです。
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
定理5
！！！未翻訳
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
これから勾配を推定する手順を説明します。詳細な証明は付録Bをご覧ください。b番目のブロックの勾配を推定するには、ユニタリー演算子の線形結合に基づいた手法[30)を使用します。ここではb番目のブロックに焦点を当てるため、生成子のブロックインデックスを省略し、$ G_j \equiv G^b_{j}とします。ここで、
$ |\psi_b\rangle = U_b(\theta_b) \cdots U_2(\theta_2)U_1(\theta_1)V|0\rangle \tag{25}
と定義します。これは、b番目のブロックを通過した後の状態です。
また、
https://scrapbox.io/files/688cbc4f4a3ca91b62084612.png
と定義します。
まず、2つのエルミートオブザーバブルの集合を定義します。$ G_jと$ Hが可換であるような$ jについて、$ O_0 = \{O_j\} = \{2G_jH\}と定義します。一方、$ G_jと$ Hが反可換であるようなjについて、$ O_1 = {O_j} = {2iG_jH}と定義します。可換生成子回路とは異なり、このb番目のブロックの後に回路$ W_bが適用されるため、$ Hと可換である$ O_0の生成子も勾配に寄与します。$ O_0または$ O_1内のすべての生成子は互いに可換であるため、同時に対角化できることに注意してください。まず、$ O_1に含まれる添え字jに対応する偏導関数に焦点を当てます。図2 (b)に示す回路を実装して量子状態$ |\psi\rangleを生成します。ここで、$ Dは$ O_1のオブザーバブルを対角化するユニタリー演算子であり、$ \tilde{W}_bは
https://scrapbox.io/files/688cbd47e87f1e9c4d00c597.png
で定義されます。
例として、ブロックbの生成子が$ W_b内のすべての生成子と反可換である場合、 $ \tilde{W}_bは$ W_bと同じ形式を持ち、$ θが$ -\thetaに置き換えられます。この回路について、
https://scrapbox.io/files/688cbdb3b1074140a4a61dc7.png
$ Dが$ O_jを対角化するため、偏導関数は(14)と同様に、事後処理を介して計算基底で回路をサンプリングすることによって得られます。$ O_0の場合もプロセスは同じですが、回路中の$ W_bを$ iW_bに置き換え、$ O_0内の可観測量を対角化するユニタリ$ Dを使用します。したがって、各ブロックには2つの回路が必要ですが、最終ブロックでHと可換な生成子勾配はゼロになるため、$ 2B−1個の回路で十分です。
ーーーーーーーーーーーーーーーーーーーーー
4.1 可換ブロック回路による表現力の向上
可換ブロック回路が図1の単一ブロック回路と比較して表現力が向上しているかという疑問が当然生じますが、これは事実です。表現力を定量化するために、ゲート生成子の動的リー代数[31)を以下のように定義して使用します。
https://scrapbox.io/files/688f20832dcdc1b9c7c203bd.png
/icons/hr.icon
関連