QUBO, Ising Hamiltonians dan VQA
Saya mengerti bahwa biasanya masalah optimasi kombinatorial diubah menjadi QUBO, yang memiliki pemetaan yang sangat sederhana ke Ising Hamiltonians. Ising Hamiltonian pada gilirannya memiliki sifat yang diinginkan menjadi diagonal dalam basis komputasi dan status dasar adalah salah satu vektor basis komputasi. Dengan demikian mudah untuk mengukur status dalam basis komputasi dan mendapatkan solusi string bit.
Masalahnya adalah bahwa Ising Hamiltonian dan QUBO adalah kuadrat dalam istilahnya dan memungkinkan paling banyak 2 interaksi tubuh. Saya baru-baru ini menemukan sebuah makalah tentang pemfaktoran bilangan bulat yang dinyatakan sebagai masalah pengoptimalan ( faktorisasi kuantum 56153 dengan hanya 4 qubit ), di mana fungsi biaya adalah polinomial derajat ketiga. Saya dapat mengurangi ini menjadi 2 interaksi tubuh dan dengan demikian membuat masalah QUBO, memetakannya ke Ising Hamiltonian dan menyelesaikannya di mesin IBM menggunakan QAOA. Namun, konversi antara polinomial derajat 3 ke derajat 2 ini membebani saya qubit tambahan.
Lalu apa pendekatan umumnya ketika Anda memiliki 3/4 interaksi tubuh, misalnya seperti yang saya tautkan dalam makalah ini? Penulis ini, serta penulis dari karya sebelumnya yang mereka kutip, tidak peduli dengan fakta bahwa ini bukan QUBO. Apakah ada alternatif untuk Ising Hamiltonians dan QUBO dalam kasus seperti itu? Apakah benar bahwa kita dapat menggunakan bentuk Hamiltonian apa pun (tidak harus Ising) untuk QAOA / VQE asalkan dapat diuraikan menjadi produk tensor operator Pauli Z (yang membuatnya diagonal dalam basis komputasi)?
Jawaban
Dalam definisi dari makalah ini [ 1 ] biaya Hamiltonian tidak terbatas pada kasus Ising Hamiltonian. Makalah [ 1 ] juga memiliki jawaban untuk "pendekatan umum untuk$3/4$ ($n$) interaksi tubuh ".
Kutipan langsung dari [ 1 ]:
Dari fungsi biaya klasik yaitu polinomial dalam variabel biner $x_1 , . . . , x_n $, kita dapat membangun Hamiltonian $H_C$ di $n$ qubit dengan terlebih dahulu menulis ulang fungsi biaya dalam bentuk variabel $z_i \in \{−1, 1 \}$, dimana $x_i = (1 − z_i )/2$ untuk mendapatkan polinomial $f (z) = \sum_{C \subset \{1,...n\}} \alpha_C \prod_{j \in C} z_j$ dan kemudian mengganti setiap kemunculan $z_i$ dengan operator Pauli $\sigma_i^z$. Jadi,$H_C$ adalah diagonal di $\sigma_z$-basis dan mengambil formulir
$$H_C = \sum_{C \subset \{1,...,n\}} \alpha_C \bigotimes_{j \in C} \sigma_i^z \tag{2}$$
dimana $C$ adalah bagian dari semua qubit, dan $\alpha_C$ adalah koefisien nyata untuk kopling banyak benda antara qubit dalam subset $C$.
Artinya jika kita memiliki fungsi biaya klasik$f(x) = 4 x_1 +6x_1 x_2 - 2x_2 x_3 x_4$, kita harus mengganti $x$s dengan $z$s dan dapatkan:
$$f(z) = 2(1 - z_1) + 3 (1 - z_1) (1 - z_2) - (1 - z_2) (1 - z_3) (1 - z_4)$$
Setelah menyederhanakan ganti $z$s dengan $\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$$
dan selesai. Perhatikan bahwa prosedur ini juga akan berfungsi untuk QUBO$\rightarrow$Ising Hamiltonian (lihat jawaban ini ). Dengan cara ini kita akan dapat menyusun cost Hamiltonian dengan properti yang diinginkan (dalam QAOA):
$$H_C |x\rangle = f(x)|x\rangle$$
dimana $x = x_1 x_2 x_3 x_4$ adalah bitstring.
Contoh cost Hamiltonian dengan$3$kopling-tubuh antara qubit dapat ditemukan dalam makalah ini [ 2 ] untuk masalah E3LIN2 ([ 2 ] Persamaan.$6$ dengan notasi yang sedikit berubah):
$$ H_C = \frac{1}{2} \sum_{a < b < c} d_{abc} \sigma_a^z \sigma_b^z \sigma_c^z \tag{6}$$
dimana $d_{abc}$ adalah $0$ atau $+1$ atau $-1$, $a$, $b$ dan $c$ adalah indeks qubit.
[ 1 ] Z. Wang, S. Hadfield, Z. Jiang, EG Rieffel, "The Quantum Approximation Optimization Algorithm for MaxCut: A Fermionic View"
[ 2 ] E. Farhi, J. Goldstone, S. Gutmann, "Algoritma Pengoptimalan Perkiraan Kuantum yang Diterapkan pada Masalah Kendala Kejadian Terikat"