Distance calculation と Grover optimization に関する一考察

今回の記事は、考察であり、正確性は一切保証しません。

量子k-meanの論文 K-Means Clustering on Noisy Intermediate Scale Quantum Computers
を読んでいて、以下の記述が気になりました。

Distance calculations for K-means are done using this method and the nearest centroid is found using Grovers Optimization [11] subroutine.

解説すると、この論文ではK-meanアルゴリズムにおける距離（分類したいデータと現状の重心たちとの距離）を量子回路で計算しています。¹
距離計算の結果は、量子ビットが$0$である確率という測定結果として得られます。（古典情報です）
k-meanで本当にやりたいのは、距離の数値のリストを得ることではなくて、その中で最小を与えるindexを知ることです。
それがGroverのアルゴリズムでできる　というのがこの論文での主張で、それは正しいのですが、教科書的なGroverのアルゴリズムでは足りません。
もちろん文献を調べれば"答え"があると思うのですが、今回はここを自分なりに考えてみたいと思います。

Groverのアルゴリズムで最小値を探すには？

Groverのアルゴリズムは、解であるものを量子並列に検証・マーキングしながら干渉させることで
最終的に解だけを生き残らせるアルゴリズムです。
解は複数あっても構いませんが、解の個数は既知であることが前提です。
とはいえ既知でない場合は、QAEなどの方法で推定することは出来ますので、それほど厳しい制約ではありません。
(これをQuantum counting と呼ぶことがあります。そのうち記事にします）

しかしこれで最小値を見つけるにはどうしたらいいのでしょう？
与えられた数値が最小値であるかどうかを検証するオラクル　というのは、明らかに最小値を知っていないと無理そうに思えます。
解を知らないと作れないオラクルは意味がありません。（以下の過去記事も参照下さい）
Groverのアルゴリズムと、解を知らないオラクル

しかしGroverアルゴリズムを少し拡張するだけで、この問題を回避できます。
それがDHアルゴリズムです。

DHA (Durr and Hoyer Algorithm)

DHアルゴリズム(DHA)は、DurrとHoyerが提案した最小値探索Groverアルゴリズムです。
Durr and Hoyer, "A Quantum Algorithm for Finding the Minimum"
最小を探したいことは割とあるので、DHAはすごく重要なのですが、あまり教科書や解説記事には出てこない気がしますね。²

DHAのアイデアは単純で、反復法により徐々に探索範囲を狭めて追い込んでいくものです。
私もあいまいな理解ですが、概ね以下のようなものです。³

1. 数値のリストからランダムに１つ選んでくる
2. 選んだ数値より小さい数値を持つデータたちをまとめてマーキングする（オラクル）
3. Grover増幅し、測定する。マーキングされた状態のどれか１つが得られる。これは1.で選んだ数値より小さい。
4. 3.で得た数値を基準として、2~3を繰り返す。値が更新されなくなったら最小値。

この場合、オラクルに要求されるのは
「与えられた値以下のものをマーキングせよ」
なので、最小値を知っている必要はありません。

DHAはGrover Adaptive Search (GAS)とも言われるみたいです。
GAS in qiskit document(https://qiskit.org/documentation/tutorials/optimization/4_grover_optimizer.html)

オラクルの構成は？

しかし、以前として「どうやってオラクルを作るのか」がはっきり理解できません。
自分なりに考えてみます。

まず、距離の値を$N$ bitでデジタル化します。例えば $N=3$としてみます。
距離のリスト(2進数)が、
1) 000
2) 001
3) 101
4) 111
だったとしましょう。ランダムに選んだものが 3)の 101 であったとします。
101より小さい値であるためには、
1. 左端ビットが0であれば、無条件に該当。1であれば次の桁を見る。
2. 真ん中ビットを見て1であれば非該当。0であれば、次の桁を見る。
3. 右端のビットを見て、0であれば該当。1であれば非該当。
このような段階的な判定に帰着させられます。
これは明らかに論理回路で組めますので、量子ゲートに出来ます。⁴

あとはGrover増幅後にサンプリングすればよいです。
得られた値を基準値として、同じことを繰り返します。(DHA)

これだけだと最小の距離の数値がわかるだけなのですが、データのindex番号も補助ビットとして条件づけておいて

$| index \rangle \otimes |distance \rangle$
としておけば問題ないでしょう。

結論

あっているかはわからないが、自分で処理のフローを考えるのは面白い。

---

1. 量子的にやる利点は計算量です。$N$量子ビットの状態は$2^{N}$次元複素ベクトルとして扱えるので、ここに内積を計算させたいベクトルを埋め込んでやります。ベクトルの次元が$N$であったとしても量子ビットが$\log_{2}(N)$個あれば埋め込めてしまいます。距離計算はいくつかの量子ゲート操作で半ば自動的に進ませることができ、最後に測定で距離の数値を抽出できます。 ↩

2. 例えば、とある最尤推定の論文でしれっと出てきました。 ↩

3. Grover増幅は増幅回数が適切でないといけません。注意です。 ↩

4. ぶっちゃけ、$y_{binary}-101$ を古典的に計算してから埋め込むとずっと楽が出来る気もしますが、、 ↩