QUBO, Ising Hamiltonians và VQA
Tôi hiểu rằng thông thường các bài toán tối ưu hóa tổ hợp được chuyển thành QUBO, có một ánh xạ rất đơn giản đến Ising Hamiltonians. Đến lượt nó, Ising Hamiltonians có các đặc tính mong muốn là đường chéo trong cơ sở tính toán và trạng thái cơ bản là một trong những vectơ cơ sở tính toán. Do đó, dễ dàng đo trạng thái trong cơ sở tính toán và thu được giải pháp chuỗi bit.
Vấn đề là Ising Hamilton và QUBO là bậc hai theo nghĩa của nó và cho phép nhiều nhất 2 tương tác vật thể. Gần đây tôi đã xem một bài báo về tính toán số nguyên được biểu thị dưới dạng bài toán tối ưu hóa ( Phân tích thừa số lượng tử của 56153 chỉ với 4 qubit ), trong đó hàm chi phí là một đa thức bậc ba. Tôi đã có thể giảm điều này xuống còn 2 tương tác cơ thể và do đó đặt vấn đề thành QUBO, ánh xạ nó thành Ising Hamilton và giải nó trên máy IBM bằng QAOA. Tuy nhiên, việc chuyển đổi này giữa đa thức bậc 3 sang bậc 2 khiến tôi tốn thêm qubit.
Sau đó, cách tiếp cận chung là gì khi bạn có 3/4 cơ thể tương tác, ví dụ như trong bài báo này tôi đã liên kết? Các tác giả của cuốn sách này, cũng như các tác giả của các tác phẩm trước đây mà họ trích dẫn, không quan tâm đến thực tế rằng đây không phải là QUBO. Có lựa chọn thay thế cho Ising Hamiltonians và QUBOs trong những trường hợp như vậy không? Có chính xác không khi chúng ta có thể sử dụng bất kỳ dạng Hamilton nào (không nhất thiết là Ising) cho QAOA / VQE miễn là nó có thể phân hủy thành các sản phẩm tensor của các toán tử Pauli Z (làm cho nó chéo trong cơ sở tính toán)?
Trả lời
Trong định nghĩa từ bài báo này [ 1 ] giá trị Hamilton không bị giới hạn trong trường hợp Ising Hamilton. Bài báo [ 1 ] cũng có câu trả lời cho "cách tiếp cận chung cho$3/4$ ($n$) các tương tác cơ thể ”.
Trích dẫn trực tiếp từ [ 1 ]:
Từ một hàm chi phí cổ điển là một đa thức trong các biến nhị phân $x_1 , . . . , x_n $, chúng ta có thể xây dựng một Hamilton $H_C$ trên $n$ qubit bằng cách viết lại đầu tiên hàm chi phí theo các biến $z_i \in \{−1, 1 \}$, Ở đâu $x_i = (1 − z_i )/2$ để có được một đa thức $f (z) = \sum_{C \subset \{1,...n\}} \alpha_C \prod_{j \in C} z_j$ và sau đó thay thế mỗi lần xuất hiện $z_i$ với nhà điều hành Pauli $\sigma_i^z$. Vì vậy,$H_C$ là đường chéo trong $\sigma_z$-basis và có hình thức
$$H_C = \sum_{C \subset \{1,...,n\}} \alpha_C \bigotimes_{j \in C} \sigma_i^z \tag{2}$$
Ở đâu $C$ là một tập hợp con của tất cả các qubit, và $\alpha_C$ là một hệ số thực cho sự ghép nối nhiều phần giữa các qubit trong tập con $C$.
Điều này có nghĩa là nếu chúng ta có một hàm chi phí cổ điển$f(x) = 4 x_1 +6x_1 x_2 - 2x_2 x_3 x_4$, chúng ta nên thay thế $x$s với $z$s và lấy:
$$f(z) = 2(1 - z_1) + 3 (1 - z_1) (1 - z_2) - (1 - z_2) (1 - z_3) (1 - z_4)$$
Sau khi đơn giản hóa thay thế $z$s với $\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$$
và thực hiện. Lưu ý rằng quy trình này cũng sẽ hoạt động đối với QUBO$\rightarrow$Ising Hamiltonian (xem câu trả lời này ). Bằng cách này, chúng ta sẽ có thể xây dựng chi phí Hamilton với thuộc tính mong muốn (trong QAOA):
$$H_C |x\rangle = f(x)|x\rangle$$
Ở đâu $x = x_1 x_2 x_3 x_4$ là một chuỗi bit.
Một ví dụ về chi phí Hamilton với$3$-body khớp nối giữa các qubit có thể được tìm thấy trong bài báo này [ 2 ] cho bài toán E3LIN2 ([ 2 ] Eq.$6$ với các ký hiệu được thay đổi một chút):
$$ H_C = \frac{1}{2} \sum_{a < b < c} d_{abc} \sigma_a^z \sigma_b^z \sigma_c^z \tag{6}$$
Ở đâu $d_{abc}$ Là $0$ hoặc là $+1$ hoặc là $-1$, $a$, $b$ và $c$ là các chỉ mục qubit.
[ 1 ] Z. Wang, S. Hadfield, Z. Jiang, EG Rieffel, "Thuật toán tối ưu hóa xấp xỉ lượng tử cho MaxCut: A Fermionic View"
[ 2 ] E. Farhi, J. Goldstone, S. Gutmann, "Một thuật toán tối ưu hóa gần đúng lượng tử được áp dụng cho một vấn đề ràng buộc về sự xuất hiện có giới hạn"