Existe um método geral de expressar o problema de otimização como um hamiltoniano?

Digamos que temos um problema de otimização no formato:

$$\min_x f(x) \\ g_i(x) \leq 0, i = 1, ..., m \\ h_j(x) = 0, j = 1, ..., p,$$

onde $f(x)$ é uma função objetiva, $g_i(x)$ são restrições de desigualdade e $h_j(x)$ são restrições de igualdade.

Recentemente, eu estava lendo sobre a computação quântica adiabática . A Wikipedia diz:

Primeiro, é encontrado um hamiltoniano (potencialmente complicado) cujo estado fundamental descreve a solução para o problema de interesse. Em seguida, um sistema com um hamiltoniano simples é preparado e inicializado para o estado fundamental. Finalmente, o hamiltoniano simples é adiabaticamente evoluído para o hamiltoniano complicado e desejado. Pelo teorema adiabático, o sistema permanece no estado fundamental, portanto, no final, o estado do sistema descreve a solução para o problema. A computação quântica adiabática demonstrou ser polinomialmente equivalente à computação quântica convencional no modelo de circuito.

Existe algum método geral de expressar o problema de otimização (por exemplo, como apresentado acima) no formalismo hamiltoniano usado na computação quântica adiabática ?

Conforme solicitado nos comentários, aqui está um exemplo trabalhado. O corpo principal lida com a minimização de para um problema específico. Na parte inferior, segue-se uma breve discussão sobre restrições e, em seguida, uma breve discussão sobre o caso geral.$f(x)$

Vamos resolver o problema de corte máximo ponderado, pois

1. É um exemplo relativamente direto
2. É difícil classicamente
3. É um exemplo relativamente comum na literatura (por exemplo, https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.90.067903 )
4. Possui uma conexão clara com um Hamiltoniano físico (óculos Ising)

Para entender o problema, começamos com um gráfico não direcionado de vértices , em que cada vértice tem peso e cada aresta que conecta e tem peso . Em seguida, cortamos o gráfico em dois pedaços. O corte não precisa ser reto, mas não deve se auto-interceptar e não pode cortar nenhuma aresta duas vezes. Em seguida, calculamos um " pagamento " para o nosso corte. O pagamento é a soma dos pesos das arestas pelas quais cortamos, mais a soma dos pesos dos vértices em um lado do corte. $n$$\{V\}$$v_i\in V$$w_i\geq0$$v_i$$v_j$$w_{ij}\geq0$P 1$P$$^1$

Fonte

Nesta imagem, o pagamento seria: para as arestas mais para os vértices (assumindo que o número dentro de cada vértice seja o seu peso) . O problema de otimização é maximizar para um determinado gráfico . $1+4+3+3+2 = 13$$5+6+1 = 12$$\to P=25$P 2$P$$^2$

Para escrever isso matematicamente, podemos pensar em termos de cadeias de bits. Definimos um corte por uma string que não é contado na soma e é contado na soma. Para tornar a matemática um pouco mais limpa, se o gráfico não estiver totalmente conectado, faça com que o gráfico esteja totalmente conectado e defina para quaisquer pares não conectados .$s\in\{0,1\}^n$$s_i=0\to v_i$ s i = 1 → v i w i j$s_i=1\to v_i$ $w_{ij}=0$$v_i,v_j$

Por exemplo, olhando a imagem acima novamente, vamos interpretar os números dentro dos vértices como o índice de vértices, em vez do peso, como assumimos acima. Então o corte desenhado corresponde a . estão no lado "bom" do corte e são contados, enquanto estão no lado "ruim" do corte e não são contados .$s=100011$$s_1=s_5=s_6=1\to v_1, v_5, v_6$$s_2=s_3=s_4=0$

Isso nos permite escrever

$$P(s) = \sum_i s_i w_i + \sum_{i,j} s_i(1-s_j)w_{ij}$$

O primeiro termo conta apenas os pesos de todos os vértices no lado "bom" do corte. O segundo termo conta o peso de uma aresta se os vértices que ela conectar estiverem em lados opostos do corte. Observe que isso não conta duas vezes, pois só conta a aresta quando e não quando .$s_i=1, s_j=0$$s_i=0, s_j=1$

