QUBO, Ising Hamiltonians 및 VQA
나는 일반적으로 조합 최적화 문제가 Ising Hamiltonians에 대한 매우 간단한 매핑을 가진 QUBO로 바뀌는 것을 이해합니다. Ising Hamiltonians는 계산 기반에서 대각선이되는 원하는 속성을 가지며지면 상태는 계산 기반 벡터 중 하나입니다. 따라서 계산 기반으로 상태를 측정하고 비트 문자열 솔루션을 얻는 것이 쉽습니다.
문제는 Ising Hamiltonian과 QUBO가 그 용어로 2 차적이며 최대 2 개의 신체 상호 작용을 허용한다는 것입니다. 나는 최근 에 비용 함수가 3 차 다항식 인 최적화 문제 ( 단지 4 큐 비트를 사용하는 56153의 양자 분해) 로 표현 된 정수 인수 분해에 관한 논문 을 보았습니다 . 나는 이것을 2 개의 신체 상호 작용으로 줄일 수 있었고 따라서 문제를 QUBO로 만들고 Ising Hamiltonian에 매핑하고 QAOA를 사용하여 IBM 컴퓨터에서 해결할 수있었습니다. 그러나 3 차 다항식을 2 차로 변환하려면 추가 큐 비트가 필요합니다.
예를 들어 내가 링크 한이 논문에서와 같이 3/4 신체 상호 작용을 할 때 일반적인 접근 방식은 무엇입니까? 이것의 저자와 그들이 인용하는 이전 작품의 저자는 이것이 QUBO가 아니라는 사실에 관심이 없습니다. 이러한 경우 해밀턴과 QUBO에 대한 대안이 있습니까? Pauli Z 연산자의 텐서 곱으로 분해 될 수있는 한 QAOA / VQE에 대해 어떤 형태의 Hamiltonian (반드시 Ising이 아님)을 사용할 수 있다는 것이 맞습니까?
답변
이 논문의 정의에서 [ 1 ] Hamiltonian의 비용은 Ising Hamiltonian의 경우에만 국한되지 않습니다. 논문 [ 1 ]은 또한 언급 된 "일반적인 접근 방식$3/4$ ($n$) 신체 상호 작용 ".
[ 1 ] 의 직접 인용 :
이진 변수의 다항식 인 고전적인 비용 함수에서 $x_1 , . . . , x_n $, 우리는 Hamiltonian을 구성 할 수 있습니다. $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$ Pauli 연산자와 $\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$에스:
$$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에서 원하는 속성을 사용하여 비용 Hamiltonian을 구성 할 수 있습니다.
$$H_C |x\rangle = f(x)|x\rangle$$
어디 $x = x_1 x_2 x_3 x_4$ 비트 문자열입니다.
Hamiltonian의 비용 의 예$3$큐 비트 간의 커플 링은 몸이 논문 [에서 찾을 수 2 E3LIN2의 문제] ([ 2 ] 식.$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$ 큐 비트 인덱스입니다.
[ 1 ] Z. Wang, S. Hadfield, Z. Jiang, EG Rieffel, "MaxCut을위한 양자 근사화 최적화 알고리즘 : Fermionic View"
[ 2 ] E. Farhi, J. Goldstone, S. Gutmann, "제한된 발생 제약 문제에 적용되는 양자 근사 최적화 알고리즘"