QUBO, Ising Hamiltonians และ VQA
ฉันเข้าใจว่าโดยปกติแล้วปัญหาการเพิ่มประสิทธิภาพ Combinatorial จะกลายเป็น QUBO ซึ่งมีการจับคู่กับ Ising Hamiltonians ที่ง่ายมาก ในทางกลับกัน Ising Hamiltonians มีคุณสมบัติที่ต้องการในการเป็นเส้นทแยงมุมในพื้นฐานการคำนวณและสถานะพื้นดินเป็นหนึ่งในเวกเตอร์พื้นฐานการคำนวณ ดังนั้นจึงเป็นเรื่องง่ายที่จะวัดสถานะในพื้นฐานการคำนวณและรับโซลูชันสตริงบิต
ปัญหาคือ Ising Hamiltonian และ QUBO เป็นกำลังสองตามเงื่อนไขและอนุญาตให้มีการโต้ตอบกับร่างกายได้สูงสุด 2 ครั้ง ฉันเพิ่งเจอบทความเกี่ยวกับการแยกตัวประกอบจำนวนเต็มซึ่งแสดงเป็นปัญหาการเพิ่มประสิทธิภาพ (การแยกตัวประกอบควอนตัมของ 56153 ที่มีเพียง 4 qubits ) โดยที่ฟังก์ชันต้นทุนเป็นพหุนามระดับที่สาม ฉันสามารถลดการโต้ตอบนี้เป็น 2 การโต้ตอบของร่างกายและทำให้ปัญหา QUBO แมปกับ Ising Hamiltonian และแก้ปัญหาบนเครื่อง IBM โดยใช้ QAOA อย่างไรก็ตามการแปลงระหว่างพหุนามระดับ 3 ถึงระดับ 2 นี้ทำให้ฉันเสียค่า qubits เพิ่ม
แล้วอะไรคือแนวทางทั่วไปเมื่อคุณมีปฏิสัมพันธ์ของร่างกาย 3/4 เช่นในบทความนี้ฉันเชื่อมโยง? ผู้เขียนเรื่องนี้ตลอดจนผู้เขียนผลงานก่อนหน้านี้ที่พวกเขาอ้างถึงไม่เกี่ยวข้องกับข้อเท็จจริงที่ว่านี่ไม่ใช่ QUBO มีทางเลือกอื่นสำหรับ Ising Hamiltonians และ QUBO ในกรณีเช่นนี้หรือไม่? ถูกต้องหรือไม่ที่เราสามารถใช้ Hamiltonian รูปแบบใดก็ได้ (ไม่จำเป็นต้องเป็น Ising) สำหรับ QAOA / VQE ตราบใดที่สามารถย่อยสลายเป็นผลิตภัณฑ์เทนเซอร์ของตัวดำเนินการ Pauli Z (ซึ่งทำให้เป็นแนวทแยงในการคำนวณ)
คำตอบ
ในคำจำกัดความจากบทความนี้ [ 1 ] ค่าใช้จ่ายของแฮมิลตันไม่ได้ จำกัด เฉพาะกรณีของอิสซิงแฮมิลตัน กระดาษ [ 1 ] ยังมีคำตอบสำหรับ "แนวทางทั่วไปสำหรับ$3/4$ ($n$) ปฏิสัมพันธ์ของร่างกาย ".
คำพูดโดยตรงจาก [ 1 ]:
จากฟังก์ชันต้นทุนคลาสสิกที่เป็นพหุนามในตัวแปรไบนารี $x_1 , . . . , x_n $เราสามารถสร้างแฮมิลตันได้ $H_C$ บน $n$ qubits โดยการเขียนฟังก์ชันต้นทุนใหม่ในแง่ของตัวแปรก่อน $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$ ด้วยตัวดำเนินการ Pauli $\sigma_i^z$. ด้วยประการฉะนี้$H_C$ อยู่ในแนวทแยงใน $\sigma_z$-basis และอยู่ในรูปแบบ
$$H_C = \sum_{C \subset \{1,...,n\}} \alpha_C \bigotimes_{j \in C} \sigma_i^z \tag{2}$$
ที่ไหน $C$ เป็นส่วนย่อยของ qubits ทั้งหมดและ $\alpha_C$ เป็นค่าสัมประสิทธิ์ที่แท้จริงสำหรับการมีเพศสัมพันธ์หลายตัวระหว่างควิตในส่วนย่อย $C$.
ซึ่งหมายความว่าถ้าเรามีฟังก์ชันต้นทุนแบบคลาสสิก$f(x) = 4 x_1 +6x_1 x_2 - 2x_2 x_3 x_4$เราควรเปลี่ยน $x$s ด้วย $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$s ด้วย $\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$Ising Hamiltonian (ดูคำตอบนี้) ด้วยวิธีนี้เราจะสามารถสร้างต้นทุนแฮมิลตันด้วยคุณสมบัติที่ต้องการ (ใน QAOA):
$$H_C |x\rangle = f(x)|x\rangle$$
ที่ไหน $x = x_1 x_2 x_3 x_4$ เป็นบิตสตริง
ตัวอย่างค่าใช้จ่ายของ Hamiltonian กับ$3$-body coupling ระหว่าง qubits สามารถพบได้ในบทความนี้ [ 2 ] สำหรับปัญหา E3LIN2 ([ 2 ] Eq.$6$ ด้วยสัญกรณ์ที่เปลี่ยนแปลงเล็กน้อย):
$$ H_C = \frac{1}{2} \sum_{a < b < c} d_{abc} \sigma_a^z \sigma_b^z \sigma_c^z \tag{6}$$
ที่ไหน $d_{abc}$ คือ $0$ หรือ $+1$ หรือ $-1$, $a$, $b$ และ $c$ คือดัชนี qubit
[ 1 ] Z. Wang, S. Hadfield, Z. Jiang, EG Rieffel, "อัลกอริธึมการเพิ่มประสิทธิภาพการประมาณควอนตัมสำหรับ MaxCut: มุมมอง Fermionic"
[ 2 ] E. Farhi, J. Goldstone, S. Gutmann, "อัลกอริทึมการเพิ่มประสิทธิภาพโดยประมาณควอนตัมที่ใช้กับปัญหาข้อ จำกัด การเกิดขึ้นที่มีขอบเขต"