Então agora nosso problema de otimização é encontrar a string que maximiza . A idéia aqui é pensar em como uma medida de energia de um sistema como o estado do sistema. Isso significa que podemos relacionar ao nosso Hamiltoniano. Aqui está um pouco sutil que estamos tentando maximizar mas geralmente falamos em encontrar o estado fundamental de um Hamiltoniano. Isso não é um problema, mas eu queria salientar - podemos observar o estado de excitação mais alta de energia (estado anti-terra, se ) ou usar como nossa função de energia e trabalhar com o estado fundamental como normal. O trabalho de Let com a mais alta animado estado e maximizar .$s$$P(s)$$P(s)$$s$$P(s)$$P(s)$$-P(s)$$P$

Gostaríamos de criar um hamiltoniano de modo que seu estado de energia mais alto seja modo que seja o máximo. Essencialmente, queremos transformar , uma função de energia, em , um operador de energia. Fazemos isso observando que, para , temos$|s_0\rangle$$P(s_0)$$P(s)$H | s ⟩ ∈ { | 0 ⟩ , | 1 ⟩ } eu - Z$\hat{H}$$|s\rangle\in\{|0\rangle,|1\rangle\}$

$$\frac{I-Z}{2}|s\rangle=s|s\rangle\to\text{ define } \hat{s}_i=\frac{I-Z_i}{2}$$

Onde é o Pauli agindo no qubit . Agora obtemos nosso Hamiltoniano substituindo por (e 1 por ) em$Z_i$$Z$$i$s$s$$\hat{s}$$I$$P$

$$H=\sum_i \hat{s}_i w_i + \sum_{i,j} \hat{s}_i(I-\hat{s}_j)w_{i,j}=\sum_i\frac{I-Z_i}{2} w_i + \sum_{i,j} \frac{I-Z_i}{2}\left(I-\frac{I-Z_j}{2}\right)w_{i,j}$$

Isso pode ser limpo expandindo e vendo$\sum_{i,j}(Z_i-Z_j)=0\to$

$$H=\sum_i \frac{w_i}{2}\left(I-Z_i\right) + \sum_{i,j} \frac{w_{ij}}{4}\left(I-Z_iZ_j\right)=\sum_i \frac{w_i}{2}\left(I-Z_i\right) + \sum_{i<j} \frac{w_{ij}}{2}\left(I-Z_iZ_j\right)$$

Podemos limpar isso ainda mais, multiplicando por 2 e removendo uma constante mudança de energia (exclua os termos ). Novo Hamiltoniano com os mesmos valores próprios com valores próprios redimensionados e deslocados (claramente a energia máxima não é afetada por essas transformações)$I$

$$H=-\sum_i w_iZ_i - \sum_{i<j} w_{ij}Z_iZ_j$$

Se você é um físico de matéria condensada, provavelmente reconhecerá esse hamiltoniano como um vidro de spin de Ising. Não é realmente relevante para o problema, mas acho que é legal.

Então agora temos um hamiltoniano cujo estado (anti-) fundamental codifica a sequência de bits que maximiza e resolve o problema.$s_0$$P(s)$

A última coisa que precisamos é de um Hamiltoniano inicial , que lentamente (adiabaticamente) transformamos em nosso Hamiltoniano final, para que possamos definir o Hamiltoniano completo$H_0$$H$

$$H_T(t)=(1-f(t))H_0 + f(t)H: f(0)=0, f(t_f)=1$$

