QUBO, Ising Hamiltonian ve VQA
Genelde kombinatoryal optimizasyon problemlerinin, Ising Hamiltonian'la çok basit bir eşlemesi olan QUBO'ya dönüştürüldüğünü anlıyorum. Ising Hamiltoniyanlar, sırayla, hesaplama temelinde köşegen olmak gibi istenen özelliklere sahiptir ve temel durum, hesaplama temel vektörlerinden biridir. Dolayısıyla, durumu hesaplama temelinde ölçmek ve bit dizisi çözümünü elde etmek kolaydır.
Sorun, Ising Hamiltonian ve QUBO'nun kendi terimleriyle ikinci dereceden olması ve en fazla 2 vücut etkileşimine izin vermesidir. Son zamanlarda, optimizasyon problemi ( 56153'ün sadece 4 kübitlik kuantum çarpanlarına ayırma) olarak ifade edilen tamsayı faktörleme hakkında , maliyet fonksiyonunun üçüncü derece polinom olduğu bir makaleye rastladım . Bunu 2 vücut etkileşimine indirgeyebildim ve böylece QUBO sorununu çözebildim, Ising Hamiltonian ile eşleştirebildim ve QAOA kullanarak IBM makinelerinde çözebildim. Ancak, 3. dereceden 2. dereceye polinom arasındaki bu dönüşüm bana ekstra kübitlere mal oluyor.
O halde 3/4 beden etkileşiminiz olduğunda genel yaklaşım nedir, örneğin bu makalede bağlandığım gibi? Bunun yazarları ve alıntı yaptıkları önceki eserlerin yazarları bunun QUBO olmadığı gerçeğiyle ilgilenmiyorlar. Bu gibi durumlarda Ising Hamiltonians ve QUBO'lara alternatif var mı? Pauli Z operatörlerinin tensör ürünlerine ayrıştırılabildiği sürece QAOA / VQE için Hamiltonian'ın herhangi bir biçimini (zorunlu olarak Ising değil) kullanabileceğimiz doğru mu?
Yanıtlar
Bu makaledeki [ 1 ] tanımda , maliyet Hamiltoniyen Ising Hamilton vakası ile sınırlı değildir. Makalenin [ 1 ] de belirtilen "genel yaklaşım için bir cevabı var.$3/4$ ($n$) vücut etkileşimleri ".
[ 1 ] ' den doğrudan bir alıntı :
İkili değişkenlerde bir polinom olan klasik bir maliyet fonksiyonundan $x_1 , . . . , x_n $bir Hamiltonian inşa edebiliriz $H_C$ açık $n$ önce maliyet fonksiyonunu değişkenler açısından yeniden yazarak kübit'ler $z_i \in \{−1, 1 \}$, nerede $x_i = (1 − z_i )/2$ bir polinom elde etmek için $f (z) = \sum_{C \subset \{1,...n\}} \alpha_C \prod_{j \in C} z_j$ ve sonra her bir oluşumunu değiştirerek $z_i$ Pauli operatörü ile $\sigma_i^z$. Böylece,$H_C$ köşegendir $\sigma_z$temel ve şeklini alır
$$H_C = \sum_{C \subset \{1,...,n\}} \alpha_C \bigotimes_{j \in C} \sigma_i^z \tag{2}$$
nerede $C$ tüm kübitlerin bir alt kümesidir ve $\alpha_C$ alt kümedeki kübitler arasındaki çok gövdeli bağlantı için gerçek bir katsayıdır $C$.
Bu, klasik bir maliyet fonksiyonumuz varsa$f(x) = 4 x_1 +6x_1 x_2 - 2x_2 x_3 x_4$değiştirmeliyiz $x$s ile $z$s ve elde edin:
$$f(z) = 2(1 - z_1) + 3 (1 - z_1) (1 - z_2) - (1 - z_2) (1 - z_3) (1 - z_4)$$
Değiştirmeyi basitleştirdikten sonra $z$s ile $\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$$
ve bitti. Bu prosedürün QUBO için de işe yarayacağını unutmayın.$\rightarrow$Ising Hamiltonian (bu cevaba bakınız ). Bu şekilde, istenen (QAOA'da) özellik ile maliyet Hamiltoniyenini inşa edebileceğiz:
$$H_C |x\rangle = f(x)|x\rangle$$
nerede $x = x_1 x_2 x_3 x_4$ bir bit dizisidir.
Hamiltonian'ın maliyetine bir örnek$3$E3LIN2 problemi ([ 2 ] Denklemi için bu yazıda [ 2 ] kübitler arası gövde bağlantısı bulunabilir .$6$ biraz değiştirilmiş notasyonlarla):
$$ H_C = \frac{1}{2} \sum_{a < b < c} d_{abc} \sigma_a^z \sigma_b^z \sigma_c^z \tag{6}$$
nerede $d_{abc}$ dır-dir $0$ veya $+1$ veya $-1$, $a$, $b$ ve $c$ kübit dizinleridir.
[ 1 ] Z. Wang, S. Hadfield, Z. Jiang, EG Rieffel, "MaxCut için Kuantum Yaklaşım Optimizasyon Algoritması: Fermiyonik Bir Görünüm"
[ 2 ] E. Farhi, J. Goldstone, S. Gutmann, "Sınırlı Bir Oluşum Kısıtlaması Problemine Uygulanan Kuantum Yaklaşık Optimizasyon Algoritması"