QUBO、Ising Hamiltonians、VQA

Oct 12 2020

通常、組み合わせ最適化問題は、イジングハミルトニアンへの非常に単純なマッピングを持つQUBOに変換されることを理解しています。次に、Isingハミルトニアンは計算基底で対角であるという望ましい特性を持ち、基底状態は計算基底ベクトルの1つです。したがって、計算ベースで状態を測定し、ビット文字列ソリューションを取得するのは簡単です。

問題は、イジングハミルトニアンとQUBOがその項で二次であり、最大2つの身体の相互作用を可能にすることです。私は最近、最適化問題（4キュービットのみの56153の量子因数分解）として表される整数因数分解についての論文に出くわしました。ここで、コスト関数は3次多項式です。これを2つのボディの相互作用に減らして、問題をQUBOにし、イジングハミルトニアンにマップして、QAOAを使用してIBMマシンで解決することができました。ただし、次数3の多項式から次数2へのこの変換には、余分なキュービットがかかります。

たとえば、私がリンクしたこの論文のように、3/4の体の相互作用がある場合の一般的なアプローチは何ですか？これの作者、および彼らが引用する以前の作品の作者は、これがQUBOではないという事実に関心がありません。そのような場合、IsingHamiltoniansとQUBOに代わるものはありますか？Pauli Z演算子のテンソル積に分解可能である限り（計算ベースで対角になる）、QAOA / VQEに任意の形式のハミルトニアン（必ずしもイジングではない）を使用できるのは正しいですか？

回答

DavitKhachatryan Oct 12 2020 at 18:44

この論文の定義[ 1 ]では、コストハミルトニアンはイジングハミルトニアンの場合に限定されていません。論文[ 1 ]には、前述の「一般的なアプローチ」に対する回答もあります。$3/4$ （（$n$）身体の相互作用」。

[ 1 ]からの直接引用：

バイナリ変数の多項式である古典的なコスト関数から $x_1 , . . . , x_n $、ハミルトニアンを構築できます $H_C$ オン $n$ 最初に変数の観点からコスト関数を書き直すことによるキュービット $z_i \in \{−1, 1 \}$、どこ $x_i = (1 − z_i )/2$ 多項式を取得するには $f (z) = \sum_{C \subset \{1,...n\}} \alpha_C \prod_{j \in C} z_j$ 次に、の各発生を置き換えます $z_i$ パウリ演算子を使用 $\sigma_i^z$。したがって、$H_C$ で対角線です $\sigma_z$-基礎と形を取る

$$H_C = \sum_{C \subset \{1,...,n\}} \alpha_C \bigotimes_{j \in C} \sigma_i^z \tag{2}$$

どこ $C$ はすべてのキュービットのサブセットであり、 $\alpha_C$ サブセット内のキュービット間の多体結合の実係数です $C$。

これは、古典的なコスト関数がある場合、$f(x) = 4 x_1 +6x_1 x_2 - 2x_2 x_3 x_4$、交換する必要があります $x$と $z$sおよび取得：

$$f(z) = 2(1 - z_1) + 3 (1 - z_1) (1 - z_2) - (1 - z_2) (1 - z_3) (1 - z_4)$$

単純化した後、置換 $z$と $\sigma_z$s：

$$H_C = 4 I - 5 \sigma_1^z - 2 \sigma_2^z + \sigma_3^z + \sigma_4^z + 3 \sigma_1^z \sigma_2^z -\sigma_2^z \sigma_3^z -\sigma_3^z \sigma_4^z -\sigma_2^z \sigma_4^z + \sigma_2^z \sigma_3^z \sigma_4^z$$

完了しました。この手順はQUBOでも機能することに注意してください$\rightarrow$イジングハミルトニアン（この回答を参照）。このようにして、目的の（QAOAの）プロパティを使用してコストハミルトニアンを構築できます。

$$H_C |x\rangle = f(x)|x\rangle$$

どこ $x = x_1 x_2 x_3 x_4$ ビットストリングです。

コストハミルトニアンの例$3$-キュービット間のボディ結合は、E3LIN2問題のこの論文[ 2 ]で見つけることができます（[ 2 ]式。$6$ 表記を少し変更して）：