Como ponto de partida, é frequentemente usado para simplificar. O mínimo determinado pela precisão desejada e pelo intervalo espectral . O intervalo espectral é a diferença mínima de energia, acima de todos os , entre o estado (anti-) fundamental e o próximo estado energético. A análise da lacuna é altamente não trivial (consulte https://arxiv.org/abs/quant-ph/0509162 ) e determina a complexidade / eficiência do algoritmo. Um algoritmo com 0 intervalo não é garantido para funcionar.$f(t)\propto t$$t_f$$^3$$t$

Então, queremos um tal que$H_0$

1. Podemos encontrar e preparar facilmente seu (anti) estado fundamental
2. O intervalo espectral de não é exponencialmente pequeno no tamanho do problema$H$

Para esse problema, um bom Hamiltoniano inicial é porque é fácil encontrar o estado de energia mais alto, é . É fácil de preparar, basta aplicar a . Não tenho tempo para entrar na análise da lacuna espectral, mas é improvável que esse hamiltoniano seja ideal nesse sentido (consulte https://arxiv.org/abs/1701.05584 ).$H_0 = \sum_i X_i$$|+\rangle^{\otimes n}$$H^{\otimes n}$$|0\rangle^{\otimes n}$

Com essa escolha de e tomando , terminamos. Nosso Hamiltoniano é$H_0$$f(t)=t/t_f$

$$H(t) = \left(1-f(t)\right)\sum_i X_i-f(t)\left[\sum_i w_iZ_i + \sum_{i<j} w_{ij}Z_iZ_j\right]$$

Começando no estado , evoluindo de acordo com o Hamiltoniano acima para o tempo (escolher um adequado é, novamente, geralmente altamente não trivial ), então a medição na base computacional deve retornar (com alta probabilidade) a string que maximiza .$|\psi_0\rangle = H^{\otimes n}|0\rangle^{\otimes n}$$t_f$$t_f$$s=s_0$$P(s)$

$^1$ Isso é ambíguo, pois por simetria os dois lados o farão. Podemos fazer isso rigoroso, por exemplo, direcionando o corte e levando os vértices para a esquerda do corte ao caminhar na direção do corte.

$^2$ Eu disse no comentário que minimizamos uma função de custo; se você prefere isso, basta pegar o custo pagamento e minimizar o custo.$=-$

$^3$ Estou examinando alguns detalhes sobre o que "lento" significa embaixo do tapete, mas pode estar relacionado à escala de energia do problema (por exemplo, multiplicar por uma constante mudará a velocidade).$H$

Restrições

Digamos que queremos modificar o problema acima para exigir que exatamente vértices estejam do lado "bom" do nosso corte. Matematicamente, isso é . Para impor isso, adicionamos um termo de penalidade ao Hamiltoniano para soluções que quebram essa restrição. Portanto, adicionamos um termo como escolhendo grande o suficiente para garantir que um estado que viole essa restrição não seja o estado de energia mais alta.$5$$\sum_i s_i-5=0$$H_c = -\alpha\left(\sum_i \hat{s}_i -5I\right)^2$$\alpha$

Digamos que, em vez disso, queremos exigir que não haja mais de vértices no lado "bom" do nosso corte. Parece que isso é bastante difícil de fazer. Em https://arxiv.org/abs/1702.06248, eles afirmam que aproximar uma restrição de desigualdade para ordenar requer acoplamentos de -pin que exigiriam ainda mais sobrecarga para divida-os em acoplamentos de 2 qubit, o que geralmente é necessário em uma determinada arquitetura. Essencialmente, a estratégia é aproximar uma função de etapa usando um$5$$k$$\mathcal{O}\left(N^{2k}\right)$ $k$$k^\text{th}$ordem polinomial. Parece uma maneira terrível de fazer isso - mas não consigo pensar em uma maneira melhor. Como vem de Troyer em 2017, é relativamente improvável, embora certamente possível, que atualmente seja conhecida uma maneira melhor.

O caso geral

A pergunta é sobre um método geral para codificar um problema de otimização em um hamiltoniano. Especificamente, queremos minimizar sujeito a um conjunto de restrições. Na seção acima, discuti a adição de restrições ao Hamiltoniano. Então, para um completamente geral , existe uma maneira de codificá-lo para um hamiltoniano? O método geral para isso na literatura é assumir que temos acesso a um oráculo quântico eficiente que implementa . Podemos pensar nisso como ter uma operação de caixa preta (ou seja, oráculo quântico) modo que . Então, podemos construir nosso Hamiltoniano como $f(x)$$f(x)$$f(x)$$\hat{f}(x)$$\hat{f}(x)|x\rangle=f(x) |x\rangle$

$$H = \sum_x \hat{f}(x)|x\rangle\langle x|$$ É claro que isso apenas empurra a parte difícil para encontrar / construir . De fato, argumentos simples de contagem mostram que quase todos (no sentido matemático) oráculos quânticos são exponencialmente ineficientes para implementar (consulte http://www.ar-tiste.com/imp-oracles/imps2.pdf ). Portanto, embora essa seja uma codificação geral de um problema de otimização para um Hamiltoniano - não é realmente prático. Parece que se você quiser codificar seu problema de otimização em um hamiltoniano de uma maneira útil - precisará aproveitar alguma estrutura de . Meu entendimento é que as especificidades de exatamente como fazer isso e como fazer isso da melhor maneira$\hat{f}(x)$$f(x)$ maneira não é totalmente compreendida e é objeto de pesquisa ativa.