QUBO, Hamiltonianos de Ising e VQA

Question

Eu entendo que normalmente os problemas de otimização combinatória são transformados em QUBO, que tem um mapeamento muito simples para os hamiltonianos de Ising. Os hamiltonianos de Ising, por sua vez, têm as propriedades desejadas de serem diagonais na base computacional e o estado fundamental é um dos vetores da base computacional. Portanto, é fácil medir o estado na base computacional e obter a solução da string de bits.

O problema é que o hamiltoniano de Ising e o QUBO são quadráticos em seus termos e permitem no máximo 2 interações corporais. Recentemente encontrei um artigo sobre fatoração de inteiros expressa como problema de otimização ( fatoração quântica de 56153 com apenas 4 qubits ), onde a função de custo é um polinômio de terceiro grau. Consegui reduzir isso para 2 interações de corpo e, assim, tornar o problema QUBO, mapeá-lo para Ising Hamiltoniano e resolvê-lo em máquinas IBM usando QAOA. No entanto, essa conversão entre polinômio de grau 3 para grau 2 me custa qubits extras.

Qual é então a abordagem geral quando você tem 3/4 interações corporais, por exemplo, como neste artigo que vinculei? Os autores deste, assim como os autores de trabalhos anteriores por eles citados, não se preocupam com o fato de que este não é QUBO. Existem alternativas aos hamiltonianos de Ising e QUBOs em tais casos? É correto que poderíamos usar qualquer forma de hamiltoniano (não necessariamente Ising) para QAOA / VQE, contanto que seja decomposto em produtos tensores de operadores Z de Pauli (o que o torna diagonal na base computacional)?

Answer 1

Na definição deste artigo [ 1 ] o hamiltoniano de custo não se restringe ao caso hamiltoniano de Ising. O artigo [ 1 ] também tem uma resposta para a mencionada "abordagem geral para$3/4$ ($n$) interações corporais ".

Uma citação direta de [ 1 ]:

De uma função de custo clássica que é um polinômio em variáveis ​​binárias $x_1 , . . . , x_n $, podemos construir um hamiltoniano $H_C$ em $n$ qubits, primeiro reescrevendo a função de custo em termos de variáveis $z_i \in \{−1, 1 \}$, Onde $x_i = (1 − z_i )/2$ para obter um polinômio $f (z) = \sum_{C \subset \{1,...n\}} \alpha_C \prod_{j \in C} z_j$ e então substituindo cada ocorrência de $z_i$ com a operadora Pauli $\sigma_i^z$. Portanto,$H_C$ é diagonal no $\sigma_z$-base e assume a forma

$$H_C = \sum_{C \subset \{1,...,n\}} \alpha_C \bigotimes_{j \in C} \sigma_i^z \tag{2}$$

Onde $C$ é um subconjunto de todos os qubits, e $\alpha_C$ é um coeficiente real para o acoplamento de muitos corpos entre qubits no subconjunto $C$.

Isso significa que se tivermos uma função de custo clássica$f(x) = 4 x_1 +6x_1 x_2 - 2x_2 x_3 x_4$, devemos substituir $x$s com $z$se obter:

$$f(z) = 2(1 - z_1) + 3 (1 - z_1) (1 - z_2) - (1 - z_2) (1 - z_3) (1 - z_4)$$

Depois de simplificar substitua $z$s com $\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$$

E feito. Observe que este procedimento funcionará também para QUBO$\rightarrow$Ising hamiltoniano (veja esta resposta ). Desta forma, poderemos construir o Hamiltoniano de custo com a propriedade desejada (em QAOA):

$$H_C |x\rangle = f(x)|x\rangle$$

Onde $x = x_1 x_2 x_3 x_4$ é um bitstring.

Um exemplo do custo Hamiltoniano com$3$O acoplamento de corpos entre qubits pode ser encontrado neste artigo [ 2 ] para o problema E3LIN2 ([ 2 ] Eq.$6$ com notações ligeiramente alteradas):

$$ H_C = \frac{1}{2} \sum_{a < b < c} d_{abc} \sigma_a^z \sigma_b^z \sigma_c^z \tag{6}$$

Onde $d_{abc}$ é $0$ ou $+1$ ou $-1$, $a$, $b$ e $c$ são índices 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, "A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem"